New ArrayMap class.

This is a new kind of key/value mapping that stores its data
as an array, so it doesn't need to create an extra Entry object
for every mapping placed in to it.  It is also optimized to reduce
memory overhead in other ways, by keeping the base object small,
being fairly aggressive about keeping the array data structures
small, etc.

There are some unit and performance tests dropped in to some
random places; they will need to be put somewhere else once I
decided what we are going to do with this for the next release
(for example if we make it public the unit tests should go in
to CTS).

Switch IntentResolver to using ArrayMap instead of HashMap.

Also get rid of a bunch of duplicate implementations of binarySearch,
and add an optimization to the various sparse arrays where you can
supply an explicit 0 capacity to prevent it from doing an initial
array allocation; use this new optimization in a few places where it
makes sense.

Change-Id: I01ef2764680f8ae49938e2a2ed40dc01606a056b

21 files changed, 1758 insertions, 924 deletions

diff --git a/core/java/android/app/LoaderManager.java b/core/java/android/app/LoaderManager.java
index 267555a70921..b13b24a1ca0c 100644
--- a/core/java/android/app/LoaderManager.java
+++ b/core/java/android/app/LoaderManager.java
@@ -204,13 +204,13 @@ class LoaderManagerImpl extends LoaderManager {
     // These are the currently active loaders.  A loader is here
     // from the time its load is started until it has been explicitly
     // stopped or restarted by the application.
-    final SparseArray<LoaderInfo> mLoaders = new SparseArray<LoaderInfo>();
+    final SparseArray<LoaderInfo> mLoaders = new SparseArray<LoaderInfo>(0);
 
     // These are previously run loaders.  This list is maintained internally
     // to avoid destroying a loader while an application is still using it.
     // It allows an application to restart a loader, but continue using its
     // previously run loader until the new loader's data is available.
-    final SparseArray<LoaderInfo> mInactiveLoaders = new SparseArray<LoaderInfo>();
+    final SparseArray<LoaderInfo> mInactiveLoaders = new SparseArray<LoaderInfo>(0);
 
     final String mWho;
 
diff --git a/core/java/android/content/pm/RegisteredServicesCache.java b/core/java/android/content/pm/RegisteredServicesCache.java
index 288d55f577f6..875e8de2daed 100644
--- a/core/java/android/content/pm/RegisteredServicesCache.java
+++ b/core/java/android/content/pm/RegisteredServicesCache.java
@@ -82,7 +82,7 @@ public abstract class RegisteredServicesCache<V> {
     @GuardedBy("mServicesLock")
     private boolean mPersistentServicesFileDidNotExist;
     @GuardedBy("mServicesLock")
-    private final SparseArray<UserServices<V>> mUserServices = new SparseArray<UserServices<V>>();
+    private final SparseArray<UserServices<V>> mUserServices = new SparseArray<UserServices<V>>(2);
 
     private static class UserServices<V> {
         @GuardedBy("mServicesLock")
diff --git a/core/java/android/content/res/Resources.java b/core/java/android/content/res/Resources.java
index c7976c3c6723..cff974d01792 100644
--- a/core/java/android/content/res/Resources.java
+++ b/core/java/android/content/res/Resources.java
@@ -99,11 +99,11 @@ public class Resources {
     /*package*/ final Configuration mTmpConfig = new Configuration();
     /*package*/ TypedValue mTmpValue = new TypedValue();
     /*package*/ final LongSparseArray<WeakReference<Drawable.ConstantState> > mDrawableCache
-            = new LongSparseArray<WeakReference<Drawable.ConstantState> >();
+            = new LongSparseArray<WeakReference<Drawable.ConstantState> >(0);
     /*package*/ final LongSparseArray<WeakReference<ColorStateList> > mColorStateListCache
-            = new LongSparseArray<WeakReference<ColorStateList> >();
+            = new LongSparseArray<WeakReference<ColorStateList> >(0);
     /*package*/ final LongSparseArray<WeakReference<Drawable.ConstantState> > mColorDrawableCache
-            = new LongSparseArray<WeakReference<Drawable.ConstantState> >();
+            = new LongSparseArray<WeakReference<Drawable.ConstantState> >(0);
     /*package*/ boolean mPreloading;
 
     /*package*/ TypedArray mCachedStyledAttributes = null;
diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java
new file mode 100644
index 000000000000..70f7d2edecc9
--- /dev/null
+++ b/core/java/android/util/ArrayMap.java
@@ -0,0 +1,615 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.util;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * ArrayMap is a generic key->value mapping data structure that is
+ * designed to be more memory efficient than a traditional {@link java.util.HashMap}.
+ * It keeps its mappings in an array data structure -- an integer array of hash
+ * codes for each item, and an Object array of the key/value pairs.  This allows it to
+ * avoid having to create an extra object for every entry put in to the map, and it
+ * also tries to control the growth of the size of these arrays more aggressively
+ * (since growing them only requires copying the entries in the array, not rebuilding
+ * a hash map).
+ *
+ * <p>Note that this implementation is not intended to be appropriate for data structures
+ * that may contain large numbers of items.  It is generally slower than a traditional
+ * HashMap, since lookups require a binary search and adds and removes require inserting
+ * and deleting entries in the array.  For containers holding up to hundreds of items,
+ * the performance difference is not significant, less than 50%.  For larger numbers of items
+ * this data structure should be avoided.</p>
+ *
+ * <p><b>Note:</b> unlike {@link java.util.HashMap}, this container does not support
+ * null keys.</p>
+ *
+ * <p>Because this container is intended to better balance memory use, unlike most other
+ * standard Java containers it will shrink its array as items are removed from it.  Currently
+ * you have no control over this shrinking -- if you set a capacity and then remove an
+ * item, it may reduce the capacity to better match the current size.  In the future an
+ * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p>
+ *
+ * @hide
+ */
+public final class ArrayMap<K, V> implements Map<K, V> {
+    private static final boolean DEBUG = false;
+    private static final String TAG = "ArrayMap";
+
+    /**
+     * The minimum amount by which the capacity of a ArrayMap will increase.
+     * This is tuned to be relatively space-efficient.
+     */
+    private static final int BASE_SIZE = 4;
+
+    /**
+     * Maximum number of entries to have in array caches.
+     */
+    private static final int CACHE_SIZE = 10;
+
+    /**
+     * Caches of small array objects to avoid spamming garbage.  The cache
+     * Object[] variable is a pointer to a linked list of array objects.
+     * The first entry in the array is a pointer to the next array in the
+     * list; the second entry is a pointer to the int[] hash code array for it.
+     */
+    static Object[] mBaseCache;
+    static int mBaseCacheSize;
+    static Object[] mTwiceBaseCache;
+    static int mTwiceBaseCacheSize;
+
+    int[] mHashes;
+    Object[] mArray;
+    int mSize;
+    MapCollections<K, V> mCollections;
+
+    private int indexOf(Object key, int hash) {
+        final int N = mSize;
+
+        // Important fast case: if nothing is in here, nothing to look for.
+        if (N == 0) {
+            return ~0;
+        }
+
+        int index = SparseArray.binarySearch(mHashes, N, hash);
+
+        // If the hash code wasn't found, then we have no entry for this key.
+        if (index < 0) {
+            return index;
+        }
+
+        // If the key at the returned index matches, that's what we want.
+        if (mArray[index<<1].equals(key)) {
+            return index;
+        }
+
+        // Search for a matching key after the index.
+        int end;
+        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
+            if (mArray[end << 1].equals(key)) return end;
+        }
+
+        // Search for a matching key before the index.
+        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
+            if (mArray[i << 1].equals(key)) return i;
+        }
+
+        // Key not found -- return negative value indicating where a
+        // new entry for this key should go.  We use the end of the
+        // hash chain to reduce the number of array entries that will
+        // need to be copied when inserting.
+        return ~end;
+    }
+
+    private void allocArrays(final int size) {
+        if (size == (BASE_SIZE*2)) {
+            synchronized (ArrayMap.class) {
+                if (mTwiceBaseCache != null) {
+                    final Object[] array = mTwiceBaseCache;
+                    mArray = array;
+                    mTwiceBaseCache = (Object[])array[0];
+                    mHashes = (int[])array[1];
+                    array[0] = array[1] = null;
+                    mTwiceBaseCacheSize--;
+                    if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
+                            + " now have " + mTwiceBaseCacheSize + " entries");
+                    return;
+                }
+            }
+        } else if (size == BASE_SIZE) {
+            synchronized (ArrayMap.class) {
+                if (mBaseCache != null) {
+                    final Object[] array = mBaseCache;
+                    mArray = array;
+                    mBaseCache = (Object[])array[0];
+                    mHashes = (int[])array[1];
+                    array[0] = array[1] = null;
+                    mBaseCacheSize--;
+                    if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
+                            + " now have " + mBaseCacheSize + " entries");
+                    return;
+                }
+            }
+        }
+
+        mHashes = new int[size];
+        mArray = new Object[size<<1];
+    }
+
+    private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
+        if (hashes.length == (BASE_SIZE*2)) {
+            synchronized (ArrayMap.class) {
+                if (mTwiceBaseCacheSize < CACHE_SIZE) {
+                    array[0] = mTwiceBaseCache;
+                    array[1] = hashes;
+                    for (int i=(size<<1)-1; i>=2; i--) {
+                        array[i] = null;
+                    }
+                    mTwiceBaseCache = array;
+                    mTwiceBaseCacheSize++;
+                    if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
+                            + " now have " + mTwiceBaseCacheSize + " entries");
+                }
+            }
+        } else if (hashes.length == BASE_SIZE) {
+            synchronized (ArrayMap.class) {
+                if (mBaseCacheSize < CACHE_SIZE) {
+                    array[0] = mBaseCache;
+                    array[1] = hashes;
+                    for (int i=(size<<1)-1; i>=2; i--) {
+                        array[i] = null;
+                    }
+                    mBaseCache = array;
+                    mBaseCacheSize++;
+                    if (DEBUG) Log.d(TAG, "Storing 1x cache " + array
+                            + " now have " + mBaseCacheSize + " entries");
+                }
+            }
+        }
+    }
+
+    /**
+     * Create a new empty ArrayMap.  The default capacity of an array map is 0, and
+     * will grow once items are added to it.
+     */
+    public ArrayMap() {
+        mHashes = SparseArray.EMPTY_INTS;
+        mArray = SparseArray.EMPTY_OBJECTS;
+        mSize = 0;
+    }
+
+    /**
+     * Create a new ArrayMap with a given initial capacity.
+     */
+    public ArrayMap(int capacity) {
+        if (capacity == 0) {
+            mHashes = SparseArray.EMPTY_INTS;
+            mArray = SparseArray.EMPTY_OBJECTS;
+        } else {
+            allocArrays(capacity);
+        }
+        mSize = 0;
+    }
+
+    /**
+     * Make the array map empty.  All storage is released.
+     */
+    @Override
+    public void clear() {
+        freeArrays(mHashes, mArray, mSize);
+        mHashes = SparseArray.EMPTY_INTS;
+        mArray = SparseArray.EMPTY_OBJECTS;
+        mSize = 0;
+    }
+
+    /**
+     * Ensure the array map can hold at least <var>minimumCapacity</var>
+     * items.
+     */
+    public void ensureCapacity(int minimumCapacity) {
+        if (mHashes.length < minimumCapacity) {
+            int[] ohashes = mHashes;
+            Object[] oarray = mArray;
+            allocArrays(minimumCapacity);
+            if (mHashes.length > 0) {
+                System.arraycopy(ohashes, 0, mHashes, 0, mHashes.length);
+                System.arraycopy(oarray, 0, mArray, 0, mArray.length);
+            }
+            freeArrays(ohashes, oarray, mSize);
+        }
+    }
+
+    /**
+     * Check whether a key exists in the array.
+     *
+     * @param key The key to search for.
+     * @return Returns true if the key exists, else false.
+     */
+    @Override
+    public boolean containsKey(Object key) {
+        return indexOf(key, key.hashCode()) >= 0;
+    }
+
+    private int indexOfValue(Object value) {
+        final int N = mSize*2;
+        final Object[] array = mArray;
+        if (value == null) {
+            for (int i=1; i<N; i+=2) {
+                if (array[i] == null) {
+                    return i>>1;
+                }
+            }
+        } else {
+            for (int i=1; i<N; i+=2) {
+                if (value.equals(array[i])) {
+                    return i>>1;
+                }
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * Check whether a value exists in the array.  This requires a linear search
+     * through the entire array.
+     *
+     * @param value The value to search for.
+     * @return Returns true if the value exists, else false.
+     */
+    @Override
+    public boolean containsValue(Object value) {
+        return indexOfValue(value) >= 0;
+    }
+
+    /**
+     * Retrieve a value from the array.
+     * @param key The key of the value to retrieve.
+     * @return Returns the value associated with the given key,
+     * or null if there is no such key.
+     */
+    @Override
+    public V get(Object key) {
+        final int index = indexOf(key, key.hashCode());
+        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
+    }
+
+    /**
+     * Return the key at the given index in the array.
+     * @param index The desired index, must be between 0 and {@link #size()}-1.
+     * @return Returns the key stored at the given index.
+     */
+    public K keyAt(int index) {
+        return (K)mArray[index << 1];
+    }
+
+    /**
+     * Return the value at the given index in the array.
+     * @param index The desired index, must be between 0 and {@link #size()}-1.
+     * @return Returns the value stored at the given index.
+     */
+    public V valueAt(int index) {
+        return (V)mArray[(index << 1) + 1];
+    }
+
+    /**
+     * Set the value at a given index in the array.
+     * @param index The desired index, must be between 0 and {@link #size()}-1.
+     * @param value The new value to store at this index.
+     * @return Returns the previous value at the given index.
+     */
+    public V setValueAt(int index, V value) {
+        index = (index << 1) + 1;
+        V old = (V)mArray[index];
+        mArray[index] = value;
+        return old;
+    }
+
+    /**
+     * Return true if the array map contains no items.
+     */
+    @Override
+    public boolean isEmpty() {
+        return mSize <= 0;
+    }
+
+    /**
+     * Add a new value to the array map.
+     * @param key The key under which to store the value.  <b>Must not be null.</b>  If
+     * this key already exists in the array, its value will be replaced.
+     * @param value The value to store for the given key.
+     * @return Returns the old value that was stored for the given key, or null if there
+     * was no such key.
+     */
+    @Override
+    public V put(K key, V value) {
+        final int hash = key.hashCode();
+        int index = indexOf(key, hash);
+        if (index >= 0) {
+            index = (index<<1) + 1;
+            final V old = (V)mArray[index];
+            mArray[index] = value;
+            return old;
+        }
+
+        index = ~index;
+        if (mSize >= mHashes.length) {
+            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
+                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
+
+            if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
+
+            final int[] ohashes = mHashes;
+            final Object[] oarray = mArray;
+            allocArrays(n);
+
+            if (mHashes.length > 0) {
+                if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
+                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
+                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
+            }
+
+            freeArrays(ohashes, oarray, mSize);
+        }
+
+        if (index < mSize) {
+            if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index)
+                    + " to " + (index+1));
+            System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
+            System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
+        }
+
+        mHashes[index] = hash;
+        mArray[index<<1] = key;
+        mArray[(index<<1)+1] = value;
+        mSize++;
+        return null;
+    }
+
+    /**
+     * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var>
+     * @param array The array whose contents are to be retrieved.
+     */
+    public void putAll(ArrayMap<? extends K, ? extends V> array) {
+        final int N = array.mSize;
+        ensureCapacity(mSize + N);
+        for (int i=0; i<N; i++) {
+            put(array.keyAt(i), array.valueAt(i));
+        }
+    }
+
+    /**
+     * Remove an existing key from the array map.
+     * @param key The key of the mapping to remove.
+     * @return Returns the value that was stored under the key, or null if there
+     * was no such key.
+     */
+    @Override
+    public V remove(Object key) {
+        int index = indexOf(key, key.hashCode());
+        if (index >= 0) {
+            return removeAt(index);
+        }
+
+        return null;
+    }
+
+    /**
+     * Remove the key/value mapping at the given index.
+     * @param index The desired index, must be between 0 and {@link #size()}-1.
+     * @return Returns the value that was stored at this index.
+     */
+    public V removeAt(int index) {
+        final V old = (V)mArray[(index << 1) + 1];
+        if (mSize <= 1) {
+            // Now empty.
+            if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
+            freeArrays(mHashes, mArray, mSize);
+            mHashes = SparseArray.EMPTY_INTS;
+            mArray = SparseArray.EMPTY_OBJECTS;
+            mSize = 0;
+        } else {
+            if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
+                // Shrunk enough to reduce size of arrays.  We don't allow it to
+                // shrink smaller than (BASE_SIZE*2) to avoid flapping between
+                // that and BASE_SIZE.
+                final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
+
+                if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);
+
+                final int[] ohashes = mHashes;
+                final Object[] oarray = mArray;
+                allocArrays(n);
+
+                mSize--;
+                if (index > 0) {
+                    if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
+                    System.arraycopy(ohashes, 0, mHashes, 0, index);
+                    System.arraycopy(oarray, 0, mArray, 0, index << 1);
+                }
+                if (index < mSize) {
+                    if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize
+                            + " to " + index);
+                    System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
+                    System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
+                            (mSize - index) << 1);
+                }
+            } else {
+                mSize--;
+                if (index < mSize) {
+                    if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize
+                            + " to " + index);
+                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
+                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
+                            (mSize - index) << 1);
+                }
+                mArray[mSize << 1] = null;
+                mArray[(mSize << 1) + 1] = null;
+            }
+        }
+        return old;
+    }
+
+    /**
+     * Return the number of items in this array map.
+     */
+    @Override
+    public int size() {
+        return mSize;
+    }
+
+    // ------------------------------------------------------------------------
+    // Interop with traditional Java containers.  Not as efficient as using
+    // specialized collection APIs.
+    // ------------------------------------------------------------------------
+
+    private MapCollections<K, V> getCollection() {
+        if (mCollections == null) {
+            mCollections = new MapCollections<K, V>() {
+                @Override
+                protected int colGetSize() {
+                    return mSize;
+                }
+
+                @Override
+                protected Object colGetEntry(int index, int offset) {
+                    return mArray[(index<<1) + offset];
+                }
+
+                @Override
+                protected int colIndexOfKey(Object key) {
+                    return indexOf(key, key.hashCode());
+                }
+
+                @Override
+                protected int colIndexOfValue(Object value) {
+                    return indexOfValue(value);
+                }
+
+                @Override
+                protected Map<K, V> colGetMap() {
+                    return ArrayMap.this;
+                }
+
+                @Override
+                protected void colPut(K key, V value) {
+                    put(key, value);
+                }
+
+                @Override
+                protected V colSetValue(int index, V value) {
+                    return setValueAt(index, value);
+                }
+
+                @Override
+                protected void colRemoveAt(int index) {
+                    removeAt(index);
+                }
+
+                @Override
+                protected void colClear() {
+                    clear();
+                }
+            };
+        }
+        return mCollections;
+    }
+
+    /**
+     * Determine if the array map contains all of the keys in the given collection.
+     * @param collection The collection whose contents are to be checked against.
+     * @return Returns true if this array map contains a key for every entry
+     * in <var>collection</var>, else returns false.
+     */
+    public boolean containsAll(Collection<?> collection) {
+        return MapCollections.containsAllHelper(this, collection);
+    }
+
+    /**
+     * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var>
+     * @param map The map whose contents are to be retrieved.
+     */
+    @Override
+    public void putAll(Map<? extends K, ? extends V> map) {
+        ensureCapacity(mSize + map.size());
+        for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
+            put(entry.getKey(), entry.getValue());
+        }
+    }
+
+    /**
+     * Remove all keys in the array map that exist in the given collection.
+     * @param collection The collection whose contents are to be used to remove keys.
+     * @return Returns true if any keys were removed from the array map, else false.
+     */
+    public boolean removeAll(Collection<?> collection) {
+        return MapCollections.removeAllHelper(this, collection);
+    }
+
+    /**
+     * Remove all keys in the array map that do <b>not</b> exist in the given collection.
+     * @param collection The collection whose contents are to be used to determine which
+     * keys to keep.
+     * @return Returns true if any keys were removed from the array map, else false.
+     */
+    public boolean retainAll(Collection<?> collection) {
+        return MapCollections.retainAllHelper(this, collection);
+    }
+
+    /**
+     * Return a {@link java.util.Set} for iterating over and interacting with all mappings
+     * in the array map.
+     *
+     * <p><b>Note:</b> this is a very inefficient way to access the array contents, it
+     * requires generating a number of temporary objects.</p>
+     *
+     * <p><b>Note:</b></p> the semantics of this
+     * Set are subtly different than that of a {@link java.util.HashMap}: most important,
+     * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single
+     * object that exists for the entire iterator, so you can <b>not</b> hold on to it
+     * after calling {@link java.util.Iterator#next() Iterator.next}.</p>
+     */
+    @Override
+    public Set<Map.Entry<K, V>> entrySet() {
+        return getCollection().getEntrySet();
+    }
+
+    /**
+     * Return a {@link java.util.Set} for iterating over and interacting with all keys
+     * in the array map.
+     *
+     * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it
+     * requires generating a number of temporary objects.</p>
+     */
+    @Override
+    public Set<K> keySet() {
+        return getCollection().getKeySet();
+    }
+
+    /**
+     * Return a {@link java.util.Collection} for iterating over and interacting with all values
+     * in the array map.
+     *
+     * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it
+     * requires generating a number of temporary objects.</p>
+     */
+    @Override
+    public Collection<V> values() {
+        return getCollection().getValues();
+    }
+}
diff --git a/core/java/android/util/LongSparseArray.java b/core/java/android/util/LongSparseArray.java
index 630e5f37d8a0..660b743a14e6 100644
--- a/core/java/android/util/LongSparseArray.java
+++ b/core/java/android/util/LongSparseArray.java
@@ -41,13 +41,19 @@ public class LongSparseArray<E> implements Cloneable {
     /**
      * Creates a new LongSparseArray containing no mappings that will not
      * require any additional memory allocation to store the specified
-     * number of mappings.
+     * number of mappings.  If you supply an initial capacity of 0, the
+     * sparse array will be initialized with a light-weight representation
+     * not requiring any additional array allocations.
      */
     public LongSparseArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-
-        mKeys = new long[initialCapacity];
-        mValues = new Object[initialCapacity];
+        if (initialCapacity == 0) {
+            mKeys = SparseLongArray.EMPTY_LONGS;
+            mValues = SparseArray.EMPTY_OBJECTS;
+        } else {
+            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
+            mKeys = new long[initialCapacity];
+            mValues = new Object[initialCapacity];
+        }
         mSize = 0;
     }
 
