FileDocCategorySizeDatePackage
ArrayMap.javaAPI DocAndroid 5.1 API30277Thu Mar 12 22:22:10 GMT 2015android.util

ArrayMap

public final class ArrayMap extends Object implements Map
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).

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%.

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 explicit call to set the capacity should turn off this aggressive shrinking behavior.

Fields Summary
private static final boolean
DEBUG
private static final String
TAG
private static final int
BASE_SIZE
The minimum amount by which the capacity of a ArrayMap will increase. This is tuned to be relatively space-efficient.
private static final int
CACHE_SIZE
Maximum number of entries to have in array caches.
public static final ArrayMap
EMPTY
static Object[]
mBaseCache
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 int
mBaseCacheSize
static Object[]
mTwiceBaseCache
static int
mTwiceBaseCacheSize
static final int[]
EMPTY_IMMUTABLE_INTS
Special hash array value that indicates the container is immutable.
int[]
mHashes
Object[]
mArray
int
mSize
MapCollections
mCollections
Constructors Summary
public ArrayMap()
Create a new empty ArrayMap. The default capacity of an array map is 0, and will grow once items are added to it.

        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        mSize = 0;
public ArrayMap(int capacity)
Create a new ArrayMap with a given initial capacity.

        if (capacity == 0) {
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
private ArrayMap(boolean immutable)

        // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
        // instance instead of the usual EmptyArray.INT. The reference
        // is checked later to see if the array is allowed to grow.
        mHashes = immutable ? EMPTY_IMMUTABLE_INTS : EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        mSize = 0;
public ArrayMap(ArrayMap map)
Create a new ArrayMap with the mappings from the given ArrayMap.

        this();
        if (map != null) {
            putAll(map);
        }
Methods Summary
private voidallocArrays(int size)

        if (mHashes == EMPTY_IMMUTABLE_INTS) {
            throw new UnsupportedOperationException("ArrayMap is immutable");
        }
        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];
public voidappend(K key, V value)
Special fast path for appending items to the end of the array without validation. The array must already be large enough to contain the item.

hide

        int index = mSize;
        final int hash = key == null ? 0 : key.hashCode();
        if (index >= mHashes.length) {
            throw new IllegalStateException("Array is full");
        }
        if (index > 0 && mHashes[index-1] > hash) {
            RuntimeException e = new RuntimeException("here");
            e.fillInStackTrace();
            Log.w(TAG, "New hash " + hash
                    + " is before end of array hash " + mHashes[index-1]
                    + " at index " + index + " key " + key, e);
            put(key, value);
            return;
        }
        mSize = index+1;
        mHashes[index] = hash;
        index <<= 1;
        mArray[index] = key;
        mArray[index+1] = value;
public voidclear()
Make the array map empty. All storage is released.

        if (mSize > 0) {
            freeArrays(mHashes, mArray, mSize);
            mHashes = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
            mSize = 0;
        }
public booleancontainsAll(java.util.Collection collection)
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 collection, else returns false.

        return MapCollections.containsAllHelper(this, collection);
public booleancontainsKey(java.lang.Object key)
Check whether a key exists in the array.

param
key The key to search for.
return
Returns true if the key exists, else false.

        return indexOfKey(key) >= 0;
public booleancontainsValue(java.lang.Object value)
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.

        return indexOfValue(value) >= 0;
public voidensureCapacity(int minimumCapacity)
Ensure the array map can hold at least minimumCapacity items.

        if (mHashes.length < minimumCapacity) {
            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(minimumCapacity);
            if (mSize > 0) {
                System.arraycopy(ohashes, 0, mHashes, 0, mSize);
                System.arraycopy(oarray, 0, mArray, 0, mSize<<1);
            }
            freeArrays(ohashes, oarray, mSize);
        }
public java.util.SetentrySet()
Return a {@link java.util.Set} for iterating over and interacting with all mappings in the array map.

Note: this is a very inefficient way to access the array contents, it requires generating a number of temporary objects.

Note:

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 not hold on to it after calling {@link java.util.Iterator#next() Iterator.next}.

        return getCollection().getEntrySet();
public booleanequals(java.lang.Object object)
{@inheritDoc}

This implementation returns false if the object is not a map, or if the maps have different sizes. Otherwise, for each key in this map, values of both maps are compared. If the values for any key are not equal, the method returns false, otherwise it returns true.

        if (this == object) {
            return true;
        }
        if (object instanceof Map) {
            Map<?, ?> map = (Map<?, ?>) object;
            if (size() != map.size()) {
                return false;
            }

            try {
                for (int i=0; i<mSize; i++) {
                    K key = keyAt(i);
                    V mine = valueAt(i);
                    Object theirs = map.get(key);
                    if (mine == null) {
                        if (theirs != null || !map.containsKey(key)) {
                            return false;
                        }
                    } else if (!mine.equals(theirs)) {
                        return false;
                    }
                }
            } catch (NullPointerException ignored) {
                return false;
            } catch (ClassCastException ignored) {
                return false;
            }
            return true;
        }
        return false;
public voiderase()

hide
Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap.

        if (mSize > 0) {
            final int N = mSize<<1;
            final Object[] array = mArray;
            for (int i=0; i<N; i++) {
                array[i] = null;
            }
            mSize = 0;
        }
private static voidfreeArrays(int[] hashes, java.lang.Object[] array, 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");
                }
            }
        }
public Vget(java.lang.Object key)
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.

        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
private MapCollectionsgetCollection()

        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 indexOfKey(key);
                }

                @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;
