diff --git a/core/java/android/content/pm/PackageParser.java b/core/java/android/content/pm/PackageParser.java
index ca4ff6a..8515520 100644
--- a/core/java/android/content/pm/PackageParser.java
+++ b/core/java/android/content/pm/PackageParser.java
@@ -74,7 +74,6 @@
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
@@ -380,7 +379,7 @@
      */
     public static PackageInfo generatePackageInfo(PackageParser.Package p,
             int gids[], int flags, long firstInstallTime, long lastUpdateTime,
-            HashSet<String> grantedPermissions, PackageUserState state) {
+            ArraySet<String> grantedPermissions, PackageUserState state) {
 
         return generatePackageInfo(p, gids, flags, firstInstallTime, lastUpdateTime,
                 grantedPermissions, state, UserHandle.getCallingUserId());
@@ -401,7 +400,7 @@
 
     public static PackageInfo generatePackageInfo(PackageParser.Package p,
             int gids[], int flags, long firstInstallTime, long lastUpdateTime,
-            HashSet<String> grantedPermissions, PackageUserState state, int userId) {
+            ArraySet<String> grantedPermissions, PackageUserState state, int userId) {
 
         if (!checkUseInstalledOrHidden(flags, state)) {
             return null;
diff --git a/core/java/android/content/pm/PackageUserState.java b/core/java/android/content/pm/PackageUserState.java
index 4dcad6f..a9c7be3 100644
--- a/core/java/android/content/pm/PackageUserState.java
+++ b/core/java/android/content/pm/PackageUserState.java
@@ -18,7 +18,7 @@
 
 import static android.content.pm.PackageManager.COMPONENT_ENABLED_STATE_DEFAULT;
 
-import java.util.HashSet;
+import android.util.ArraySet;
 
 /**
  * Per-user state information about a package.
@@ -34,8 +34,8 @@
 
     public String lastDisableAppCaller;
 
-    public HashSet<String> disabledComponents;
-    public HashSet<String> enabledComponents;
+    public ArraySet<String> disabledComponents;
+    public ArraySet<String> enabledComponents;
 
     public PackageUserState() {
         installed = true;
@@ -51,9 +51,9 @@
         hidden = o.hidden;
         lastDisableAppCaller = o.lastDisableAppCaller;
         disabledComponents = o.disabledComponents != null
-                ? new HashSet<String>(o.disabledComponents) : null;
+                ? new ArraySet<String>(o.disabledComponents) : null;
         enabledComponents = o.enabledComponents != null
-                ? new HashSet<String>(o.enabledComponents) : null;
+                ? new ArraySet<String>(o.enabledComponents) : null;
         blockUninstall = o.blockUninstall;
     }
-}
\ No newline at end of file
+}
diff --git a/core/java/android/util/ArraySet.java b/core/java/android/util/ArraySet.java
index 423e48b..68f725e 100644
--- a/core/java/android/util/ArraySet.java
+++ b/core/java/android/util/ArraySet.java
@@ -245,13 +245,20 @@
     /**
      * Create a new ArraySet with the mappings from the given ArraySet.
      */
-    public ArraySet(ArraySet set) {
+    public ArraySet(ArraySet<E> set) {
         this();
         if (set != null) {
             addAll(set);
         }
     }
 
+    /** {@hide} */
+    public ArraySet(Collection<E> set) {
+        this();
+        if (set != null) {
+            addAll(set);
+        }
+    }
 
     /**
      * Make the array map empty.  All storage is released.
diff --git a/services/core/java/com/android/server/IntentResolver.java b/services/core/java/com/android/server/IntentResolver.java
index 07cc864..387eabc 100644
--- a/services/core/java/com/android/server/IntentResolver.java
+++ b/services/core/java/com/android/server/IntentResolver.java
@@ -21,7 +21,6 @@
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
@@ -30,6 +29,7 @@
 import android.net.Uri;
 import android.util.FastImmutableArraySet;
 import android.util.ArrayMap;
+import android.util.ArraySet;
 import android.util.Log;
 import android.util.PrintWriterPrinter;
 import android.util.Slog;
@@ -736,7 +736,7 @@
     /**
      * All filters that have been registered.
      */
-    private final HashSet<F> mFilters = new HashSet<F>();
+    private final ArraySet<F> mFilters = new ArraySet<F>();
 
     /**
      * All of the MIME types that have been registered, such as "image/jpeg",
diff --git a/services/core/java/com/android/server/SystemConfig.java b/services/core/java/com/android/server/SystemConfig.java
index cf2a49f..f4fb519 100644
--- a/services/core/java/com/android/server/SystemConfig.java
+++ b/services/core/java/com/android/server/SystemConfig.java
@@ -32,8 +32,6 @@
 import java.io.FileNotFoundException;
 import java.io.FileReader;
 import java.io.IOException;
-import java.util.HashMap;
-import java.util.HashSet;
 
 import static com.android.internal.util.ArrayUtils.appendInt;
 
@@ -50,7 +48,7 @@
 
     // These are the built-in uid -> permission mappings that were read from the
     // system configuration files.
-    final SparseArray<HashSet<String>> mSystemPermissions = new SparseArray<>();
+    final SparseArray<ArraySet<String>> mSystemPermissions = new SparseArray<>();
 
     // These are the built-in shared libraries that were read from the
     // system configuration files.  Keys are the library names; strings are the
@@ -59,7 +57,7 @@
 
     // These are the features this devices supports that were read from the
     // system configuration files.
-    final HashMap<String, FeatureInfo> mAvailableFeatures = new HashMap<>();
+    final ArrayMap<String, FeatureInfo> mAvailableFeatures = new ArrayMap<>();
 
     public static final class PermissionEntry {
         public final String name;
@@ -94,7 +92,7 @@
         return mGlobalGids;
     }
 
-    public SparseArray<HashSet<String>> getSystemPermissions() {
+    public SparseArray<ArraySet<String>> getSystemPermissions() {
         return mSystemPermissions;
     }
 
@@ -102,7 +100,7 @@
         return mSharedLibraries;
     }
 
-    public HashMap<String, FeatureInfo> getAvailableFeatures() {
+    public ArrayMap<String, FeatureInfo> getAvailableFeatures() {
         return mAvailableFeatures;
     }
 
@@ -252,9 +250,9 @@
                         continue;
                     }
                     perm = perm.intern();
-                    HashSet<String> perms = mSystemPermissions.get(uid);
+                    ArraySet<String> perms = mSystemPermissions.get(uid);
                     if (perms == null) {
-                        perms = new HashSet<String>();
+                        perms = new ArraySet<String>();
                         mSystemPermissions.put(uid, perms);
                     }
                     perms.add(perm);
diff --git a/services/core/java/com/android/server/pm/BackgroundDexOptService.java b/services/core/java/com/android/server/pm/BackgroundDexOptService.java
index a7eebf8..cb9a45e 100644
--- a/services/core/java/com/android/server/pm/BackgroundDexOptService.java
+++ b/services/core/java/com/android/server/pm/BackgroundDexOptService.java
@@ -23,9 +23,9 @@
 import android.content.ComponentName;
 import android.content.Context;
 import android.os.ServiceManager;
+import android.util.ArraySet;
 import android.util.Log;
 
-import java.util.HashSet;
 import java.util.concurrent.atomic.AtomicBoolean;
 
 /**
@@ -59,7 +59,7 @@
         if (pm.isStorageLow()) {
             return false;
         }
-        final HashSet<String> pkgs = pm.getPackagesThatNeedDexOpt();
+        final ArraySet<String> pkgs = pm.getPackagesThatNeedDexOpt();
         if (pkgs == null) {
             return false;
         }
diff --git a/services/core/java/com/android/server/pm/GrantedPermissions.java b/services/core/java/com/android/server/pm/GrantedPermissions.java
index 14258a4..8f0f935 100644
--- a/services/core/java/com/android/server/pm/GrantedPermissions.java
+++ b/services/core/java/com/android/server/pm/GrantedPermissions.java
@@ -17,13 +17,12 @@
 package com.android.server.pm;
 
 import android.content.pm.ApplicationInfo;
-
-import java.util.HashSet;
+import android.util.ArraySet;
 
 class GrantedPermissions {
     int pkgFlags;
 
-    HashSet<String> grantedPermissions = new HashSet<String>();
+    ArraySet<String> grantedPermissions = new ArraySet<String>();
 
     int[] gids;
 
@@ -34,7 +33,7 @@
     @SuppressWarnings("unchecked")
     GrantedPermissions(GrantedPermissions base) {
         pkgFlags = base.pkgFlags;
-        grantedPermissions = (HashSet<String>) base.grantedPermissions.clone();
+        grantedPermissions = new ArraySet<>(base.grantedPermissions);
 
         if (base.gids != null) {
             gids = base.gids.clone();
diff --git a/services/core/java/com/android/server/pm/PackageKeySetData.java b/services/core/java/com/android/server/pm/PackageKeySetData.java
index 9f9bafd..8f12c03 100644
--- a/services/core/java/com/android/server/pm/PackageKeySetData.java
+++ b/services/core/java/com/android/server/pm/PackageKeySetData.java
@@ -16,10 +16,9 @@
 
 package com.android.server.pm;
 
-import com.android.internal.util.ArrayUtils;
+import android.util.ArrayMap;
 
-import java.util.HashMap;
-import java.util.Map;
+import com.android.internal.util.ArrayUtils;
 
 public class PackageKeySetData {
 
@@ -34,7 +33,7 @@
 
     private long[] mDefinedKeySets;
 
-    private final Map<String, Long> mKeySetAliases = new HashMap<String, Long>();
+    private final ArrayMap<String, Long> mKeySetAliases = new ArrayMap<String, Long>();
 
     PackageKeySetData() {
         mProperSigningKeySet = KEYSET_UNASSIGNED;
@@ -132,7 +131,7 @@
         return mDefinedKeySets;
     }
 
-    protected Map<String, Long> getAliases() {
+    protected ArrayMap<String, Long> getAliases() {
         return mKeySetAliases;
     }
 
diff --git a/services/core/java/com/android/server/pm/PackageManagerService.java b/services/core/java/com/android/server/pm/PackageManagerService.java
index b79e157..056c2e6 100644
--- a/services/core/java/com/android/server/pm/PackageManagerService.java
+++ b/services/core/java/com/android/server/pm/PackageManagerService.java
@@ -199,8 +199,6 @@
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.Date;
-import java.util.HashMap;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
@@ -371,20 +369,20 @@
     // Keys are String (package name), values are Package.  This also serves
     // as the lock for the global state.  Methods that must be called with
     // this lock held have the prefix "LP".
-    final HashMap<String, PackageParser.Package> mPackages =
-            new HashMap<String, PackageParser.Package>();
+    final ArrayMap<String, PackageParser.Package> mPackages =
+            new ArrayMap<String, PackageParser.Package>();
 
     // Tracks available target package names -> overlay package paths.
-    final HashMap<String, HashMap<String, PackageParser.Package>> mOverlays =
-        new HashMap<String, HashMap<String, PackageParser.Package>>();
+    final ArrayMap<String, ArrayMap<String, PackageParser.Package>> mOverlays =
+        new ArrayMap<String, ArrayMap<String, PackageParser.Package>>();
 
     final Settings mSettings;
     boolean mRestoredSettings;
 
     // System configuration read by SystemConfig.
     final int[] mGlobalGids;
-    final SparseArray<HashSet<String>> mSystemPermissions;
-    final HashMap<String, FeatureInfo> mAvailableFeatures;
+    final SparseArray<ArraySet<String>> mSystemPermissions;
+    final ArrayMap<String, FeatureInfo> mAvailableFeatures;
 
     // If mac_permissions.xml was found for seinfo labeling.
     boolean mFoundPolicyFile;
@@ -403,8 +401,8 @@
     }
 
     // Currently known shared libraries.
-    final HashMap<String, SharedLibraryEntry> mSharedLibraries =
-            new HashMap<String, SharedLibraryEntry>();
+    final ArrayMap<String, SharedLibraryEntry> mSharedLibraries =
+            new ArrayMap<String, SharedLibraryEntry>();
 
     // All available activities, for your resolving pleasure.
     final ActivityIntentResolver mActivities =
@@ -422,23 +420,23 @@
 
     // Mapping from provider base names (first directory in content URI codePath)
     // to the provider information.
-    final HashMap<String, PackageParser.Provider> mProvidersByAuthority =
-            new HashMap<String, PackageParser.Provider>();
+    final ArrayMap<String, PackageParser.Provider> mProvidersByAuthority =
+            new ArrayMap<String, PackageParser.Provider>();
 
     // Mapping from instrumentation class names to info about them.
-    final HashMap<ComponentName, PackageParser.Instrumentation> mInstrumentation =
-            new HashMap<ComponentName, PackageParser.Instrumentation>();
+    final ArrayMap<ComponentName, PackageParser.Instrumentation> mInstrumentation =
+            new ArrayMap<ComponentName, PackageParser.Instrumentation>();
 
     // Mapping from permission names to info about them.
-    final HashMap<String, PackageParser.PermissionGroup> mPermissionGroups =
-            new HashMap<String, PackageParser.PermissionGroup>();
+    final ArrayMap<String, PackageParser.PermissionGroup> mPermissionGroups =
+            new ArrayMap<String, PackageParser.PermissionGroup>();
 
     // Packages whose data we have transfered into another package, thus
     // should no longer exist.
-    final HashSet<String> mTransferedPackages = new HashSet<String>();
+    final ArraySet<String> mTransferedPackages = new ArraySet<String>();
     
     // Broadcast actions that are only available to the system.
-    final HashSet<String> mProtectedBroadcasts = new HashSet<String>();
+    final ArraySet<String> mProtectedBroadcasts = new ArraySet<String>();
 
     /** List of packages waiting for verification. */
     final SparseArray<PackageVerificationState> mPendingVerification
@@ -449,7 +447,7 @@
 
     final PackageInstallerService mInstallerService;
 
-    HashSet<PackageParser.Package> mDeferredDexOpt = null;
+    ArraySet<PackageParser.Package> mDeferredDexOpt = null;
 
     // Cache of users who need badging.
     SparseBooleanArray mUserNeedsBadging = new SparseBooleanArray();
@@ -473,24 +471,24 @@
     // Set of pending broadcasts for aggregating enable/disable of components.
     static class PendingPackageBroadcasts {
         // for each user id, a map of <package name -> components within that package>
-        final SparseArray<HashMap<String, ArrayList<String>>> mUidMap;
+        final SparseArray<ArrayMap<String, ArrayList<String>>> mUidMap;
 
         public PendingPackageBroadcasts() {
-            mUidMap = new SparseArray<HashMap<String, ArrayList<String>>>(2);
+            mUidMap = new SparseArray<ArrayMap<String, ArrayList<String>>>(2);
         }
 
         public ArrayList<String> get(int userId, String packageName) {
-            HashMap<String, ArrayList<String>> packages = getOrAllocate(userId);
+            ArrayMap<String, ArrayList<String>> packages = getOrAllocate(userId);
             return packages.get(packageName);
         }
 
         public void put(int userId, String packageName, ArrayList<String> components) {
-            HashMap<String, ArrayList<String>> packages = getOrAllocate(userId);
+            ArrayMap<String, ArrayList<String>> packages = getOrAllocate(userId);
             packages.put(packageName, components);
         }
 
         public void remove(int userId, String packageName) {
-            HashMap<String, ArrayList<String>> packages = mUidMap.get(userId);
+            ArrayMap<String, ArrayList<String>> packages = mUidMap.get(userId);
             if (packages != null) {
                 packages.remove(packageName);
             }
@@ -508,7 +506,7 @@
             return mUidMap.keyAt(n);
         }
 
-        public HashMap<String, ArrayList<String>> packagesForUserId(int userId) {
+        public ArrayMap<String, ArrayList<String>> packagesForUserId(int userId) {
             return mUidMap.get(userId);
         }
 
@@ -525,10 +523,10 @@
             mUidMap.clear();
         }
 
-        private HashMap<String, ArrayList<String>> getOrAllocate(int userId) {
-            HashMap<String, ArrayList<String>> map = mUidMap.get(userId);
+        private ArrayMap<String, ArrayList<String>> getOrAllocate(int userId) {
+            ArrayMap<String, ArrayList<String>> map = mUidMap.get(userId);
             if (map == null) {
-                map = new HashMap<String, ArrayList<String>>();
+                map = new ArrayMap<String, ArrayList<String>>();
                 mUidMap.put(userId, map);
             }
             return map;
@@ -565,7 +563,7 @@
     static UserManagerService sUserManager;
 
     // Stores a list of users whose package restrictions file needs to be updated
-    private HashSet<Integer> mDirtyUsers = new HashSet<Integer>();
+    private ArraySet<Integer> mDirtyUsers = new ArraySet<Integer>();
 
     final private DefaultContainerConnection mDefContainerConn =
             new DefaultContainerConnection();
@@ -1384,7 +1382,7 @@
             // scanning install directories.
             final int scanFlags = SCAN_NO_PATHS | SCAN_DEFER_DEX | SCAN_BOOTING;
 
-            final HashSet<String> alreadyDexOpted = new HashSet<String>();
+            final ArraySet<String> alreadyDexOpted = new ArraySet<String>();
 
             /**
              * Add everything in the in the boot class path to the
@@ -2369,7 +2367,7 @@
                     return PackageManager.PERMISSION_GRANTED;
                 }
             } else {
-                HashSet<String> perms = mSystemPermissions.get(uid);
+                ArraySet<String> perms = mSystemPermissions.get(uid);
                 if (perms != null && perms.contains(permName)) {
                     return PackageManager.PERMISSION_GRANTED;
                 }
@@ -2790,11 +2788,11 @@
                     PackageManager.SIGNATURE_NO_MATCH;
         }
 
-        HashSet<Signature> set1 = new HashSet<Signature>();
+        ArraySet<Signature> set1 = new ArraySet<Signature>();
         for (Signature sig : s1) {
             set1.add(sig);
         }
-        HashSet<Signature> set2 = new HashSet<Signature>();
+        ArraySet<Signature> set2 = new ArraySet<Signature>();
         for (Signature sig : s2) {
             set2.add(sig);
         }
@@ -2829,11 +2827,11 @@
             return PackageManager.SIGNATURE_NO_MATCH;
         }
 
-        HashSet<Signature> existingSet = new HashSet<Signature>();
+        ArraySet<Signature> existingSet = new ArraySet<Signature>();
         for (Signature sig : existingSigs.mSignatures) {
             existingSet.add(sig);
         }
-        HashSet<Signature> scannedCompatSet = new HashSet<Signature>();
+        ArraySet<Signature> scannedCompatSet = new ArraySet<Signature>();
         for (Signature sig : scannedPkg.mSignatures) {
             try {
                 Signature[] chainSignatures = sig.getChainSignatures();
@@ -4023,7 +4021,7 @@
     }
 
     private void createIdmapsForPackageLI(PackageParser.Package pkg) {
-        HashMap<String, PackageParser.Package> overlays = mOverlays.get(pkg.packageName);
+        ArrayMap<String, PackageParser.Package> overlays = mOverlays.get(pkg.packageName);
         if (overlays == null) {
             Slog.w(TAG, "Unable to create idmap for " + pkg.packageName + ": no overlay packages");
             return;
@@ -4044,7 +4042,7 @@
                     opkg.baseCodePath + ": overlay not trusted");
             return false;
         }
-        HashMap<String, PackageParser.Package> overlaySet = mOverlays.get(pkg.packageName);
+        ArrayMap<String, PackageParser.Package> overlaySet = mOverlays.get(pkg.packageName);
         if (overlaySet == null) {
             Slog.e(TAG, "was about to create idmap for " + pkg.baseCodePath + " and " +
                     opkg.baseCodePath + " but target package has no known overlays");
@@ -4465,7 +4463,7 @@
     public void performBootDexOpt() {
         enforceSystemOrRoot("Only the system can request dexopt be performed");
 
-        final HashSet<PackageParser.Package> pkgs;
+        final ArraySet<PackageParser.Package> pkgs;
         synchronized (mPackages) {
             pkgs = mDeferredDexOpt;
             mDeferredDexOpt = null;
@@ -4488,7 +4486,7 @@
             }
             // Give priority to system apps that listen for pre boot complete.
             Intent intent = new Intent(Intent.ACTION_PRE_BOOT_COMPLETED);
-            HashSet<String> pkgNames = getPackageNamesForIntent(intent);
+            ArraySet<String> pkgNames = getPackageNamesForIntent(intent);
             for (Iterator<PackageParser.Package> it = pkgs.iterator(); it.hasNext();) {
                 PackageParser.Package pkg = it.next();
                 if (pkgNames.contains(pkg.packageName)) {
@@ -4562,7 +4560,7 @@
         }
     }
 
-    private void filterRecentlyUsedApps(HashSet<PackageParser.Package> pkgs) {
+    private void filterRecentlyUsedApps(ArraySet<PackageParser.Package> pkgs) {
         // Filter out packages that aren't recently used.
         //
         // The exception is first boot of a non-eng device (aka !mLazyDexOpt), which
@@ -4598,14 +4596,14 @@
         }
     }
 
-    private HashSet<String> getPackageNamesForIntent(Intent intent) {
+    private ArraySet<String> getPackageNamesForIntent(Intent intent) {
         List<ResolveInfo> ris = null;
         try {
             ris = AppGlobals.getPackageManager().queryIntentReceivers(
                     intent, null, 0, UserHandle.USER_OWNER);
         } catch (RemoteException e) {
         }
-        HashSet<String> pkgNames = new HashSet<String>();
+        ArraySet<String> pkgNames = new ArraySet<String>();
         if (ris != null) {
             for (ResolveInfo ri : ris) {
                 pkgNames.add(ri.activityInfo.packageName);
@@ -4683,8 +4681,8 @@
         }
     }
 
-    public HashSet<String> getPackagesThatNeedDexOpt() {
-        HashSet<String> pkgs = null;
+    public ArraySet<String> getPackagesThatNeedDexOpt() {
+        ArraySet<String> pkgs = null;
         synchronized (mPackages) {
             for (PackageParser.Package p : mPackages.values()) {
                 if (DEBUG_DEXOPT) {
@@ -4694,7 +4692,7 @@
                     continue;
                 }
                 if (pkgs == null) {
-                    pkgs = new HashSet<String>();
+                    pkgs = new ArraySet<String>();
                 }
                 pkgs.add(p.packageName);
             }
@@ -4707,7 +4705,7 @@
     }
 
     private void performDexOptLibsLI(ArrayList<String> libs, String[] instructionSets,
-             boolean forceDex, boolean defer, HashSet<String> done) {
+             boolean forceDex, boolean defer, ArraySet<String> done) {
         for (int i=0; i<libs.size(); i++) {
             PackageParser.Package libPkg;
             String libName;
@@ -4732,7 +4730,7 @@
     static final int DEX_OPT_FAILED = -1;
 
     private int performDexOptLI(PackageParser.Package pkg, String[] targetInstructionSets,
-            boolean forceDex, boolean defer, HashSet<String> done) {
+            boolean forceDex, boolean defer, ArraySet<String> done) {
         final String[] instructionSets = targetInstructionSets != null ?
                 targetInstructionSets : getAppDexInstructionSets(pkg.applicationInfo);
 
@@ -4810,7 +4808,7 @@
                     // our list of deferred dexopts.
                     if (defer && isDexOptNeeded != DexFile.UP_TO_DATE) {
                         if (mDeferredDexOpt == null) {
-                            mDeferredDexOpt = new HashSet<PackageParser.Package>();
+                            mDeferredDexOpt = new ArraySet<PackageParser.Package>();
                         }
                         mDeferredDexOpt.add(pkg);
                         return DEX_OPT_DEFERRED;
@@ -4907,7 +4905,7 @@
     }
 
     private static String[] getDexCodeInstructionSets(String[] instructionSets) {
-        HashSet<String> dexCodeInstructionSets = new HashSet<String>(instructionSets.length);
+        ArraySet<String> dexCodeInstructionSets = new ArraySet<String>(instructionSets.length);
         for (String instructionSet : instructionSets) {
             dexCodeInstructionSets.add(getDexCodeInstructionSet(instructionSet));
         }
@@ -4950,9 +4948,9 @@
 
     private int performDexOptLI(PackageParser.Package pkg, String[] instructionSets,
                                 boolean forceDex, boolean defer, boolean inclDependencies) {
-        HashSet<String> done;
+        ArraySet<String> done;
         if (inclDependencies && (pkg.usesLibraries != null || pkg.usesOptionalLibraries != null)) {
-            done = new HashSet<String>();
+            done = new ArraySet<String>();
             done.add(pkg.packageName);
         } else {
             done = null;
@@ -6137,7 +6135,7 @@
             r = null;
             for (i=0; i<N; i++) {
                 PackageParser.Permission p = pkg.permissions.get(i);
-                HashMap<String, BasePermission> permissionMap =
+                ArrayMap<String, BasePermission> permissionMap =
                         p.tree ? mSettings.mPermissionTrees
                         : mSettings.mPermissions;
                 p.group = mPermissionGroups.get(p.info.group);
@@ -6265,9 +6263,9 @@
                 if (pkg.mOverlayTarget != null && !pkg.mOverlayTarget.equals("android")) {
                     if (!mOverlays.containsKey(pkg.mOverlayTarget)) {
                         mOverlays.put(pkg.mOverlayTarget,
-                                new HashMap<String, PackageParser.Package>());
+                                new ArrayMap<String, PackageParser.Package>());
                     }
-                    HashMap<String, PackageParser.Package> map = mOverlays.get(pkg.mOverlayTarget);
+                    ArrayMap<String, PackageParser.Package> map = mOverlays.get(pkg.mOverlayTarget);
                     map.put(pkg.packageName, pkg);
                     PackageParser.Package orig = mPackages.get(pkg.mOverlayTarget);
                     if (orig != null && !createIdmapForPackagePairLI(orig, pkg)) {
@@ -6928,13 +6926,13 @@
             return;
         }
         final GrantedPermissions gp = ps.sharedUser != null ? ps.sharedUser : ps;
-        HashSet<String> origPermissions = gp.grantedPermissions;
+        ArraySet<String> origPermissions = gp.grantedPermissions;
         boolean changedPermission = false;
 
         if (replace) {
             ps.permissionsFixed = false;
             if (gp == ps) {
-                origPermissions = new HashSet<String>(gp.grantedPermissions);
+                origPermissions = new ArraySet<String>(gp.grantedPermissions);
                 gp.grantedPermissions.clear();
                 gp.gids = mGlobalGids;
             }
@@ -7081,7 +7079,7 @@
     }
 
     private boolean grantSignaturePermission(String perm, PackageParser.Package pkg,
-                                          BasePermission bp, HashSet<String> origPermissions) {
+                                          BasePermission bp, ArraySet<String> origPermissions) {
         boolean allowed;
         allowed = (compareSignatures(
                 bp.packageSetting.signatures.mSignatures, pkg.mSignatures)
@@ -7339,8 +7337,8 @@
 //        }
 
         // Keys are String (activity class name), values are Activity.
-        private final HashMap<ComponentName, PackageParser.Activity> mActivities
-                = new HashMap<ComponentName, PackageParser.Activity>();
+        private final ArrayMap<ComponentName, PackageParser.Activity> mActivities
+                = new ArrayMap<ComponentName, PackageParser.Activity>();
         private int mFlags;
     }
 
@@ -7538,8 +7536,8 @@
 //        }
 
         // Keys are String (activity class name), values are Activity.
-        private final HashMap<ComponentName, PackageParser.Service> mServices
-                = new HashMap<ComponentName, PackageParser.Service>();
+        private final ArrayMap<ComponentName, PackageParser.Service> mServices
+                = new ArrayMap<ComponentName, PackageParser.Service>();
         private int mFlags;
     };
 
@@ -7732,8 +7730,8 @@
             out.println(Integer.toHexString(System.identityHashCode(filter)));
         }
 
-        private final HashMap<ComponentName, PackageParser.Provider> mProviders
-                = new HashMap<ComponentName, PackageParser.Provider>();
+        private final ArrayMap<ComponentName, PackageParser.Provider> mProviders
+                = new ArrayMap<ComponentName, PackageParser.Provider>();
         private int mFlags;
     };
 
@@ -11835,8 +11833,8 @@
         synchronized (mPackages) {
             CrossProfileIntentResolver resolver =
                     mSettings.editCrossProfileIntentResolverLPw(sourceUserId);
-            HashSet<CrossProfileIntentFilter> set =
-                    new HashSet<CrossProfileIntentFilter>(resolver.filterSet());
+            ArraySet<CrossProfileIntentFilter> set =
+                    new ArraySet<CrossProfileIntentFilter>(resolver.filterSet());
             for (CrossProfileIntentFilter filter : set) {
                 if (filter.getOwnerPackage().equals(ownerPackage)
                         && filter.getOwnerUserId() == callingUserId) {
diff --git a/services/core/java/com/android/server/pm/PackageSettingBase.java b/services/core/java/com/android/server/pm/PackageSettingBase.java
index bf13fd9..1dcadb4 100644
--- a/services/core/java/com/android/server/pm/PackageSettingBase.java
+++ b/services/core/java/com/android/server/pm/PackageSettingBase.java
@@ -21,10 +21,10 @@
 import static android.content.pm.PackageManager.COMPONENT_ENABLED_STATE_ENABLED;
 
 import android.content.pm.PackageUserState;
+import android.util.ArraySet;
 import android.util.SparseArray;
 
 import java.io.File;
-import java.util.HashSet;
 
 /**
  * Settings base class for pending and resolved classes.
@@ -321,8 +321,8 @@
 
     void setUserState(int userId, int enabled, boolean installed, boolean stopped,
             boolean notLaunched, boolean hidden,
-            String lastDisableAppCaller, HashSet<String> enabledComponents,
-            HashSet<String> disabledComponents, boolean blockUninstall) {
+            String lastDisableAppCaller, ArraySet<String> enabledComponents,
+            ArraySet<String> disabledComponents, boolean blockUninstall) {
         PackageUserState state = modifyUserState(userId);
         state.enabled = enabled;
         state.installed = installed;
@@ -335,39 +335,39 @@
         state.blockUninstall = blockUninstall;
     }
 
-    HashSet<String> getEnabledComponents(int userId) {
+    ArraySet<String> getEnabledComponents(int userId) {
         return readUserState(userId).enabledComponents;
     }
 
-    HashSet<String> getDisabledComponents(int userId) {
+    ArraySet<String> getDisabledComponents(int userId) {
         return readUserState(userId).disabledComponents;
     }
 
-    void setEnabledComponents(HashSet<String> components, int userId) {
+    void setEnabledComponents(ArraySet<String> components, int userId) {
         modifyUserState(userId).enabledComponents = components;
     }
 
-    void setDisabledComponents(HashSet<String> components, int userId) {
+    void setDisabledComponents(ArraySet<String> components, int userId) {
         modifyUserState(userId).disabledComponents = components;
     }
 
-    void setEnabledComponentsCopy(HashSet<String> components, int userId) {
+    void setEnabledComponentsCopy(ArraySet<String> components, int userId) {
         modifyUserState(userId).enabledComponents = components != null
-                ? new HashSet<String>(components) : null;
+                ? new ArraySet<String>(components) : null;
     }
 
-    void setDisabledComponentsCopy(HashSet<String> components, int userId) {
+    void setDisabledComponentsCopy(ArraySet<String> components, int userId) {
         modifyUserState(userId).disabledComponents = components != null
-                ? new HashSet<String>(components) : null;
+                ? new ArraySet<String>(components) : null;
     }
 
     PackageUserState modifyUserStateComponents(int userId, boolean disabled, boolean enabled) {
         PackageUserState state = modifyUserState(userId);
         if (disabled && state.disabledComponents == null) {
-            state.disabledComponents = new HashSet<String>(1);
+            state.disabledComponents = new ArraySet<String>(1);
         }
         if (enabled && state.enabledComponents == null) {
-            state.enabledComponents = new HashSet<String>(1);
+            state.enabledComponents = new ArraySet<String>(1);
         }
         return state;
     }
diff --git a/services/core/java/com/android/server/pm/Settings.java b/services/core/java/com/android/server/pm/Settings.java
index 7de56c8..200eb5f 100644
--- a/services/core/java/com/android/server/pm/Settings.java
+++ b/services/core/java/com/android/server/pm/Settings.java
@@ -63,6 +63,8 @@
 import android.content.pm.UserInfo;
 import android.content.pm.PackageUserState;
 import android.content.pm.VerifierDeviceIdentity;
+import android.util.ArrayMap;
+import android.util.ArraySet;
 import android.util.Log;
 import android.util.Slog;
 import android.util.SparseArray;
@@ -78,8 +80,6 @@
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Date;
-import java.util.HashMap;
-import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
@@ -159,11 +159,11 @@
     private final File mStoppedPackagesFilename;
     private final File mBackupStoppedPackagesFilename;
 
-    final HashMap<String, PackageSetting> mPackages =
-            new HashMap<String, PackageSetting>();
+    final ArrayMap<String, PackageSetting> mPackages =
+            new ArrayMap<String, PackageSetting>();
     // List of replaced system applications
-    private final HashMap<String, PackageSetting> mDisabledSysPackages =
-        new HashMap<String, PackageSetting>();
+    private final ArrayMap<String, PackageSetting> mDisabledSysPackages =
+        new ArrayMap<String, PackageSetting>();
 
     private static int mFirstAvailableUid = 0;
 
@@ -206,8 +206,8 @@
     final SparseArray<CrossProfileIntentResolver> mCrossProfileIntentResolvers =
             new SparseArray<CrossProfileIntentResolver>();
 
-    final HashMap<String, SharedUserSetting> mSharedUsers =
-            new HashMap<String, SharedUserSetting>();
+    final ArrayMap<String, SharedUserSetting> mSharedUsers =
+            new ArrayMap<String, SharedUserSetting>();
     private final ArrayList<Object> mUserIds = new ArrayList<Object>();
     private final SparseArray<Object> mOtherUserIds =
             new SparseArray<Object>();
@@ -217,12 +217,12 @@
             new ArrayList<Signature>();
 
     // Mapping from permission names to info about them.
-    final HashMap<String, BasePermission> mPermissions =
-            new HashMap<String, BasePermission>();
+    final ArrayMap<String, BasePermission> mPermissions =
+            new ArrayMap<String, BasePermission>();
 
     // Mapping from permission tree names to info about them.
-    final HashMap<String, BasePermission> mPermissionTrees =
-            new HashMap<String, BasePermission>();
+    final ArrayMap<String, BasePermission> mPermissionTrees =
+            new ArrayMap<String, BasePermission>();
 
     // Packages that have been uninstalled and still need their external
     // storage data deleted.
@@ -232,7 +232,7 @@
     // Keys are the new names of the packages, values are the original
     // names.  The packages appear everwhere else under their original
     // names.
-    final HashMap<String, String> mRenamedPackages = new HashMap<String, String>();
+    final ArrayMap<String, String> mRenamedPackages = new ArrayMap<String, String>();
     
     final StringBuilder mReadMessages = new StringBuilder();
 
@@ -437,7 +437,7 @@
     void transferPermissionsLPw(String origPkg, String newPkg) {
         // Transfer ownership of permissions to the new package.
         for (int i=0; i<2; i++) {
-            HashMap<String, BasePermission> permissions =
+            ArrayMap<String, BasePermission> permissions =
                     i == 0 ? mPermissionTrees : mPermissions;
             for (BasePermission bp : permissions.values()) {
                 if (origPkg.equals(bp.sourcePackage)) {
@@ -582,7 +582,7 @@
                         }
                         p.appId = dis.appId;
                         // Clone permissions
-                        p.grantedPermissions = new HashSet<String>(dis.grantedPermissions);
+                        p.grantedPermissions = new ArraySet<String>(dis.grantedPermissions);
                         // Clone component info
                         List<UserInfo> users = getAllUsers();
                         if (users != null) {
@@ -1138,8 +1138,8 @@
                     final boolean blockUninstall = blockUninstallStr == null
                             ? false : Boolean.parseBoolean(blockUninstallStr);
 
-                    HashSet<String> enabledComponents = null;
-                    HashSet<String> disabledComponents = null;
+                    ArraySet<String> enabledComponents = null;
+                    ArraySet<String> disabledComponents = null;
 
                     int packageDepth = parser.getDepth();
                     while ((type=parser.next()) != XmlPullParser.END_DOCUMENT
@@ -1189,9 +1189,9 @@
         }
     }
 
-    private HashSet<String> readComponentsLPr(XmlPullParser parser)
+    private ArraySet<String> readComponentsLPr(XmlPullParser parser)
             throws IOException, XmlPullParserException {
-        HashSet<String> components = null;
+        ArraySet<String> components = null;
         int type;
         int outerDepth = parser.getDepth();
         String tagName;
@@ -1207,7 +1207,7 @@
                 String componentName = parser.getAttributeValue(null, ATTR_NAME);
                 if (componentName != null) {
                     if (components == null) {
-                        components = new HashSet<String>();
+                        components = new ArraySet<String>();
                     }
                     components.add(componentName);
                 }
@@ -1921,7 +1921,7 @@
     }
 
     ArrayList<PackageSetting> getListOfIncompleteInstallPackagesLPr() {
-        final HashSet<String> kList = new HashSet<String>(mPackages.keySet());
+        final ArraySet<String> kList = new ArraySet<String>(mPackages.keySet());
         final Iterator<String> its = kList.iterator();
         final ArrayList<PackageSetting> ret = new ArrayList<PackageSetting>();
         while (its.hasNext()) {
@@ -2511,7 +2511,7 @@
         return defValue;
     }
 
-    private void readPermissionsLPw(HashMap<String, BasePermission> out, XmlPullParser parser)
+    private void readPermissionsLPw(ArrayMap<String, BasePermission> out, XmlPullParser parser)
             throws IOException, XmlPullParserException {
         int outerDepth = parser.getDepth();
         int type;
@@ -3016,7 +3016,7 @@
         }
     }
 
-    private void readGrantedPermissionsLPw(XmlPullParser parser, HashSet<String> outPerms)
+    private void readGrantedPermissionsLPw(XmlPullParser parser, ArraySet<String> outPerms)
             throws IOException, XmlPullParserException {
         int outerDepth = parser.getDepth();
         int type;
@@ -3090,8 +3090,8 @@
                 int sourceUserId = mCrossProfileIntentResolvers.keyAt(i);
                 CrossProfileIntentResolver cpir = mCrossProfileIntentResolvers.get(sourceUserId);
                 boolean needsWriting = false;
-                HashSet<CrossProfileIntentFilter> cpifs =
-                        new HashSet<CrossProfileIntentFilter>(cpir.filterSet());
+                ArraySet<CrossProfileIntentFilter> cpifs =
+                        new ArraySet<CrossProfileIntentFilter>(cpir.filterSet());
                 for (CrossProfileIntentFilter cpif : cpifs) {
                     if (cpif.getTargetUserId() == userId) {
                         needsWriting = true;
@@ -3147,7 +3147,7 @@
         return ps;
     }
 
-    private String compToString(HashSet<String> cmp) {
+    private String compToString(ArraySet<String> cmp) {
         return cmp != null ? Arrays.toString(cmp.toArray()) : "[]";
     }
  
@@ -3477,7 +3477,7 @@
                 pw.print(prefix); pw.print("    lastDisabledCaller: ");
                         pw.println(lastDisabledAppCaller);
             }
-            HashSet<String> cmp = ps.getDisabledComponents(user.id);
+            ArraySet<String> cmp = ps.getDisabledComponents(user.id);
             if (cmp != null && cmp.size() > 0) {
                 pw.print(prefix); pw.println("    disabledComponents:");
                 for (String s : cmp) {
diff --git a/services/core/java/com/android/server/pm/SharedUserSetting.java b/services/core/java/com/android/server/pm/SharedUserSetting.java
index ca1eeea..2b406f7 100644
--- a/services/core/java/com/android/server/pm/SharedUserSetting.java
+++ b/services/core/java/com/android/server/pm/SharedUserSetting.java
@@ -16,7 +16,7 @@
 
 package com.android.server.pm;
 
-import java.util.HashSet;
+import android.util.ArraySet;
 
 /**
  * Settings data for a particular shared user ID we know about.
@@ -29,7 +29,7 @@
     // flags that are associated with this uid, regardless of any package flags
     int uidFlags;
 
-    final HashSet<PackageSetting> packages = new HashSet<PackageSetting>();
+    final ArraySet<PackageSetting> packages = new ArraySet<PackageSetting>();
 
     final PackageSignatures signatures = new PackageSignatures();