diff --git a/core/java/android/util/LongSparseLongArray.java b/core/java/android/util/LongSparseLongArray.java
index 34b61264d653..503295c52bea 100644
--- a/core/java/android/util/LongSparseLongArray.java
+++ b/core/java/android/util/LongSparseLongArray.java
@@ -42,13 +42,19 @@ public class LongSparseLongArray implements Cloneable {
     /**
      * Creates a new SparseLongArray containing no mappings that will not
      * require any additional memory allocation to store the specified
-     * number of mappings.
+     * number of mappings.  If you supply an initial capacity of 0, the
+     * sparse array will be initialized with a light-weight representation
+     * not requiring any additional array allocations.
      */
     public LongSparseLongArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-
-        mKeys = new long[initialCapacity];
-        mValues = new long[initialCapacity];
+        if (initialCapacity == 0) {
+            mKeys = SparseLongArray.EMPTY_LONGS;
+            mValues = SparseLongArray.EMPTY_LONGS;
+        } else {
+            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
+            mKeys = new long[initialCapacity];
+            mValues = new long[initialCapacity];
+        }
         mSize = 0;
     }
 
diff --git a/core/java/android/util/MapCollections.java b/core/java/android/util/MapCollections.java
new file mode 100644
index 000000000000..f29fb65c6ce4
--- /dev/null
+++ b/core/java/android/util/MapCollections.java
@@ -0,0 +1,496 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.util;
+
+import libcore.util.Objects;
+
+import java.lang.reflect.Array;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Helper for writing standard Java collection interfaces to a data
+ * structure like {@link ArrayMap}.
+ * @hide
+ */
+abstract class MapCollections<K, V> {
+    EntrySet mEntrySet;
+    KeySet mKeySet;
+    ValuesCollection mValues;
+
+    final class ArrayIterator<T> implements Iterator<T> {
+        final int mOffset;
+        int mSize;
+        int mIndex;
+        boolean mCanRemove = false;
+
+        ArrayIterator(int offset) {
+            mOffset = offset;
+            mSize = colGetSize();
+        }
+
+        @Override
+        public boolean hasNext() {
+            return mIndex < mSize;
+        }
+
+        @Override
+        public T next() {
+            Object res = colGetEntry(mIndex, mOffset);
+            mIndex++;
+            mCanRemove = true;
+            return (T)res;
+        }
+
+        @Override
+        public void remove() {
+            if (!mCanRemove) {
+                throw new IllegalStateException();
+            }
+            mIndex--;
+            mSize--;
+            mCanRemove = false;
+            colRemoveAt(mIndex);
+        }
+    }
+
+    final class MapIterator implements Iterator<Map.Entry<K, V>>, Map.Entry<K, V> {
+        int mEnd;
+        int mIndex;
+        boolean mEntryValid = false;
+
+        MapIterator() {
+            mEnd = colGetSize() - 1;
+            mIndex = -1;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return mIndex < mEnd;
+        }
+
+        @Override
+        public Map.Entry<K, V> next() {
+            mIndex++;
+            mEntryValid = true;
+            return this;
+        }
+
+        @Override
+        public void remove() {
+            if (!mEntryValid) {
+                throw new IllegalStateException();
+            }
+            mIndex--;
+            mEnd--;
+            mEntryValid = false;
+            colRemoveAt(mIndex);
+        }
+
+        @Override
+        public K getKey() {
+            if (!mEntryValid) {
+                throw new IllegalStateException(
+                        "This container does not support retaining Map.Entry objects");
+            }
+            return (K)colGetEntry(mIndex, 0);
+        }
+
+        @Override
+        public V getValue() {
+            if (!mEntryValid) {
+                throw new IllegalStateException(
+                        "This container does not support retaining Map.Entry objects");
+            }
+            return (V)colGetEntry(mIndex, 1);
+        }
+
+        @Override
+        public V setValue(V object) {
+            if (!mEntryValid) {
+                throw new IllegalStateException(
+                        "This container does not support retaining Map.Entry objects");
+            }
+            return colSetValue(mIndex, object);
+        }
+
+        @Override
+        public final boolean equals(Object o) {
+            if (!mEntryValid) {
+                throw new IllegalStateException(
+                        "This container does not support retaining Map.Entry objects");
+            }
+            if (!(o instanceof Map.Entry)) {
+                return false;
+            }
+            Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
+            return Objects.equal(e.getKey(), colGetEntry(mIndex, 0))
+                    && Objects.equal(e.getValue(), colGetEntry(mIndex, 1));
+        }
+
+        @Override
+        public final int hashCode() {
+            if (!mEntryValid) {
+                throw new IllegalStateException(
+                        "This container does not support retaining Map.Entry objects");
+            }
+            final Object key = colGetEntry(mIndex, 0);
+            final Object value = colGetEntry(mIndex, 1);
+            return (key == null ? 0 : key.hashCode()) ^
+                    (value == null ? 0 : value.hashCode());
+        }
+
+        @Override
+        public final String toString() {
+            return getKey() + "=" + getValue();
+        }
+    }
+
+    final class EntrySet implements Set<Map.Entry<K, V>> {
+        @Override
+        public boolean add(Map.Entry<K, V> object) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean addAll(Collection<? extends Map.Entry<K, V>> collection) {
+            int oldSize = colGetSize();
+            for (Map.Entry<K, V> entry : collection) {
+                colPut(entry.getKey(), entry.getValue());
+            }
+            return oldSize != colGetSize();
+        }
+
+        @Override
+        public void clear() {
+            colClear();
+        }
+
+        @Override
+        public boolean contains(Object object) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> collection) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return colGetSize() == 0;
+        }
+
+        @Override
+        public Iterator<Map.Entry<K, V>> iterator() {
+            return new MapIterator();
+        }
+
+        @Override
+        public boolean remove(Object object) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean removeAll(Collection<?> collection) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean retainAll(Collection<?> collection) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public int size() {
+            return colGetSize();
+        }
+
+        @Override
+        public Object[] toArray() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public <T> T[] toArray(T[] array) {
+            throw new UnsupportedOperationException();
+        }
+    };
+
+    final class KeySet implements Set<K> {
+
+        @Override
+        public boolean add(K object) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean addAll(Collection<? extends K> collection) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void clear() {
+            colClear();
+        }
+
+        @Override
+        public boolean contains(Object object) {
+            return colIndexOfKey(object) >= 0;
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> collection) {
+            return removeAllHelper(colGetMap(), collection);
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return colGetSize() == 0;
+        }
+
+        @Override
+        public Iterator<K> iterator() {
+            return new ArrayIterator<K>(0);
+        }
+
+        @Override
+        public boolean remove(Object object) {
+            int index = colIndexOfKey(object);
+            if (index >= 0) {
+                colRemoveAt(index);
+                return true;
+            }
+            return false;
+        }
+
+        @Override
+        public boolean removeAll(Collection<?> collection) {
+            return removeAllHelper(colGetMap(), collection);
+        }
+
+        @Override
+        public boolean retainAll(Collection<?> collection) {
+            return retainAllHelper(colGetMap(), collection);
+        }
+
+        @Override
+        public int size() {
+            return colGetSize();
+        }
+
+        @Override
+        public Object[] toArray() {
+            return toArrayHelper(1);
+        }
+
+        @Override
+        public <T> T[] toArray(T[] array) {
+            return toArrayHelper(array, 1);
+        }
+    };
+
+    final class ValuesCollection implements Collection<V> {
+
+        @Override
+        public boolean add(V object) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean addAll(Collection<? extends V> collection) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void clear() {
+            colClear();
+        }
+
+        @Override
+        public boolean contains(Object object) {
+            return colIndexOfValue(object) >= 0;
+        }
+
+        @Override
+        public boolean containsAll(Collection<?> collection) {
+            Iterator<?> it = collection.iterator();
+            while (it.hasNext()) {
+                if (!contains(it.next())) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return colGetSize() == 0;
+        }
+
+        @Override
+        public Iterator<V> iterator() {
+            return new ArrayIterator<V>(1);
+        }
+
+        @Override
+        public boolean remove(Object object) {
+            int index = colIndexOfValue(object);
+            if (index >= 0) {
+                colRemoveAt(index);
+                return true;
+            }
+            return false;
+        }
+
+        @Override
+        public boolean removeAll(Collection<?> collection) {
+            int N = colGetSize();
+            boolean changed = false;
+            for (int i=0; i<N; i++) {
+                Object cur = colGetEntry(i, 1);
+                if (collection.contains(cur)) {
+                    colRemoveAt(i);
+                    i--;
+                    N--;
+                    changed = true;
+                }
+            }
+            return changed;
+        }
+
+        @Override
+        public boolean retainAll(Collection<?> collection) {
+            int N = colGetSize();
+            boolean changed = false;
+            for (int i=0; i<N; i++) {
+                Object cur = colGetEntry(i, 1);
+                if (!collection.contains(cur)) {
+                    colRemoveAt(i);
+                    i--;
+                    N--;
+                    changed = true;
+                }
+            }
+            return changed;
+        }
+
+        @Override
+        public int size() {
+            return colGetSize();
+        }
+
+        @Override
+        public Object[] toArray() {
+            return toArrayHelper(1);
+        }
+
+        @Override
+        public <T> T[] toArray(T[] array) {
+            return toArrayHelper(array, 1);
+        }
+    };
+
+    public static <K, V> boolean containsAllHelper(Map<K, V> map, Collection<?> collection) {
+        Iterator<?> it = collection.iterator();
+        while (it.hasNext()) {
+            if (!map.containsKey(it.next())) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public static <K, V> boolean removeAllHelper(Map<K, V> map, Collection<?> collection) {
+        int oldSize = map.size();
+        Iterator<?> it = collection.iterator();
+        while (it.hasNext()) {
+            map.remove(it.next());
+        }
+        return oldSize != map.size();
+    }
+
+    public static <K, V> boolean retainAllHelper(Map<K, V> map, Collection<?> collection) {
+        int oldSize = map.size();
+        Iterator<K> it = map.keySet().iterator();
+        while (it.hasNext()) {
+            if (!collection.contains(it.next())) {
+                it.remove();
+            }
+        }
+        return oldSize != map.size();
+    }
+
+
+    public Object[] toArrayHelper(int offset) {
+        final int N = colGetSize();
+        Object[] result = new Object[N];
+        for (int i=0; i<N; i++) {
+            result[i] = colGetEntry(i, offset);
+        }
+        return result;
+    }
+
+    public <T> T[] toArrayHelper(T[] array, int offset) {
+        final int N  = colGetSize();
+        if (array.length < N) {
+            @SuppressWarnings("unchecked") T[] newArray
+                = (T[]) Array.newInstance(array.getClass().getComponentType(), N);
+            array = newArray;
+        }
+        for (int i=0; i<N; i++) {
+            array[i] = (T)colGetEntry(i, offset);
+        }
+        if (array.length > N) {
+            array[N] = null;
+        }
+        return array;
+    }
+
+    public Set<Map.Entry<K, V>> getEntrySet() {
+        if (mEntrySet == null) {
+            mEntrySet = new EntrySet();
+        }
+        return mEntrySet;
+    }
+
+    public Set<K> getKeySet() {
+        if (mKeySet == null) {
+            mKeySet = new KeySet();
+        }
+        return mKeySet;
+    }
+
+    public Collection<V> getValues() {
+        if (mValues == null) {
+            mValues = new ValuesCollection();
+        }
+        return mValues;
+    }
+
+    protected abstract int colGetSize();
+    protected abstract Object colGetEntry(int index, int offset);
+    protected abstract int colIndexOfKey(Object key);
+    protected abstract int colIndexOfValue(Object key);
+    protected abstract Map<K, V> colGetMap();
+    protected abstract void colPut(K key, V value);
+    protected abstract V colSetValue(int index, V value);
+    protected abstract void colRemoveAt(int index);
+    protected abstract void colClear();
+}
diff --git a/core/java/android/util/SparseArray.java b/core/java/android/util/SparseArray.java
index 7e8fee56ea95..001fc5bcbbb6 100644
--- a/core/java/android/util/SparseArray.java
+++ b/core/java/android/util/SparseArray.java
@@ -25,6 +25,8 @@ import com.android.internal.util.ArrayUtils;
  */
 public class SparseArray<E> implements Cloneable {
     private static final Object DELETED = new Object();
+    static final int[] EMPTY_INTS = new int[0];
+    static final Object[] EMPTY_OBJECTS = new Object[0];
     private boolean mGarbage = false;
 
     private int[] mKeys;
@@ -41,13 +43,19 @@ public class SparseArray<E> implements Cloneable {
     /**
      * Creates a new SparseArray containing no mappings that will not
      * require any additional memory allocation to store the specified
-     * number of mappings.
+     * number of mappings.  If you supply an initial capacity of 0, the
+     * sparse array will be initialized with a light-weight representation
+     * not requiring any additional array allocations.
      */
     public SparseArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
-
-        mKeys = new int[initialCapacity];
-        mValues = new Object[initialCapacity];
+        if (initialCapacity == 0) {
+            mKeys = EMPTY_INTS;
+            mValues = EMPTY_OBJECTS;
+        } else {
+            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
+            mKeys = new int[initialCapacity];
+            mValues = new Object[initialCapacity];
+        }
         mSize = 0;
     }
 
@@ -79,7 +87,7 @@ public class SparseArray<E> implements Cloneable {
      */
     @SuppressWarnings("unchecked")
     public E get(int key, E valueIfKeyNotFound) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = binarySearch(mKeys, mSize, key);
 
         if (i < 0 || mValues[i] == DELETED) {
             return valueIfKeyNotFound;
@@ -92,7 +100,7 @@ public class SparseArray<E> implements Cloneable {
      * Removes the mapping from the specified key, if there was any.
      */
     public void delete(int key) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             if (mValues[i] != DELETED) {
@@ -153,7 +161,7 @@ public class SparseArray<E> implements Cloneable {
      * was one.
      */
     public void put(int key, E value) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             mValues[i] = value;
@@ -170,7 +178,7 @@ public class SparseArray<E> implements Cloneable {
                 gc();
 
                 // Search again because indices may have changed.
-                i = ~binarySearch(mKeys, 0, mSize, key);
+                i = ~binarySearch(mKeys, mSize, key);
             }
 
             if (mSize >= mKeys.length) {
@@ -261,7 +269,7 @@ public class SparseArray<E> implements Cloneable {
             gc();
         }
 
-        return binarySearch(mKeys, 0, mSize, key);
+        return binarySearch(mKeys, mSize, key);
     }
 
     /**
@@ -335,23 +343,23 @@ public class SparseArray<E> implements Cloneable {
         mSize = pos + 1;
     }
 
-    private static int binarySearch(int[] a, int start, int len, int key) {
-        int high = start + len, low = start - 1, guess;
-
-        while (high - low > 1) {
-            guess = (high + low) / 2;
-
-            if (a[guess] < key)
-                low = guess;
-            else
-                high = guess;
+    // This is Arrays.binarySearch(), but doesn't do any argument validation.
+    static int binarySearch(int[] array, int size, int value) {
+        int lo = 0;
+        int hi = size - 1;
+
+        while (lo <= hi) {
+            int mid = (lo + hi) >>> 1;
+            int midVal = array[mid];
+
+            if (midVal < value) {
+                lo = mid + 1;
+            } else if (midVal > value) {
+                hi = mid - 1;
+            } else {
+                return mid;  // value found
+            }
         }
-
-        if (high == start + len)
-            return ~(start + len);
-        else if (a[high] == key)
-            return high;
-        else
-            return ~high;
+        return ~lo;  // value not present
     }
 }
diff --git a/core/java/android/util/SparseBooleanArray.java b/core/java/android/util/SparseBooleanArray.java
index 76c47c6aabad..73e3629d467d 100644
--- a/core/java/android/util/SparseBooleanArray.java
+++ b/core/java/android/util/SparseBooleanArray.java
@@ -25,6 +25,8 @@ import com.android.internal.util.ArrayUtils;
  * than using a HashMap to map Integers to Booleans.
  */
 public class SparseBooleanArray implements Cloneable {
+    static final boolean[] EMPTY_BOOLEANS = new boolean[0];
+
     /**
      * Creates a new SparseBooleanArray containing no mappings.
      */
@@ -35,13 +37,19 @@ public class SparseBooleanArray implements Cloneable {
     /**
      * Creates a new SparseBooleanArray containing no mappings that will not
      * require any additional memory allocation to store the specified
-     * number of mappings.
+     * number of mappings.  If you supply an initial capacity of 0, the
+     * sparse array will be initialized with a light-weight representation
+     * not requiring any additional array allocations.
      */
     public SparseBooleanArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
-
-        mKeys = new int[initialCapacity];
-        mValues = new boolean[initialCapacity];
+        if (initialCapacity == 0) {
+            mKeys = SparseArray.EMPTY_INTS;
+            mValues = EMPTY_BOOLEANS;
+        } else {
+            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
+            mKeys = new int[initialCapacity];
+            mValues = new boolean[initialCapacity];
+        }
         mSize = 0;
     }
 
@@ -71,7 +79,7 @@ public class SparseBooleanArray implements Cloneable {
      * if no such mapping has been made.
      */
     public boolean get(int key, boolean valueIfKeyNotFound) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i < 0) {
             return valueIfKeyNotFound;
@@ -84,7 +92,7 @@ public class SparseBooleanArray implements Cloneable {
      * Removes the mapping from the specified key, if there was any.
      */
     public void delete(int key) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             System.arraycopy(mKeys, i + 1, mKeys, i, mSize - (i + 1));
@@ -99,7 +107,7 @@ public class SparseBooleanArray implements Cloneable {
      * was one.
      */
     public void put(int key, boolean value) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             mValues[i] = value;
@@ -164,7 +172,7 @@ public class SparseBooleanArray implements Cloneable {
      * key is not mapped.
      */
     public int indexOfKey(int key) {
-        return binarySearch(mKeys, 0, mSize, key);
+        return SparseArray.binarySearch(mKeys, mSize, key);
     }
 
     /**
@@ -220,26 +228,6 @@ public class SparseBooleanArray implements Cloneable {
         mSize = pos + 1;
     }
     
-    private static int binarySearch(int[] a, int start, int len, int key) {
-        int high = start + len, low = start - 1, guess;
-
-        while (high - low > 1) {
-            guess = (high + low) / 2;
-
-            if (a[guess] < key)
-                low = guess;
-            else
-                high = guess;
-        }
-
-        if (high == start + len)
-            return ~(start + len);
-        else if (a[high] == key)
-            return high;
-        else
-            return ~high;
-    }
-
     private int[] mKeys;
     private boolean[] mValues;
     private int mSize;
diff --git a/core/java/android/util/SparseIntArray.java b/core/java/android/util/SparseIntArray.java
index 8d111770e8dd..122f7f58e0e5 100644
--- a/core/java/android/util/SparseIntArray.java
+++ b/core/java/android/util/SparseIntArray.java
@@ -24,7 +24,6 @@ import com.android.internal.util.ArrayUtils;
  * than using a HashMap to map Integers to Integers.
  */
 public class SparseIntArray implements Cloneable {
-
     private int[] mKeys;
     private int[] mValues;
     private int mSize;
@@ -39,13 +38,19 @@ public class SparseIntArray implements Cloneable {
     /**
      * Creates a new SparseIntArray containing no mappings that will not
      * require any additional memory allocation to store the specified
-     * number of mappings.
+     * number of mappings.  If you supply an initial capacity of 0, the
+     * sparse array will be initialized with a light-weight representation
+     * not requiring any additional array allocations.
      */
     public SparseIntArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
-
-        mKeys = new int[initialCapacity];
-        mValues = new int[initialCapacity];
+        if (initialCapacity == 0) {
+            mKeys = SparseArray.EMPTY_INTS;
+            mValues = SparseArray.EMPTY_INTS;
+        } else {
+            initialCapacity = ArrayUtils.idealIntArraySize(initialCapacity);
+            mKeys = new int[initialCapacity];
+            mValues = new int[initialCapacity];
+        }
         mSize = 0;
     }
 
@@ -75,7 +80,7 @@ public class SparseIntArray implements Cloneable {
      * if no such mapping has been made.
      */
     public int get(int key, int valueIfKeyNotFound) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i < 0) {
             return valueIfKeyNotFound;
@@ -88,7 +93,7 @@ public class SparseIntArray implements Cloneable {
      * Removes the mapping from the specified key, if there was any.
      */
     public void delete(int key) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             removeAt(i);
@@ -110,7 +115,7 @@ public class SparseIntArray implements Cloneable {
      * was one.
      */
     public void put(int key, int value) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             mValues[i] = value;
@@ -175,7 +180,7 @@ public class SparseIntArray implements Cloneable {
      * key is not mapped.
      */
     public int indexOfKey(int key) {
-        return binarySearch(mKeys, 0, mSize, key);
+        return SparseArray.binarySearch(mKeys, mSize, key);
     }
 
     /**
@@ -230,24 +235,4 @@ public class SparseIntArray implements Cloneable {
         mValues[pos] = value;
         mSize = pos + 1;
     }
-    
-    private static int binarySearch(int[] a, int start, int len, int key) {
-        int high = start + len, low = start - 1, guess;
-
-        while (high - low > 1) {
-            guess = (high + low) / 2;
-
-            if (a[guess] < key)
-                low = guess;
-            else
-                high = guess;
-        }
-
-        if (high == start + len)
-            return ~(start + len);
-        else if (a[high] == key)
-            return high;
-        else
-            return ~high;
-    }
 }
diff --git a/core/java/android/util/SparseLongArray.java b/core/java/android/util/SparseLongArray.java
index 2f7a6fe63bb5..c608996c99bf 100644
--- a/core/java/android/util/SparseLongArray.java
+++ b/core/java/android/util/SparseLongArray.java
@@ -24,6 +24,7 @@ import com.android.internal.util.ArrayUtils;
  * than using a HashMap to map Integers to Longs.
  */
 public class SparseLongArray implements Cloneable {
+    static final long[] EMPTY_LONGS = new long[0];
 
     private int[] mKeys;
     private long[] mValues;
@@ -39,13 +40,19 @@ public class SparseLongArray implements Cloneable {
     /**
      * Creates a new SparseLongArray containing no mappings that will not
      * require any additional memory allocation to store the specified
-     * number of mappings.
+     * number of mappings.  If you supply an initial capacity of 0, the
+     * sparse array will be initialized with a light-weight representation
+     * not requiring any additional array allocations.
      */
     public SparseLongArray(int initialCapacity) {
-        initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
-
-        mKeys = new int[initialCapacity];
-        mValues = new long[initialCapacity];
+        if (initialCapacity == 0) {
+            mKeys = SparseArray.EMPTY_INTS;
+            mValues = EMPTY_LONGS;
+        } else {
+            initialCapacity = ArrayUtils.idealLongArraySize(initialCapacity);
+            mKeys = new int[initialCapacity];
+            mValues = new long[initialCapacity];
+        }
         mSize = 0;
     }
 
@@ -75,7 +82,7 @@ public class SparseLongArray implements Cloneable {
      * if no such mapping has been made.
      */
     public long get(int key, long valueIfKeyNotFound) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i < 0) {
             return valueIfKeyNotFound;
@@ -88,7 +95,7 @@ public class SparseLongArray implements Cloneable {
      * Removes the mapping from the specified key, if there was any.
      */
     public void delete(int key) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             removeAt(i);
@@ -110,7 +117,7 @@ public class SparseLongArray implements Cloneable {
      * was one.
      */
     public void put(int key, long value) {
-        int i = binarySearch(mKeys, 0, mSize, key);
+        int i = SparseArray.binarySearch(mKeys, mSize, key);
 
         if (i >= 0) {
             mValues[i] = value;
@@ -164,7 +171,7 @@ public class SparseLongArray implements Cloneable {
      * key is not mapped.
      */
     public int indexOfKey(int key) {
-        return binarySearch(mKeys, 0, mSize, key);
+        return SparseArray.binarySearch(mKeys, mSize, key);
     }
 
     /**
@@ -222,24 +229,4 @@ public class SparseLongArray implements Cloneable {
         mKeys = nkeys;
         mValues = nvalues;
     }
-
-    private static int binarySearch(int[] a, int start, int len, long key) {
-        int high = start + len, low = start - 1, guess;
-
-        while (high - low > 1) {
-            guess = (high + low) / 2;
-
-            if (a[guess] < key)
-                low = guess;
-            else
-                high = guess;
-        }
-
-        if (high == start + len)
-            return ~(start + len);
-        else if (a[high] == key)
-            return high;
-        else
-            return ~high;
-    }
 }
diff --git a/core/java/android/view/View.java b/core/java/android/view/View.java
index babccf6f1c65..667505a573b1 100644
--- a/core/java/android/view/View.java
+++ b/core/java/android/view/View.java
@@ -15688,7 +15688,7 @@ public class View implements Drawable.Callback, KeyEvent.Callback,
 
     private void setKeyedTag(int key, Object tag) {
         if (mKeyedTags == null) {
-            mKeyedTags = new SparseArray<Object>();
+            mKeyedTags = new SparseArray<Object>(2);
         }
 
         mKeyedTags.put(key, tag);
diff --git a/core/java/android/widget/AbsListView.java b/core/java/android/widget/AbsListView.java
index 5de739945494..4c0ccca0a784 100644
--- a/core/java/android/widget/AbsListView.java
+++ b/core/java/android/widget/AbsListView.java
@@ -1151,10 +1151,10 @@ public abstract class AbsListView extends AdapterView<ListAdapter> implements Te
         }
         if (mChoiceMode != CHOICE_MODE_NONE) {
             if (mCheckStates == null) {
-                mCheckStates = new SparseBooleanArray();
+                mCheckStates = new SparseBooleanArray(0);
             }
             if (mCheckedIdStates == null && mAdapter != null && mAdapter.hasStableIds()) {
-                mCheckedIdStates = new LongSparseArray<Integer>();
+                mCheckedIdStates = new LongSparseArray<Integer>(0);
             }
             // Modal multi-choice mode only has choices when the mode is active. Clear them.
             if (mChoiceMode == CHOICE_MODE_MULTIPLE_MODAL) {
diff --git a/services/java/com/android/server/IntentResolver.java b/services/java/com/android/server/IntentResolver.java
index 35345f5762ee..3a35f3f857dd 100644
--- a/services/java/com/android/server/IntentResolver.java
+++ b/services/java/com/android/server/IntentResolver.java
@@ -20,7 +20,6 @@ import java.io.PrintWriter;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
@@ -29,12 +28,12 @@ import java.util.Set;
 
 import android.net.Uri;
 import android.util.FastImmutableArraySet;
+import android.util.ArrayMap;
 import android.util.Log;
 import android.util.PrintWriterPrinter;
 import android.util.Slog;
 import android.util.LogPrinter;
 import android.util.Printer;
-import android.util.StringBuilderPrinter;
 
 import android.content.Intent;
 import android.content.IntentFilter;
@@ -46,7 +45,6 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
     final private static String TAG = "IntentResolver";
     final private static boolean DEBUG = false;
     final private static boolean localLOGV = DEBUG || false;
-    final private static boolean VALIDATE = false;
 
     public void addFilter(F f) {
         if (localLOGV) {
@@ -67,21 +65,11 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
             register_intent_filter(f, f.actionsIterator(),
                     mTypedActionToFilter, "      TypedAction: ");
         }
-
-        if (VALIDATE) {
-            mOldResolver.addFilter(f);
-            verifyDataStructures(f);
-        }
     }
 
     public void removeFilter(F f) {
         removeFilterInternal(f);
         mFilters.remove(f);
-
-        if (VALIDATE) {
-            mOldResolver.removeFilter(f);
-            verifyDataStructures(f);
-        }
     }
 
     void removeFilterInternal(F f) {
@@ -319,16 +307,6 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
         }
         sortResults(finalList);
 
-        if (VALIDATE) {
-            List<R> oldList = mOldResolver.queryIntent(intent, resolvedType, defaultOnly, userId);
-            if (oldList.size() != finalList.size()) {
-                ValidationFailure here = new ValidationFailure();
-                here.fillInStackTrace();
-                Log.wtf(TAG, "Query result " + intent + " size is " + finalList.size()
-                        + "; old implementation is " + oldList.size(), here);
-            }
-        }
-
         if (debug) {
             Slog.v(TAG, "Final result list:");
             for (R r : finalList) {
@@ -379,7 +357,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
         out.print(prefix); out.println(filter);
     }
 
-    private final void addFilter(HashMap<String, F[]> map, String name, F filter) {
+    private final void addFilter(ArrayMap<String, F[]> map, String name, F filter) {
         F[] array = map.get(name);
         if (array == null) {
             array = newArray(2);
@@ -464,7 +442,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
     }
 
     private final int register_intent_filter(F filter, Iterator<String> i,
-            HashMap<String, F[]> dest, String prefix) {
+            ArrayMap<String, F[]> dest, String prefix) {
         if (i == null) {
             return 0;
         }
@@ -480,7 +458,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
     }
 
     private final int unregister_intent_filter(F filter, Iterator<String> i,
-            HashMap<String, F[]> dest, String prefix) {
+            ArrayMap<String, F[]> dest, String prefix) {
         if (i == null) {
             return 0;
         }
@@ -495,7 +473,7 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
         return num;
     }
 
-    private final void remove_all_objects(HashMap<String, F[]> map, String name,
+    private final void remove_all_objects(ArrayMap<String, F[]> map, String name,
             Object object) {
         F[] array = map.get(name);
         if (array != null) {
@@ -613,120 +591,6 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
         }
     };
 
-    static class ValidationFailure extends RuntimeException {
-    }
-
-    private void verifyDataStructures(IntentFilter src) {
-        compareMaps(src, "mTypeToFilter", mTypeToFilter, mOldResolver.mTypeToFilter);
-        compareMaps(src, "mBaseTypeToFilter", mBaseTypeToFilter, mOldResolver.mBaseTypeToFilter);
-        compareMaps(src, "mWildTypeToFilter", mWildTypeToFilter, mOldResolver.mWildTypeToFilter);
-        compareMaps(src, "mSchemeToFilter", mSchemeToFilter, mOldResolver.mSchemeToFilter);
-        compareMaps(src, "mActionToFilter", mActionToFilter, mOldResolver.mActionToFilter);
-        compareMaps(src, "mTypedActionToFilter", mTypedActionToFilter, mOldResolver.mTypedActionToFilter);
-    }
-
-    private void compareMaps(IntentFilter src, String name, HashMap<String, F[]> cur,
-            HashMap<String, ArrayList<F>> old) {
-        if (cur.size() != old.size()) {
-            StringBuilder missing = new StringBuilder(128);
-            for (Map.Entry<String, ArrayList<F>> e : old.entrySet()) {
-                final F[] curArray = cur.get(e.getKey());
-                if (curArray == null) {
-                    if (missing.length() > 0) {
-                        missing.append(' ');
-                    }
-                    missing.append(e.getKey());
-                }
-            }
-            StringBuilder extra = new StringBuilder(128);
-            for (Map.Entry<String, F[]> e : cur.entrySet()) {
-                if (old.get(e.getKey()) == null) {
-                    if (extra.length() > 0) {
-                        extra.append(' ');
-                    }
-                    extra.append(e.getKey());
-                }
-            }
-            StringBuilder srcStr = new StringBuilder(1024);
-            StringBuilderPrinter printer = new StringBuilderPrinter(srcStr);
-            src.dump(printer, "");
-            ValidationFailure here = new ValidationFailure();
-            here.fillInStackTrace();
-            Log.wtf(TAG, "New map " + name + " size is " + cur.size()
-                    + "; old implementation is " + old.size()
-                    + "; missing: " + missing.toString()
-                    + "; extra: " + extra.toString()
-                    + "; src: " + srcStr.toString(), here);
-            return;
-        }
-        for (Map.Entry<String, ArrayList<F>> e : old.entrySet()) {
-            final F[] curArray = cur.get(e.getKey());
-            int curLen = curArray != null ? curArray.length : 0;
-            if (curLen == 0) {
-                ValidationFailure here = new ValidationFailure();
-                here.fillInStackTrace();
-                Log.wtf(TAG, "New map " + name + " doesn't contain expected key "
-                        + e.getKey() + " (array=" + curArray + ")");
-                return;
-            }
-            while (curLen > 0 && curArray[curLen-1] == null) {
-                curLen--;
-            }
-            final ArrayList<F> oldArray = e.getValue();
-            final int oldLen = oldArray.size();
-            if (curLen != oldLen) {
-                ValidationFailure here = new ValidationFailure();
-                here.fillInStackTrace();
-                Log.wtf(TAG, "New map " + name + " entry " + e.getKey() + " size is "
-                        + curLen + "; old implementation is " + oldLen, here);
-                return;
-            }
-            for (int i=0; i<oldLen; i++) {
-                F f = oldArray.get(i);
-                boolean found = false;
-                for (int j=0; j<curLen; j++) {
-                    if (curArray[j] == f) {
-                        found = true;
-                        break;
-                    }
-                }
-                if (!found) {
-                    ValidationFailure here = new ValidationFailure();
-                    here.fillInStackTrace();
-                    Log.wtf(TAG, "New map " + name + " entry + " + e.getKey()
-                            + " doesn't contain expected filter " + f, here);
-                }
-            }
-            for (int i=0; i<curLen; i++) {
-                if (curArray[i] == null) {
-                    ValidationFailure here = new ValidationFailure();
-                    here.fillInStackTrace();
-                    Log.wtf(TAG, "New map " + name + " entry + " + e.getKey()
-                            + " has unexpected null at " + i + "; array: " + curArray, here);
-                    break;
-                }
-            }
-        }
-    }
-
-    private final IntentResolverOld<F, R> mOldResolver = new IntentResolverOld<F, R>() {
-        @Override protected boolean isPackageForFilter(String packageName, F filter) {
-            return IntentResolver.this.isPackageForFilter(packageName, filter);
-        }
-        @Override protected boolean allowFilterResult(F filter, List<R> dest) {
-            return IntentResolver.this.allowFilterResult(filter, dest);
-        }
-        @Override protected boolean isFilterStopped(F filter, int userId) {
-            return IntentResolver.this.isFilterStopped(filter, userId);
-        }
-        @Override protected R newResult(F filter, int match, int userId) {
-            return IntentResolver.this.newResult(filter, match, userId);
-        }
-        @Override protected void sortResults(List<R> results) {
-            IntentResolver.this.sortResults(results);
-        }
-    };
-
     /**
      * All filters that have been registered.
      */
@@ -736,14 +600,14 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
      * All of the MIME types that have been registered, such as "image/jpeg",
      * "image/*", or "{@literal *}/*".
      */
-    private final HashMap<String, F[]> mTypeToFilter = new HashMap<String, F[]>();
+    private final ArrayMap<String, F[]> mTypeToFilter = new ArrayMap<String, F[]>();
 
     /**
      * The base names of all of all fully qualified MIME types that have been
      * registered, such as "image" or "*".  Wild card MIME types such as
      * "image/*" will not be here.
      */
-    private final HashMap<String, F[]> mBaseTypeToFilter = new HashMap<String, F[]>();
+    private final ArrayMap<String, F[]> mBaseTypeToFilter = new ArrayMap<String, F[]>();
 
     /**
      * The base names of all of the MIME types with a sub-type wildcard that
@@ -752,21 +616,21 @@ public abstract class IntentResolver<F extends IntentFilter, R extends Object> {
      * included here.  This also includes the "*" for the "{@literal *}/*"
      * MIME type.
      */
-    private final HashMap<String, F[]> mWildTypeToFilter = new HashMap<String, F[]>();
+    private final ArrayMap<String, F[]> mWildTypeToFilter = new ArrayMap<String, F[]>();
 
     /**
      * All of the URI schemes (such as http) that have been registered.
      */
-    private final HashMap<String, F[]> mSchemeToFilter = new HashMap<String, F[]>();
+    private final ArrayMap<String, F[]> mSchemeToFilter = new ArrayMap<String, F[]>();
 
     /**
      * All of the actions that have been registered, but only those that did
      * not specify data.
      */
-    private final HashMap<String, F[]> mActionToFilter = new HashMap<String, F[]>();
+    private final ArrayMap<String, F[]> mActionToFilter = new ArrayMap<String, F[]>();
 
     /**
      * All of the actions that have been registered and specified a MIME type.
      */
-    private final HashMap<String, F[]> mTypedActionToFilter = new HashMap<String, F[]>();
+    private final ArrayMap<String, F[]> mTypedActionToFilter = new ArrayMap<String, F[]>();
 }
diff --git a/services/java/com/android/server/IntentResolverOld.java b/services/java/com/android/server/IntentResolverOld.java
deleted file mode 100644
index 94a23796cbb0..000000000000
--- a/services/java/com/android/server/IntentResolverOld.java
+++ /dev/null
@@ -1,638 +0,0 @@
-/*
- * Copyright (C) 2006 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.server;
-
-import java.io.PrintWriter;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import android.net.Uri;
-import android.util.FastImmutableArraySet;
-import android.util.Log;
-import android.util.PrintWriterPrinter;
-import android.util.Slog;
-import android.util.LogPrinter;
-import android.util.Printer;
-
-import android.content.Intent;
-import android.content.IntentFilter;
-
-/**
- * Temporary for verification of new implementation.
- * {@hide}
- */
-public abstract class IntentResolverOld<F extends IntentFilter, R extends Object> {
-    final private static String TAG = "IntentResolver";
-    final private static boolean DEBUG = false;
-    final private static boolean localLOGV = DEBUG || false;
-
-    public void addFilter(F f) {
-        if (localLOGV) {
-            Slog.v(TAG, "Adding filter: " + f);
-            f.dump(new LogPrinter(Log.VERBOSE, TAG, Log.LOG_ID_SYSTEM), "      ");
-            Slog.v(TAG, "    Building Lookup Maps:");
-        }
-
-        mFilters.add(f);
-        int numS = register_intent_filter(f, f.schemesIterator(),
-                mSchemeToFilter, "      Scheme: ");
-        int numT = register_mime_types(f, "      Type: ");
-        if (numS == 0 && numT == 0) {
-            register_intent_filter(f, f.actionsIterator(),
-                    mActionToFilter, "      Action: ");
-        }
-        if (numT != 0) {
-            register_intent_filter(f, f.actionsIterator(),
-                    mTypedActionToFilter, "      TypedAction: ");
-        }
-    }
-
-    public void removeFilter(F f) {
-        removeFilterInternal(f);
-        mFilters.remove(f);
-    }
-
-    void removeFilterInternal(F f) {
-        if (localLOGV) {
-            Slog.v(TAG, "Removing filter: " + f);
-            f.dump(new LogPrinter(Log.VERBOSE, TAG, Log.LOG_ID_SYSTEM), "      ");
-            Slog.v(TAG, "    Cleaning Lookup Maps:");
-        }
-
-        int numS = unregister_intent_filter(f, f.schemesIterator(),
-                mSchemeToFilter, "      Scheme: ");
-        int numT = unregister_mime_types(f, "      Type: ");
-        if (numS == 0 && numT == 0) {
-            unregister_intent_filter(f, f.actionsIterator(),
-                    mActionToFilter, "      Action: ");
-        }
-        if (numT != 0) {
-            unregister_intent_filter(f, f.actionsIterator(),
-                    mTypedActionToFilter, "      TypedAction: ");
-        }
-    }
-
-    boolean dumpMap(PrintWriter out, String titlePrefix, String title,
-            String prefix, Map<String, ArrayList<F>> map, String packageName,
-            boolean printFilter) {
-        String eprefix = prefix + "  ";
-        String fprefix = prefix + "    ";
-        boolean printedSomething = false;
-        Printer printer = null;
-        for (Map.Entry<String, ArrayList<F>> e : map.entrySet()) {
-            ArrayList<F> a = e.getValue();
-            final int N = a.size();
-            boolean printedHeader = false;
-            for (int i=0; i<N; i++) {
-                F filter = a.get(i);
-                if (packageName != null && !isPackageForFilter(packageName, filter)) {
-                    continue;
-                }
-                if (title != null) {
-                    out.print(titlePrefix); out.println(title);
-                    title = null;
-                }
-                if (!printedHeader) {
-                    out.print(eprefix); out.print(e.getKey()); out.println(":");
-                    printedHeader = true;
-                }
-                printedSomething = true;
-                dumpFilter(out, fprefix, filter);
-                if (printFilter) {
-                    if (printer == null) {
-                        printer = new PrintWriterPrinter(out);
-                    }
-                    filter.dump(printer, fprefix + "  ");
-                }
-            }
-        }
-        return printedSomething;
-    }
-
-    public boolean dump(PrintWriter out, String title, String prefix, String packageName,
-            boolean printFilter) {
-        String innerPrefix = prefix + "  ";
-        String sepPrefix = "\n" + prefix;
-        String curPrefix = title + "\n" + prefix;
-        if (dumpMap(out, curPrefix, "Full MIME Types:", innerPrefix,
-                mTypeToFilter, packageName, printFilter)) {
-            curPrefix = sepPrefix;
-        }
-        if (dumpMap(out, curPrefix, "Base MIME Types:", innerPrefix,
-                mBaseTypeToFilter, packageName, printFilter)) {
-            curPrefix = sepPrefix;
-        }
-        if (dumpMap(out, curPrefix, "Wild MIME Types:", innerPrefix,
-                mWildTypeToFilter, packageName, printFilter)) {
-            curPrefix = sepPrefix;
-        }
-        if (dumpMap(out, curPrefix, "Schemes:", innerPrefix,
-                mSchemeToFilter, packageName, printFilter)) {
-            curPrefix = sepPrefix;
-        }
-        if (dumpMap(out, curPrefix, "Non-Data Actions:", innerPrefix,
-                mActionToFilter, packageName, printFilter)) {
-            curPrefix = sepPrefix;
-        }
-        if (dumpMap(out, curPrefix, "MIME Typed Actions:", innerPrefix,
-                mTypedActionToFilter, packageName, printFilter)) {
-            curPrefix = sepPrefix;
-        }
-        return curPrefix == sepPrefix;
-    }
-
-    private class IteratorWrapper implements Iterator<F> {
-        private final Iterator<F> mI;
-        private F mCur;
-
-        IteratorWrapper(Iterator<F> it) {
-            mI = it;
-        }
-
-        public boolean hasNext() {
-            return mI.hasNext();
-        }
-
-        public F next() {
-            return (mCur = mI.next());
-        }
-
-        public void remove() {
-            if (mCur != null) {
-                removeFilterInternal(mCur);
-            }
-            mI.remove();
-        }
-
-    }
-
-    /**
-     * Returns an iterator allowing filters to be removed.
-     */
-    public Iterator<F> filterIterator() {
-        return new IteratorWrapper(mFilters.iterator());
-    }
-
-    /**
-     * Returns a read-only set of the filters.
-     */
-    public Set<F> filterSet() {
-        return Collections.unmodifiableSet(mFilters);
-    }
-
-    public List<R> queryIntentFromList(Intent intent, String resolvedType, 
-            boolean defaultOnly, ArrayList<ArrayList<F>> listCut, int userId) {
-        ArrayList<R> resultList = new ArrayList<R>();
-
-        final boolean debug = localLOGV ||
-                ((intent.getFlags() & Intent.FLAG_DEBUG_LOG_RESOLUTION) != 0);
-
-        FastImmutableArraySet<String> categories = getFastIntentCategories(intent);
-        final String scheme = intent.getScheme();
-        int N = listCut.size();
-        for (int i = 0; i < N; ++i) {
-            buildResolveList(intent, categories, debug, defaultOnly,
-                    resolvedType, scheme, listCut.get(i), resultList, userId);
-        }
-        sortResults(resultList);
-        return resultList;
-    }
-
-    public List<R> queryIntent(Intent intent, String resolvedType, boolean defaultOnly,
-            int userId) {
-        String scheme = intent.getScheme();
-
-        ArrayList<R> finalList = new ArrayList<R>();
-
-        final boolean debug = localLOGV ||
-                ((intent.getFlags() & Intent.FLAG_DEBUG_LOG_RESOLUTION) != 0);
-
-        if (debug) Slog.v(
-            TAG, "Resolving type " + resolvedType + " scheme " + scheme
-            + " of intent " + intent);
-
-        ArrayList<F> firstTypeCut = null;
-        ArrayList<F> secondTypeCut = null;
-        ArrayList<F> thirdTypeCut = null;
-        ArrayList<F> schemeCut = null;
-
-        // If the intent includes a MIME type, then we want to collect all of
-        // the filters that match that MIME type.
-        if (resolvedType != null) {
-            int slashpos = resolvedType.indexOf('/');
-            if (slashpos > 0) {
-                final String baseType = resolvedType.substring(0, slashpos);
-                if (!baseType.equals("*")) {
-                    if (resolvedType.length() != slashpos+2
-                            || resolvedType.charAt(slashpos+1) != '*') {
-                        // Not a wild card, so we can just look for all filters that
-                        // completely match or wildcards whose base type matches.
-                        firstTypeCut = mTypeToFilter.get(resolvedType);
-                        if (debug) Slog.v(TAG, "First type cut: " + firstTypeCut);
-                        secondTypeCut = mWildTypeToFilter.get(baseType);
-                        if (debug) Slog.v(TAG, "Second type cut: " + secondTypeCut);
-                    } else {
-                        // We can match anything with our base type.
-                        firstTypeCut = mBaseTypeToFilter.get(baseType);
-                        if (debug) Slog.v(TAG, "First type cut: " + firstTypeCut);
-                        secondTypeCut = mWildTypeToFilter.get(baseType);
-                        if (debug) Slog.v(TAG, "Second type cut: " + secondTypeCut);
-                    }
-                    // Any */* types always apply, but we only need to do this
-                    // if the intent type was not already */*.
-                    thirdTypeCut = mWildTypeToFilter.get("*");
-                    if (debug) Slog.v(TAG, "Third type cut: " + thirdTypeCut);
-                } else if (intent.getAction() != null) {
-                    // The intent specified any type ({@literal *}/*).  This
-                    // can be a whole heck of a lot of things, so as a first
-                    // cut let's use the action instead.
-                    firstTypeCut = mTypedActionToFilter.get(intent.getAction());
-                    if (debug) Slog.v(TAG, "Typed Action list: " + firstTypeCut);
-                }
-            }
-        }
-
-        // If the intent includes a data URI, then we want to collect all of
-        // the filters that match its scheme (we will further refine matches
-        // on the authority and path by directly matching each resulting filter).
-        if (scheme != null) {
-            schemeCut = mSchemeToFilter.get(scheme);
-            if (debug) Slog.v(TAG, "Scheme list: " + schemeCut);
-        }
-
-        // If the intent does not specify any data -- either a MIME type or
-        // a URI -- then we will only be looking for matches against empty
-        // data.
-        if (resolvedType == null && scheme == null && intent.getAction() != null) {
-            firstTypeCut = mActionToFilter.get(intent.getAction());
-            if (debug) Slog.v(TAG, "Action list: " + firstTypeCut);
-        }
-
-        FastImmutableArraySet<String> categories = getFastIntentCategories(intent);
-        if (firstTypeCut != null) {
-            buildResolveList(intent, categories, debug, defaultOnly,
-                    resolvedType, scheme, firstTypeCut, finalList, userId);
-        }
-        if (secondTypeCut != null) {
-            buildResolveList(intent, categories, debug, defaultOnly,
-                    resolvedType, scheme, secondTypeCut, finalList, userId);
-        }
-        if (thirdTypeCut != null) {
-            buildResolveList(intent, categories, debug, defaultOnly,
-                    resolvedType, scheme, thirdTypeCut, finalList, userId);
-        }
-        if (schemeCut != null) {
-            buildResolveList(intent, categories, debug, defaultOnly,
-                    resolvedType, scheme, schemeCut, finalList, userId);
-        }
-        sortResults(finalList);
-
-        if (debug) {
-            Slog.v(TAG, "Final result list:");
-            for (R r : finalList) {
-                Slog.v(TAG, "  " + r);
-            }
-        }
-        return finalList;
-    }
-
-    /**
-     * Control whether the given filter is allowed to go into the result
-     * list.  Mainly intended to prevent adding multiple filters for the
-     * same target object.
-     */
-    protected boolean allowFilterResult(F filter, List<R> dest) {
-        return true;
-    }
-
-    /**
-     * Returns whether the object associated with the given filter is
-     * "stopped," that is whether it should not be included in the result
-     * if the intent requests to excluded stopped objects.
-     */
-    protected boolean isFilterStopped(F filter, int userId) {
-        return false;
-    }
-
-    /**
-     * Returns whether this filter is owned by this package. This must be
-     * implemented to provide correct filtering of Intents that have
-     * specified a package name they are to be delivered to.
-     */
-    protected abstract boolean isPackageForFilter(String packageName, F filter);
-    
-    @SuppressWarnings("unchecked")
-    protected R newResult(F filter, int match, int userId) {
-        return (R)filter;
-    }
-
-    @SuppressWarnings("unchecked")
-    protected void sortResults(List<R> results) {
-        Collections.sort(results, mResolvePrioritySorter);
-    }
-
-    protected void dumpFilter(PrintWriter out, String prefix, F filter) {
-        out.print(prefix); out.println(filter);
-    }
-
-    private final int register_mime_types(F filter, String prefix) {
-        final Iterator<String> i = filter.typesIterator();
-        if (i == null) {
-            return 0;
-        }
-
-        int num = 0;
-        while (i.hasNext()) {
-            String name = i.next();
-            num++;
-            if (localLOGV) Slog.v(TAG, prefix + name);
-            String baseName = name;
-            final int slashpos = name.indexOf('/');
-            if (slashpos > 0) {
-                baseName = name.substring(0, slashpos).intern();
-            } else {
-                name = name + "/*";
-            }
-
-            ArrayList<F> array = mTypeToFilter.get(name);
-            if (array == null) {
-                //Slog.v(TAG, "Creating new array for " + name);
-                array = new ArrayList<F>();
-                mTypeToFilter.put(name, array);
-            }
-            array.add(filter);
-
-            if (slashpos > 0) {
-                array = mBaseTypeToFilter.get(baseName);
-                if (array == null) {
-                    //Slog.v(TAG, "Creating new array for " + name);
-                    array = new ArrayList<F>();
-                    mBaseTypeToFilter.put(baseName, array);
-                }
-                array.add(filter);
-            } else {
-                array = mWildTypeToFilter.get(baseName);
-                if (array == null) {
-                    //Slog.v(TAG, "Creating new array for " + name);
-                    array = new ArrayList<F>();
-                    mWildTypeToFilter.put(baseName, array);
-                }
-                array.add(filter);
-            }
-        }
-
-        return num;
-    }
-
-    private final int unregister_mime_types(F filter, String prefix) {
-        final Iterator<String> i = filter.typesIterator();
-        if (i == null) {
-            return 0;
-        }
-
-        int num = 0;
-        while (i.hasNext()) {
-            String name = i.next();
-            num++;
-            if (localLOGV) Slog.v(TAG, prefix + name);
-            String baseName = name;
-            final int slashpos = name.indexOf('/');
-            if (slashpos > 0) {
-                baseName = name.substring(0, slashpos).intern();
-            } else {
-                name = name + "/*";
-            }
-
-            if (!remove_all_objects(mTypeToFilter.get(name), filter)) {
-                mTypeToFilter.remove(name);
-            }
-
-            if (slashpos > 0) {
-                if (!remove_all_objects(mBaseTypeToFilter.get(baseName), filter)) {
-                    mBaseTypeToFilter.remove(baseName);
-                }
-            } else {
-                if (!remove_all_objects(mWildTypeToFilter.get(baseName), filter)) {
-                    mWildTypeToFilter.remove(baseName);
-                }
-            }
-        }
-        return num;
-    }
-
-    private final int register_intent_filter(F filter, Iterator<String> i,
-            HashMap<String, ArrayList<F>> dest, String prefix) {
-        if (i == null) {
-            return 0;
-        }
-
-        int num = 0;
-        while (i.hasNext()) {
-            String name = i.next();
-            num++;
-            if (localLOGV) Slog.v(TAG, prefix + name);
-            ArrayList<F> array = dest.get(name);
-            if (array == null) {
-                //Slog.v(TAG, "Creating new array for " + name);
-                array = new ArrayList<F>();
-                dest.put(name, array);
-            }
-            array.add(filter);
-        }
-        return num;
-    }
-
-    private final int unregister_intent_filter(F filter, Iterator<String> i,
-            HashMap<String, ArrayList<F>> dest, String prefix) {
-        if (i == null) {
-            return 0;
-        }
-
-        int num = 0;
-        while (i.hasNext()) {
-            String name = i.next();
-            num++;
-            if (localLOGV) Slog.v(TAG, prefix + name);
-            if (!remove_all_objects(dest.get(name), filter)) {
-                dest.remove(name);
-            }
-        }
-        return num;
-    }
-
-    private final boolean remove_all_objects(List<F> list, Object object) {
-        if (list != null) {
-            int N = list.size();
-            for (int idx=0; idx<N; idx++) {
-                if (list.get(idx) == object) {
-                    list.remove(idx);
-                    idx--;
-                    N--;
-                }
-            }
-            return N > 0;
-        }
-        return false;
-    }
-
-    private static FastImmutableArraySet<String> getFastIntentCategories(Intent intent) {
-        final Set<String> categories = intent.getCategories();
-        if (categories == null) {
-            return null;
-        }
-        return new FastImmutableArraySet<String>(categories.toArray(new String[categories.size()]));
-    }
-
-    private void buildResolveList(Intent intent, FastImmutableArraySet<String> categories,
-            boolean debug, boolean defaultOnly,
-            String resolvedType, String scheme, List<F> src, List<R> dest, int userId) {
-        final String action = intent.getAction();
-        final Uri data = intent.getData();
-        final String packageName = intent.getPackage();
-
-        final boolean excludingStopped = intent.isExcludingStopped();
-
-        final int N = src != null ? src.size() : 0;
-        boolean hasNonDefaults = false;
-        int i;
-        for (i=0; i<N; i++) {
-            F filter = src.get(i);
-            int match;
-            if (debug) Slog.v(TAG, "Matching against filter " + filter);
-
-            if (excludingStopped && isFilterStopped(filter, userId)) {
-                if (debug) {
-                    Slog.v(TAG, "  Filter's target is stopped; skipping");
-                }
-                continue;
-            }
-
-            // Is delivery being limited to filters owned by a particular package?
-            if (packageName != null && !isPackageForFilter(packageName, filter)) {
-                if (debug) {
-                    Slog.v(TAG, "  Filter is not from package " + packageName + "; skipping");
-                }
-                continue;
-            }
-
-            // Do we already have this one?
-            if (!allowFilterResult(filter, dest)) {
-                if (debug) {
-                    Slog.v(TAG, "  Filter's target already added");
-                }
-                continue;
-            }
-
-            match = filter.match(action, resolvedType, scheme, data, categories, TAG);
-            if (match >= 0) {
-                if (debug) Slog.v(TAG, "  Filter matched!  match=0x" +
-                        Integer.toHexString(match));
-                if (!defaultOnly || filter.hasCategory(Intent.CATEGORY_DEFAULT)) {
-                    final R oneResult = newResult(filter, match, userId);
-                    if (oneResult != null) {
-                        dest.add(oneResult);
-                    }
-                } else {
-                    hasNonDefaults = true;
-                }
-            } else {
-                if (debug) {
-                    String reason;
-                    switch (match) {
-                        case IntentFilter.NO_MATCH_ACTION: reason = "action"; break;
-                        case IntentFilter.NO_MATCH_CATEGORY: reason = "category"; break;
-                        case IntentFilter.NO_MATCH_DATA: reason = "data"; break;
-                        case IntentFilter.NO_MATCH_TYPE: reason = "type"; break;
-                        default: reason = "unknown reason"; break;
-                    }
-                    Slog.v(TAG, "  Filter did not match: " + reason);
-                }
-            }
-        }
-
-        if (dest.size() == 0 && hasNonDefaults) {
-            Slog.w(TAG, "resolveIntent failed: found match, but none with Intent.CATEGORY_DEFAULT");
-        }
-    }
-
-    // Sorts a List of IntentFilter objects into descending priority order.
-    @SuppressWarnings("rawtypes")
-    private static final Comparator mResolvePrioritySorter = new Comparator() {
-        public int compare(Object o1, Object o2) {
-            final int q1 = ((IntentFilter) o1).getPriority();
-            final int q2 = ((IntentFilter) o2).getPriority();
-            return (q1 > q2) ? -1 : ((q1 < q2) ? 1 : 0);
-        }
-    };
-
-    /**
-     * All filters that have been registered.
-     */
-    final HashSet<F> mFilters = new HashSet<F>();
-
-    /**
-     * All of the MIME types that have been registered, such as "image/jpeg",
-     * "image/*", or "{@literal *}/*".
-     */
-    final HashMap<String, ArrayList<F>> mTypeToFilter
-            = new HashMap<String, ArrayList<F>>();
-
-    /**
-     * The base names of all of all fully qualified MIME types that have been
-     * registered, such as "image" or "*".  Wild card MIME types such as
-     * "image/*" will not be here.
-     */
-    final HashMap<String, ArrayList<F>> mBaseTypeToFilter
-            = new HashMap<String, ArrayList<F>>();
-
-    /**
-     * The base names of all of the MIME types with a sub-type wildcard that
-     * have been registered.  For example, a filter with "image/*" will be
-     * included here as "image" but one with "image/jpeg" will not be
-     * included here.  This also includes the "*" for the "{@literal *}/*"
-     * MIME type.
-     */
-    final HashMap<String, ArrayList<F>> mWildTypeToFilter
-            = new HashMap<String, ArrayList<F>>();
-
-    /**
-     * All of the URI schemes (such as http) that have been registered.
-     */
-    final HashMap<String, ArrayList<F>> mSchemeToFilter
-            = new HashMap<String, ArrayList<F>>();
-
-    /**
-     * All of the actions that have been registered, but only those that did
-     * not specify data.
-     */
-    final HashMap<String, ArrayList<F>> mActionToFilter
-            = new HashMap<String, ArrayList<F>>();
-
-    /**
-     * All of the actions that have been registered and specified a MIME type.
-     */
-    final HashMap<String, ArrayList<F>> mTypedActionToFilter
-            = new HashMap<String, ArrayList<F>>();
-}
-
diff --git a/services/java/com/android/server/pm/PackageManagerService.java b/services/java/com/android/server/pm/PackageManagerService.java
index f8531fad258b..9d195df19d34 100644
--- a/services/java/com/android/server/pm/PackageManagerService.java
+++ b/services/java/com/android/server/pm/PackageManagerService.java
@@ -431,7 +431,7 @@ public class PackageManagerService extends IPackageManager.Stub {
         final SparseArray<HashMap<String, ArrayList<String>>> mUidMap;
 
         public PendingPackageBroadcasts() {
-            mUidMap = new SparseArray<HashMap<String, ArrayList<String>>>();
+            mUidMap = new SparseArray<HashMap<String, ArrayList<String>>>(2);
         }
 
         public ArrayList<String> get(int userId, String packageName) {
diff --git a/services/java/com/android/server/wm/WindowAnimator.java b/services/java/com/android/server/wm/WindowAnimator.java
index dbc991583033..3fc3ac6f6986 100644
--- a/services/java/com/android/server/wm/WindowAnimator.java
+++ b/services/java/com/android/server/wm/WindowAnimator.java
@@ -65,7 +65,7 @@ public class WindowAnimator {
     Object mLastWindowFreezeSource;
 
     SparseArray<DisplayContentsAnimator> mDisplayContentsAnimators =
-            new SparseArray<WindowAnimator.DisplayContentsAnimator>();
+            new SparseArray<WindowAnimator.DisplayContentsAnimator>(2);
 
     boolean mInitialized = false;
 
@@ -654,7 +654,7 @@ public class WindowAnimator {
 
     void setAppLayoutChanges(final AppWindowAnimator appAnimator, final int changes, String s) {
         // Used to track which displays layout changes have been done.
-        SparseIntArray displays = new SparseIntArray();
+        SparseIntArray displays = new SparseIntArray(2);
         WindowList windows = appAnimator.mAppToken.allAppWindows;
         for (int i = windows.size() - 1; i >= 0; i--) {
             final int displayId = windows.get(i).getDisplayId();
diff --git a/services/java/com/android/server/wm/WindowManagerService.java b/services/java/com/android/server/wm/WindowManagerService.java
index 3ebe083fb017..62141fd66eb8 100644
--- a/services/java/com/android/server/wm/WindowManagerService.java
+++ b/services/java/com/android/server/wm/WindowManagerService.java
@@ -424,7 +424,7 @@ public class WindowManagerService extends IWindowManager.Stub
     String mLastANRState;
 
     /** All DisplayContents in the world, kept here */
-    private SparseArray<DisplayContent> mDisplayContents = new SparseArray<DisplayContent>();
+    private SparseArray<DisplayContent> mDisplayContents = new SparseArray<DisplayContent>(2);
 
     private final AllWindowsIterator mTmpWindowsIterator = new AllWindowsIterator();
 
diff --git a/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java b/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java
index c7cd975c8d1c..d7a6c1d56fa8 100644
--- a/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java
+++ b/tests/ActivityTests/src/com/google/android/test/activity/ActivityTestMain.java
@@ -182,7 +182,7 @@ public class ActivityTestMain extends Activity {
         menu.add("Send!").setOnMenuItemClickListener(new MenuItem.OnMenuItemClickListener() {
             @Override public boolean onMenuItemClick(MenuItem item) {
                 Intent intent = new Intent(ActivityTestMain.this, SingleUserReceiver.class);
-                sendOrderedBroadcast(intent, null, new BroadcastResultReceiver(), 
+                sendOrderedBroadcast(intent, null, new BroadcastResultReceiver(),
                         null, Activity.RESULT_OK, null, null);
                 return true;
             }
@@ -285,6 +285,12 @@ public class ActivityTestMain extends Activity {
                 return true;
             }
         });
+        menu.add("HashArray").setOnMenuItemClickListener(new MenuItem.OnMenuItemClickListener() {
+            @Override public boolean onMenuItemClick(MenuItem item) {
+                ArrayMapTests.run();
+                return true;
+            }
+        });
         return true;
     }
 
diff --git a/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
new file mode 100644
index 000000000000..d9e1a83b0bde
--- /dev/null
+++ b/tests/ActivityTests/src/com/google/android/test/activity/ArrayMapTests.java
@@ -0,0 +1,303 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.google.android.test.activity;
+
+import android.util.ArrayMap;
+import android.util.Log;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+
+public class ArrayMapTests {
+    static final int OP_ADD = 1;
+    static final int OP_REM = 2;
+
+    static int[] OPS = new int[] {
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD, OP_ADD,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+            OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM, OP_REM,
+    };
+
+    static int[] KEYS = new int[] {
+            // General adding and removing.
+             100,   1900,    600,    200,   1200,   1500,   1800,    100,   1900,
+            2100,    300,    800,    600,   1100,   1300,   2000,   1000,   1400,
+             600,    100,   1900,    600,    300,   2100,    200,    800,    800,
+            1800,   1500,   1300,   1100,   2000,   1400,   1000,   1200,   1900,
+
+            // Shrink when removing item from end.
+             100,    200,    300,    400,    500,    600,    700,    800,    900,
+             900,    800,    700,    600,    500,    400,    300,    200,    100,
+
+            // Shrink when removing item from middle.
+             100,    200,    300,    400,    500,    600,    700,    800,    900,
+             900,    800,    700,    600,    500,    400,    200,    300,    100,
+
+            // Shrink when removing item from front.
+             100,    200,    300,    400,    500,    600,    700,    800,    900,
+             900,    800,    700,    600,    500,    400,    100,    200,    300,
+
+            // Test hash collisions.
+             105,    106,    108,    104,    102,    102,    107,      5,    205,
+               4,    202,    203,      3,      5,    101,    109,    200,    201,
+             106,    108,    104,    102,    103,    105,    107,    101,    109,
+               4,      5,      3,      5,    200,    203,    202,    201,    205,
+    };
+
+    static class ControlledHash {
+        final int mValue;
+
+        ControlledHash(int value) {
+            mValue = value;
+        }
+
+        @Override
+        public final boolean equals(Object o) {
+            return mValue == ((ControlledHash)o).mValue;
+        }
+
+        @Override
+        public final int hashCode() {
+            return mValue/100;
+        }
+
+        @Override
+        public final String toString() {
+            return Integer.toString(mValue);
+        }
+    }
+
+    private static boolean compare(Object v1, Object v2) {
+        if (v1 == null) {
+            return v2 == null;
+        }
+        if (v2 == null) {
+            return false;
+        }
+        return v1.equals(v2);
+    }
+
+    private static boolean compareMaps(HashMap map, ArrayMap array) {
+        if (map.size() != array.size()) {
+            Log.e("test", "Bad size: expected " + map.size() + ", got " + array.size());
+            return false;
+        }
+
+        Set<Map.Entry> mapSet = map.entrySet();
+        for (Map.Entry entry : mapSet) {
+            Object expValue = entry.getValue();
+            Object gotValue = array.get(entry.getKey());
+            if (!compare(expValue, gotValue)) {
+                Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue
+                        + " at key " + entry.getKey());
+                return false;
+            }
+        }
+
+        for (int i=0; i<array.size(); i++) {
+            Object gotValue = array.valueAt(i);
+            Object key = array.keyAt(i);
+            Object expValue = map.get(key);
+            if (!compare(expValue, gotValue)) {
+                Log.e("test", "Bad value: expected " + expValue + ", got " + gotValue
+                        + " at key " + key);
+                return false;
+            }
+        }
+
+        int index = 0;
+        for (Object entry : array.entrySet()) {
+            Object key = ((Map.Entry)entry).getKey();
+            Object value = ((Map.Entry)entry).getValue();
+            Object realKey = array.keyAt(index);
+            Object realValue = array.valueAt(index);
+            if (!compare(key, realKey)) {
+                Log.e("test", "Bad entry iterator: expected key " + realKey + ", got " + key
+                        + " at index " + index);
+                return false;
+            }
+            if (!compare(value, realValue)) {
+                Log.e("test", "Bad entry iterator: expected value " + realValue + ", got " + value
+                        + " at index " + index);
+                return false;
+            }
+            index++;
+        }
+
+        index = 0;
+        for (Object key : array.keySet()) {
+            Object realKey = array.keyAt(index);
+            if (!compare(key, realKey)) {
+                Log.e("test", "Bad key iterator: expected key " + realKey + ", got " + key
+                        + " at index " + index);
+                return false;
+            }
+            index++;
+        }
+
+        index = 0;
+        for (Object value : array.values()) {
+            Object realValue = array.valueAt(index);
+            if (!compare(value, realValue)) {
+                Log.e("test", "Bad value iterator: expected value " + realValue + ", got " + value
+                        + " at index " + index);
+                return false;
+            }
+            index++;
+        }
+
+        return true;
+    }
+
+    private static boolean validateArrayMap(ArrayMap array) {
+        Set<Map.Entry> entrySet = array.entrySet();
+        int index=0;
+        Iterator<Map.Entry> entryIt = entrySet.iterator();
+        while (entryIt.hasNext()) {
+            Map.Entry entry = entryIt.next();
+            Object value = entry.getKey();
+            Object realValue = array.keyAt(index);
+            if (!compare(realValue, value)) {
+                Log.e("test", "Bad hash array entry set: expected key " + realValue
+                        + ", got " + value + " at index " + index);
+                return false;
+            }
+            value = entry.getValue();
+            realValue = array.valueAt(index);
+            if (!compare(realValue, value)) {
+                Log.e("test", "Bad hash array entry set: expected value " + realValue
+                        + ", got " + value + " at index " + index);
+                return false;
+            }
+            index++;
+        }
+
+        index = 0;
+        Set keySet = array.keySet();
+        Iterator keyIt = keySet.iterator();
+        while (keyIt.hasNext()) {
+            Object value = keyIt.next();
+            Object realValue = array.keyAt(index);
+            if (!compare(realValue, value)) {
+                Log.e("test", "Bad hash array key set: expected key " + realValue
+                        + ", got " + value + " at index " + index);
+                return false;
+            }
+            index++;
+        }
+
+        index = 0;
+        Collection valueCol = array.values();
+        Iterator valueIt = valueCol.iterator();
+        while (valueIt.hasNext()) {
+            Object value = valueIt.next();
+            Object realValue = array.valueAt(index);
+            if (!compare(realValue, value)) {
+                Log.e("test", "Bad hash array value col: expected value " + realValue
+                        + ", got " + value + " at index " + index);
+                return false;
+            }
+            index++;
+        }
+
+        return true;
+    }
+
+    private static void dump(HashMap map, ArrayMap array) {
+        Log.e("test", "HashMap of " + map.size() + " entries:");
+        Set<Map.Entry> mapSet = map.entrySet();
+        for (Map.Entry entry : mapSet) {
+            Log.e("test", "    " + entry.getKey() + " -> " + entry.getValue());
+        }
+        Log.e("test", "ArrayMap of " + array.size() + " entries:");
+        for (int i=0; i<array.size(); i++) {
+            Log.e("test", "    " + array.keyAt(i) + " -> " + array.valueAt(i));
+        }
+    }
+
+    public static void run() {
+        HashMap<ControlledHash, Integer> mHashMap = new HashMap<ControlledHash, Integer>();
+        ArrayMap<ControlledHash, Integer> mArrayMap = new ArrayMap<ControlledHash, Integer>();
+
+        for (int i=0; i<OPS.length; i++) {
+            Integer oldMap;
+            Integer oldArray;
+            switch (OPS[i]) {
+                case OP_ADD:
+                    Log.i("test", "Adding key: " + KEYS[i]);
+                    oldMap = mHashMap.put(new ControlledHash(KEYS[i]), i);
+                    oldArray = mArrayMap.put(new ControlledHash(KEYS[i]), i);
+                    break;
+                case OP_REM:
+                    Log.i("test", "Removing key: " + KEYS[i]);
+                    oldMap = mHashMap.remove(new ControlledHash(KEYS[i]));
+                    oldArray = mArrayMap.remove(new ControlledHash(KEYS[i]));
+                    break;
+                default:
+                    Log.e("test", "Bad operation " + OPS[i] + " @ " + i);
+                    return;
+            }
+            if (!compare(oldMap, oldArray)) {
+                Log.e("test", "Bad result: expected " + oldMap + ", got " + oldArray);
+                dump(mHashMap, mArrayMap);
+                return;
+            }
+            if (!validateArrayMap(mArrayMap)) {
+                dump(mHashMap, mArrayMap);
+                return;
+            }
+            if (!compareMaps(mHashMap, mArrayMap)) {
+                dump(mHashMap, mArrayMap);
+                return;
+            }
+        }
+
+        mArrayMap.put(new ControlledHash(50000), 100);
+        ControlledHash lookup = new ControlledHash(50000);
+        Iterator<ControlledHash> it = mArrayMap.keySet().iterator();
+        while (it.hasNext()) {
+            if (it.next().equals(lookup)) {
+                it.remove();
+            }
+        }
+        if (mArrayMap.containsKey(lookup)) {
+            Log.e("test", "Bad iterator: didn't remove test key");
+            dump(mHashMap, mArrayMap);
+        }
+
+        Log.e("test", "Test successful; printing final map.");
+        dump(mHashMap, mArrayMap);
+    }
+}
diff --git a/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java b/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java
index 5f4f00626059..309ce34dc87a 100644
--- a/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java
+++ b/tests/FrameworkPerf/src/com/android/frameworkperf/TestService.java
@@ -21,7 +21,11 @@ import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
 import java.io.IOException;
 import java.io.RandomAccessFile;
+import java.lang.String;
+import java.util.HashMap;
+import java.util.Random;
 
+import android.util.ArrayMap;
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
 
@@ -142,6 +146,18 @@ public class TestService extends Service {
             new LoadRecycleLargeBitmapOp(),
             new LoadSmallScaledBitmapOp(),
             new LoadLargeScaledBitmapOp(),
+            new GrowTinyHashMapOp(),
+            new GrowTinyArrayMapOp(),
+            new GrowSmallHashMapOp(),
+            new GrowSmallArrayMapOp(),
+            new GrowLargeHashMapOp(),
+            new GrowLargeArrayMapOp(),
+            new LookupTinyHashMapOp(),
+            new LookupTinyArrayMapOp(),
+            new LookupSmallHashMapOp(),
+            new LookupSmallArrayMapOp(),
+            new LookupLargeHashMapOp(),
+            new LookupLargeArrayMapOp(),
     };
 
     static final int CMD_START_TEST = 1;
@@ -1111,4 +1127,196 @@ public class TestService extends Service {
             mFile.delete();
         }
     }
+
+    static abstract class GenericMapOp extends Op {
+        final int mSize;
+        String[] mKeys;
+        String[] mValues;
+
+        GenericMapOp(String name, String longName, int size) {
+            super(name, longName);
+            mSize = size;
+        }
+
+        void onInit(Context context, boolean foreground) {
+            mKeys = new String[mSize];
+            mValues = new String[mSize];
+            Random random = new Random(0);
+            for (int i=0; i<mSize; i++) {
+                int chars = random.nextInt(10);
+                StringBuilder builder = new StringBuilder(chars);
+                for (int j=0; j<chars; j++) {
+                    builder.append('a' + random.nextInt(100));
+                }
+                mKeys[i] = builder.toString();
+                mValues[i] = Integer.toString(i);
+            }
+        }
+
+        int getOpsPerRun() {
+            return mSize;
+        }
+    }
+
+    static class GrowTinyHashMapOp extends GenericMapOp {
+        GrowTinyHashMapOp() {
+            super("GrowTinyHashMap", "Add 5 items to a HashMap", 5);
+        }
+
+        boolean onRun() {
+            HashMap<String, String> map = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowTinyArrayMapOp extends GenericMapOp {
+        GrowTinyArrayMapOp() {
+            super("GrowTinyArrayMap", "Add 5 items to a ArrayMap", 5);
+        }
+
+        boolean onRun() {
+            ArrayMap<String, String> map = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowSmallHashMapOp extends GenericMapOp {
+        GrowSmallHashMapOp() {
+            super("GrowSmallHashMap", "Add 100 items to a HashMap", 100);
+        }
+
+        boolean onRun() {
+            HashMap<String, String> map = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowSmallArrayMapOp extends GenericMapOp {
+        GrowSmallArrayMapOp() {
+            super("GrowSmallArrayMap", "Add 100 items to a ArrayMap", 100);
+        }
+
+        boolean onRun() {
+            ArrayMap<String, String> map = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowLargeHashMapOp extends GenericMapOp {
+        GrowLargeHashMapOp() {
+            super("GrowLargeHashMap", "Add 10000 items to a HashMap", 10000);
+        }
+
+        boolean onRun() {
+            HashMap<String, String> map = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class GrowLargeArrayMapOp extends GenericMapOp {
+        GrowLargeArrayMapOp() {
+            super("GrowLargeArrayMap", "Add 10000 items to a ArrayMap", 10000);
+        }
+
+        boolean onRun() {
+            ArrayMap<String, String> map = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                map.put(mKeys[i], mValues[i]);
+            }
+            return true;
+        }
+    }
+
+    static class LookupTinyHashMapOp extends LookupSmallHashMapOp {
+        LookupTinyHashMapOp() {
+            super("LookupTinyHashMap", "Lookup items in 5 entry HashMap", 5);
+        }
+    }
+
+    static class LookupTinyArrayMapOp extends LookupSmallArrayMapOp {
+        LookupTinyArrayMapOp() {
+            super("LookupTinyArrayMap", "Lookup items in 5 entry ArrayMap", 5);
+        }
+    }
+
+    static class LookupSmallHashMapOp extends GenericMapOp {
+        HashMap<String, String> mHashMap;
+
+        LookupSmallHashMapOp() {
+            super("LookupSmallHashMap", "Lookup items in 100 entry HashMap", 100);
+        }
+
+        LookupSmallHashMapOp(String name, String longname, int size) {
+            super(name, longname, size);
+        }
+
+        void onInit(Context context, boolean foreground) {
+            super.onInit(context, foreground);
+            mHashMap = new HashMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                mHashMap.put(mKeys[i], mValues[i]);
+            }
+        }
+
+        boolean onRun() {
+            for (int i=0; i<mSize; i++) {
+                mHashMap.get(mKeys[i]);
+            }
+            return true;
+        }
+    }
+
+    static class LookupSmallArrayMapOp extends GenericMapOp {
+        ArrayMap<String, String> mArrayMap;
+
+        LookupSmallArrayMapOp() {
+            super("LookupSmallArrayMap", "Lookup items in 100 entry ArrayMap", 100);
+        }
+
+        LookupSmallArrayMapOp(String name, String longname, int size) {
+            super(name, longname, size);
+        }
+
+        void onInit(Context context, boolean foreground) {
+            super.onInit(context, foreground);
+            mArrayMap = new ArrayMap<String, String>();
+            for (int i=0; i<mSize; i++) {
+                mArrayMap.put(mKeys[i], mValues[i]);
+            }
+        }
+
+        boolean onRun() {
+            for (int i=0; i<mSize; i++) {
+                mArrayMap.get(mKeys[i]);
+            }
+            return true;
+        }
+    }
+
+    static class LookupLargeHashMapOp extends LookupSmallHashMapOp {
+        LookupLargeHashMapOp() {
+            super("LookupLargeHashMap", "Lookup items in 10000 entry HashMap", 10000);
+        }
+    }
+
+    static class LookupLargeArrayMapOp extends LookupSmallArrayMapOp {
+        LookupLargeArrayMapOp() {
+            super("LookupLargeArrayMap", "Lookup items in 10000 entry ArrayMap", 10000);
+        }
+    }
 }