public inthashCode()
{@inheritDoc}

        final int[] hashes = mHashes;
        final Object[] array = mArray;
        int result = 0;
        for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) {
            Object value = array[v];
            result += hashes[i] ^ (value == null ? 0 : value.hashCode());
        }
        return result;
intindexOf(java.lang.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 = ContainerHelpers.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 (key.equals(mArray[index<<1])) {
            return index;
        }

        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            if (key.equals(mArray[end << 1])) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            if (key.equals(mArray[i << 1])) 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;
public intindexOfKey(java.lang.Object key)
Returns the index of a key in the set.

param
key The key to search for.
return
Returns the index of the key if it exists, else a negative integer.

        return key == null ? indexOfNull() : indexOf(key, key.hashCode());
intindexOfNull()

        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }

        int index = ContainerHelpers.binarySearch(mHashes, N, 0);

        // 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 (null == mArray[index<<1]) {
            return index;
        }

        // Search for a matching key after the index.
        int end;
        for (end = index + 1; end < N && mHashes[end] == 0; end++) {
            if (null == mArray[end << 1]) return end;
        }

        // Search for a matching key before the index.
        for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) {
            if (null == mArray[i << 1]) 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;
intindexOfValue(java.lang.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;
public booleanisEmpty()
Return true if the array map contains no items.

        return mSize <= 0;
public KkeyAt(int index)
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.

        return (K)mArray[index << 1];
public java.util.SetkeySet()
Return a {@link java.util.Set} for iterating over and interacting with all keys in the array map.

Note: this is a fairly inefficient way to access the array contents, it requires generating a number of temporary objects.

        return getCollection().getKeySet();
public Vput(K key, V value)
Add a new value to the array map.

param
key The key under which to store the value. 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.

        final int hash;
        int index;
        if (key == null) {
            hash = 0;
            index = indexOfNull();
        } else {
            hash = key.hashCode();
            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;
public voidputAll(android.util.ArrayMap array)
Perform a {@link #put(Object, Object)} of all key/value pairs in array

param
array The array whose contents are to be retrieved.

        final int N = array.mSize;
        ensureCapacity(mSize + N);
        if (mSize == 0) {
            if (N > 0) {
                System.arraycopy(array.mHashes, 0, mHashes, 0, N);
                System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
                mSize = N;
            }
        } else {
            for (int i=0; i<N; i++) {
                put(array.keyAt(i), array.valueAt(i));
            }
        }
public voidputAll(java.util.Map map)
Perform a {@link #put(Object, Object)} of all key/value pairs in map

param
map The map whose contents are to be retrieved.

        ensureCapacity(mSize + map.size());
        for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
public Vremove(java.lang.Object key)
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.

        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }

        return null;
public booleanremoveAll(java.util.Collection collection)
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.

        return MapCollections.removeAllHelper(this, collection);
public VremoveAt(int index)
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.

        final Object old = 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 = EmptyArray.INT;
            mArray = EmptyArray.OBJECT;
            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 (V)old;
public booleanretainAll(java.util.Collection collection)
Remove all keys in the array map that do not 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.

        return MapCollections.retainAllHelper(this, collection);
public VsetValueAt(int index, V value)
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.

        index = (index << 1) + 1;
        V old = (V)mArray[index];
        mArray[index] = value;
        return old;
public intsize()
Return the number of items in this array map.

        return mSize;
public java.lang.StringtoString()
{@inheritDoc}

This implementation composes a string by iterating over its mappings. If this map contains itself as a key or a value, the string "(this Map)" will appear in its place.

        if (isEmpty()) {
            return "{}";
        }

        StringBuilder buffer = new StringBuilder(mSize * 28);
        buffer.append('{");
        for (int i=0; i<mSize; i++) {
            if (i > 0) {
                buffer.append(", ");
            }
            Object key = keyAt(i);
            if (key != this) {
                buffer.append(key);
            } else {
                buffer.append("(this Map)");
            }
            buffer.append('=");
            Object value = valueAt(i);
            if (value != this) {
                buffer.append(value);
            } else {
                buffer.append("(this Map)");
            }
        }
        buffer.append('}");
        return buffer.toString();
public voidvalidate()
The use of the {@link #append} function can result in invalid array maps, in particular an array map where the same key appears multiple times. This function verifies that the array map is valid, throwing IllegalArgumentException if a problem is found. The main use for this method is validating an array map after unpacking from an IPC, to protect against malicious callers.

hide

        final int N = mSize;
        if (N <= 1) {
            // There can't be dups.
            return;
        }
        int basehash = mHashes[0];
        int basei = 0;
        for (int i=1; i<N; i++) {
            int hash = mHashes[i];
            if (hash != basehash) {
                basehash = hash;
                basei = i;
                continue;
            }
            // We are in a run of entries with the same hash code.  Go backwards through
            // the array to see if any keys are the same.
            final Object cur = mArray[i<<1];
            for (int j=i-1; j>=basei; j--) {
                final Object prev = mArray[j<<1];
                if (cur == prev) {
                    throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);
                }
                if (cur != null && prev != null && cur.equals(prev)) {
                    throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);
                }
            }
        }
public VvalueAt(int index)
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.

        return (V)mArray[(index << 1) + 1];
public java.util.Collectionvalues()
Return a {@link java.util.Collection} for iterating over and interacting with all values in the array map.

Note: this is a fairly inefficient way to access the array contents, it requires generating a number of temporary objects.

        return getCollection().getValues();