Android源码系列(13) -- ArrayMap

一、类签名

ArrayMap是通用的键值对映射数据结构，相比传统的HashMap有更高的内存利用率。使用数组的数据结构保存映射：一个整形数组存放每项的哈希值，一个Object数组存放键值对。通过使用数组，能避免为每个放入Map的entry创建额外的对象(对比HashMap的Node)，并能更有力地控制数组扩展的大小(扩增数组只需要创建一个新的数组并拷贝元素，不是重建hash map)。

public final class ArrayMap<K, V> implements Map<K, V>

此数据结构不适合用在存放大量items的场景。相比传统HashMap，ArrayMap速度要更慢。因为ArrayMap通过二分查找搜索item，添加或移除元素也需要操作数组的entries。不过容器仅持有的数百个items时，两者的性能差别并不明显，差别不超过50%。

为了更平衡的内存利用率，ArrayMap不像其他的标准 Java 容器类，而是会在items移除的同时缩小数组。现在也不能主动控制数组的缩小，也就是说，设置了capacity，当任意item被移除，数组的大小都会减少到刚好容纳所有item的大小。

源码来自Android 26

二、常量

private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;

// 最低扩容容量
private static final int BASE_SIZE = 4;

// cache size大小
private static final int CACHE_SIZE = 10;

// 特殊的哈希数组值，用来表示container不可变
static final int[] EMPTY_IMMUTABLE_INTS = new int[0];

// 特殊的不可变空ArrayMap常量，主要用于表示空状态
public static final ArrayMap EMPTY = new ArrayMap<>(-1);

三、成员变量

// 缓存小数组对象避免垃圾回收
 // mBaseCache[0]指向列表中的下一个数组
 // mBaseCache[1]指向int[]
static Object[] mBaseCache;
static int mBaseCacheSize;

 // 缓存小数组对象避免垃圾回收
static Object[] mTwiceBaseCache;
static int mTwiceBaseCacheSize;

final boolean mIdentityHashCode;

// 哈希数组
int[] mHashes;

// 存放key-value的数组
Object[] mArray;

// 已保存items数量
int mSize;

MapCollections<K, V> mCollections;

四、构造方法

// 构造空ArrayMap，初始默认容量为0
public ArrayMap() {
    this(0, false);
}

// 根据给定的容量值构造实例
public ArrayMap(int capacity) {
    this(capacity, false);
}

public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;

    if (capacity < 0) {
        // 此实例内容是不可变的，使用常量标记
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
        // 此实例内容可变，但初始大小为0
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        // 根据指定大小进行构造
        allocArrays(capacity);
    }
    // 以保存元素数量为0
    mSize = 0;
}

// 根据给定的map构造实例
public ArrayMap(ArrayMap<K, V> map) {
    this();
    if (map != null) {
        putAll(map);
    }
}

五、静态方法

// 二分查找
private static int binarySearchHashes(int[] hashes, int N, int hash) {
    try {
        return ContainerHelpers.binarySearch(hashes, N, hash);
    } catch (ArrayIndexOutOfBoundsException e) {
        if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
            throw new ConcurrentModificationException();
        } else {
            throw e; // the cache is poisoned at this point, there's not much we can do
        }
    }
}

// 释放hash数组与key-value数组
// 合适的数组不会释放而是缓存起来，下次数组大小合适时复用
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    // hashes.length == 8
    if (hashes.length == (BASE_SIZE*2)) {
        synchronized (ArrayMap.class) {
            // mTwiceBaseCacheSize最多保存10个
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                // 通过链表的方法保存
                array[0] = mTwiceBaseCache;
                array[1] = hashes;
                // 置空数组索引[2，(size<<1)-1]的entry
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mTwiceBaseCache = array;
                mTwiceBaseCacheSize++; // 已保存数量递增
            }
        }
    } else if (hashes.length == BASE_SIZE) { // hashes.length == 4
        synchronized (ArrayMap.class) {
            // mBaseCacheSize最多保存10个
            if (mBaseCacheSize < CACHE_SIZE) {
                array[0] = mBaseCache; // index = 0
                array[1] = hashes;     // index = 1
                // 置空数组index [2，(size<<1)-1]的entry
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                mBaseCache = array;
                mBaseCacheSize++; // 已保存数量递增
            }
        }
    }
}

六、成员方法

// 通过key和hash找索引
int indexOf(Object key, int hash) {
    final int N = mSize;

    // ArrayMap为空，返回~0
    if (N == 0) {
        return ~0;
    }

    // 通过二分查找确认索引值
    int index = binarySearchHashes(mHashes, N, hash);

    // 如果找不到哈希码，表示此key没有对应的Entry
    if (index < 0) {
        return index;
    }

    // 该key和index所表示的'key'匹配，则表示index成功命中
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    // 从index开始，检查后方索引的key是否匹配
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end; // 返回匹配的索引值
    }

    // 从index开始，检查前方索引的key是否匹配
    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;
}

int indexOfNull() {
    final int N = mSize;

    // ArrayMap为空，返回~0
    if (N == 0) {
        return ~0;
    }

    int index = binarySearchHashes(mHashes, N, 0);

    // If the hash code wasn't found, then we have no entry for this key.
    // 哈希值没有命中，表示此kay没有对应的entry.
    if (index < 0) {
        return index;
    }

    // If the key at the returned index matches, that's what we want.
    // 该key和index所表示的'key'匹配，则表示index成功命中
    if (null == mArray[index<<1]) {
        return index;
    }

    // 从index开始，检查后方索引的key是否匹配
    int end;
    for (end = index + 1; end < N && mHashes[end] == 0; end++) {
        if (null == mArray[end << 1]) return end;
    }

    // 从index开始，检查前方索引的key是否匹配
    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;
}

// 分配数组空间
private void allocArrays(final int size) {
    // 若mHashes为EMPTY_IMMUTABLE_INTS，表示此ArrayMap是不可变的，并抛出异常
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
        throw new UnsupportedOperationException("ArrayMap is immutable");
    }
    // size == 8，从缓存中复用数组
    if (size == (BASE_SIZE*2)) {
        synchronized (ArrayMap.class) {
            if (mTwiceBaseCache != null) {
                final Object[] array = mTwiceBaseCache;
                mArray = array;
                // mTwiceBaseCache = mTwiceBaseCache[0]
                mTwiceBaseCache = (Object[])array[0];
                // 取出缓存的hashes赋值给mHashes复用
                mHashes = (int[])array[1];
                // 置空索引0和索引1的空间
                array[0] = array[1] = null;
                // 已缓存数组数量递减
                mTwiceBaseCacheSize--;
                return;
            }
        }
    } else if (size == BASE_SIZE) { // size == 4，从缓存中复用数组
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                // mBaseCache = mBaseCache[0]
                mBaseCache = (Object[])array[0];
                // 取出缓存的hashes赋值给mHashes复用
                mHashes = (int[])array[1];
                // 置空索引0和索引1的空间
                array[0] = array[1] = null;
                // 已缓存数组数量递减
                mBaseCacheSize--;         
                return;
            }
        }
    }
    
    // size大小不是4或8，则就地创建新数组并赋值
    mHashes = new int[size];
    mArray = new Object[size<<1];
}

// 清空所有键值对数据
@Override
public void clear() {
    // 以保存元素数量不为空
    if (mSize > 0) {
        // ohashes i.e oldHashes
        final int[] ohashes = mHashes;
        // oarray i.e oldArray 
        final Object[] oarray = mArray;
        // osize i.e oldSize
        final int osize = mSize;
        // 设置EmptyArray.INT表明为空
        mHashes = EmptyArray.INT;
        // 设置EmptyArray.OBJECT表明为空
        mArray = EmptyArray.OBJECT;
        // 已保存item为0
        mSize = 0;
        // 释放数组空间
        freeArrays(ohashes, oarray, osize);
    }
    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) {
        throw new ConcurrentModificationException();
    }
}

// 清除所有items，但不减少ArrayMap已开辟空间
public void erase() {
    if (mSize > 0) {
        final int N = mSize<<1;
        final Object[] array = mArray;
        for (int i=0; i<N; i++) {
            array[i] = null;
        }
        mSize = 0;
    }
}

// 保证ArrayMap扩容到minimumCapacity个空间
public void ensureCapacity(int minimumCapacity) {
    final int osize = mSize;
    if (mHashes.length < minimumCapacity) {
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        // 创建新数组空间
        allocArrays(minimumCapacity);
        // 迁移items到新数组空间
        if (mSize > 0) {
            System.arraycopy(ohashes, 0, mHashes, 0, osize);
            System.arraycopy(oarray, 0, mArray, 0, osize<<1);
        }
        // 释放旧数组空间
        freeArrays(ohashes, oarray, osize);
    }
    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) {
        throw new ConcurrentModificationException();
    }
}

// 检查key是否包含在数组中
@Override
public boolean containsKey(Object key) {
    return indexOfKey(key) >= 0;
}

 // 返回key在集合中的索引
public int indexOfKey(Object key) {
    return key == null ? indexOfNull()
            : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}

// 检查value在数组中的索引值
int indexOfValue(Object value) {
    final int N = mSize*2;
    final Object[] array = mArray;
    if (value == null) {
        // value为空，则查找第一个值为空的索引
        for (int i=1; i<N; i+=2) { // 每次递增2，保证索引指到值的位置上
            // array[i]匹配null
            if (array[i] == null) {
                return i>>1; // 整形值通过右移1位完成除以2的操作，即i/2
            }
        }
    } else {
        // value不为空，则查找第一个值匹配的索引
        for (int i=1; i<N; i+=2) { // 每次递增2，保证索引指到值的位置上
            // array[i]value
            if (value.equals(array[i])) {
                return i>>1; //  整形值通过右移1位完成除以2的操作，即i/2
            }
        }
    }
    // 集合中没有指定key，返回-1
    return -1;
}

// 检查value是否包含在数组中，此调用会对整个数组进行线性查找
@Override
public boolean containsValue(Object value) {
    return indexOfValue(value) >= 0;
}

// 根据key从数组中获取对应值，没有对应值则返回null
@Override
public V get(Object key) {
    // 根据key算出所在数组的索引值
    final int index = indexOfKey(key);
    // 从索引值取值，若索引值为负数，则返回null
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

// 根据key的索引从数组中取key的实例
public K keyAt(int index) {
    // 根据索引值直接取key
    return (K)mArray[index << 1];
}

// 根据value的索引从数组中取value的实例
public V valueAt(int index) {
    // 根据索引值直接取value
    return (V)mArray[(index << 1) + 1];
}

// 根据key的索引在数组中设置key的新值，如果此索引已有旧值，则作为结果返回
public V setValueAt(int index, V value) {
    index = (index << 1) + 1;
    // 获取旧元素
    V old = (V)mArray[index];
    // 存入新元素
    mArray[index] = value;
    // 返回旧元素
    return old;
}

// 检查数组是否为空
@Override
public boolean isEmpty() {
    return mSize <= 0;
}

// 向ArrayMap中存入新的<Key, value>，如果key有对应的旧value，则旧value会被替换
@Override
public V put(K key, V value) {
    // 原数组元素数量
    final int osize = mSize;
    // 根据变量key算出来的哈希值
    final int hash;
    // 索引值
    int index;
    // key为空则搜索值为空的索引
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        // 通过key计算索引
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        // key和hash查找索引
        index = indexOf(key, hash);
    }
    if (index >= 0) { // 命中已有item
        // 已有key在mArray数组的索引
        index = (index<<1) + 1;
        // 取出旧值
        final V old = (V)mArray[index];
        // 数组相同位置存入新值
        mArray[index] = value;
        // 返回旧值
        return old;
    }

    index = ~index;
    if (osize >= mHashes.length) {
        // osize >= BASE_SIZE*2 的大小为 osize+(osize>>1)
        // BASE_SIZE*2 > osize >= BASE_SIZE 的大小为 BASE_SIZE*2
        // osize < BASE_SIZE 的大小为 BASE_SIZE
        final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1))
                : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;
        allocArrays(n);

        // 检查是否存在并发修改
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }
        
        // ohashes元素全部复制到mHashes
        // oarray元素全部复制到mArray
        if (mHashes.length > 0) {
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
        
        // 释放ohashes和oarray的空间
        freeArrays(ohashes, oarray, osize);
    }

    // 新存入key-value需插入到原有元素之间
    if (index < osize) {
        System.arraycopy(mHashes, index, mHashes, index + 1, osize - index);
        System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
    }

    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS) {
        if (osize != mSize || index >= mHashes.length) {
            throw new ConcurrentModificationException();
        }
    }
    // 数组已创建完毕，且原有元素位置都移动好，则在指定位置放入新key-value
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    // 以保存元素数量递增
    mSize++;
    return null;
}

// 不验证数组是否有足够空间插入key-value
public void append(K key, V value) {
    int index = mSize;
    final int hash = key == null ? 0
            : (mIdentityHashCode ? System.identityHashCode(key) : 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();
        put(key, value);
        return;
    }
    // 空间足够，正常插入key-value
    mSize = index+1;
    // 存入哈希值
    mHashes[index] = hash;
    index <<= 1;
    // 存入key-value
    mArray[index] = key;
    mArray[index+1] = value;
}

// 使用append()会导致array maps失效，尤其是同一个key出现了多次
// 此方法验证array map是有效的，并在出现问题时抛出IllegalArgumentException
public void validate() {
    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;
        }

        // 向前检查看key是否出现重复
        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);
            }
        }
    }
}

// 把array变量中的所有键值对存入实例中
public void putAll(ArrayMap<? extends K, ? extends V> array) {
    // 获取当前实例array长度
    final int N = array.mSize;
    // 确保当前ArrayMap有足够空间保存array的所有元素
    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));
        }
    }
}

 // 从ArrayMap中移除该存在的key和对应的value
@Override
public V remove(Object key) {
    // 根据key查找对应索引
    final int index = indexOfKey(key);
    // 索引值大于0表示key存在
    if (index >= 0) {
        // 移除该key
        return removeAt(index);
    }
    
    // key没有找到，返回null
    return null;
}

// 根据给定的index移除目标键值对，方法结果返回键值对的值
public V removeAt(int index) {
    final Object old = mArray[(index << 1) + 1];
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        // Now empty.
        freeArrays(mHashes, mArray, osize);
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        nsize = 0;
    } else {
        nsize = osize - 1;
        // mHashes.length > 8 && mSize < mHashes.length/3
        if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
            // 缩小数组的空间，并且大小不低于BASE_SIZE*2
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            allocArrays(n);
            
            // 出现并发修改，抛出异常
            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }
            
            if (index > 0) {
                // 从ohashes拷贝[0, index)到mHashes
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                // 从oarray拷贝[0，index << 1)到mArray
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            if (index < nsize) {
                // 从ohashes拷贝剩余items到mHashes
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                // 从oarray拷贝剩余items到mArray
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
        } else {
            if (index < nsize) {
                // mHashes数组，index后的hash逐个前移一位
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                // mArray数组，(index + 1) << 1后的元素前移
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                        (nsize - index) << 1);
            }
            // mArray最后两个空间置空 
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    // 检查是否存在并发修改
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }
    mSize = nsize;
    return (V)old;
}

// 返回ArrayMap保存的键值对数量
@Override
public int size() {
    return mSize;
}

// 检查元素和本实例是否等同
@Override
public boolean equals(Object object) {
    // 为同一个对象返回false
    if (this == object) {
        return true;
    }
    
    // 先检查对象object是否为Map的子类，不是则无法进行比较，返回false
    if (object instanceof Map) {
        Map<?, ?> map = (Map<?, ?>) object;
        // 先检查元素数量，以便快速确认失败并返回false
        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) {
            // 比较过程中元素类型转换抛出异常，返回false
            return false;
        }
        // 两个map的元素完全相同，返回true
        return true;
    }
    // 两个map的元素不完全相同，返回false
    return false;
}

七、集合操作

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 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;
}

// 检查ArrayMap是否包含collection中全部元素
public boolean containsAll(Collection<?> collection) {
    return MapCollections.containsAllHelper(this, collection);
}

// 把map变量中的所有键值对存入实例中
@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());
    }
}

// 移除ArrayMap中与collection共有的元素
public boolean removeAll(Collection<?> collection) {
    return MapCollections.removeAllHelper(this, collection);
}

// 仅保留ArrayMap中与collection共有的元素
public boolean retainAll(Collection<?> collection) {
    return MapCollections.retainAllHelper(this, collection);
}

// 返回一个包含ArrayMap所有键值对的集合
@Override
public Set<Map.Entry<K, V>> entrySet() {
    return getCollection().getEntrySet();
}

// 返回一个包含ArrayMap所有key的集合
@Override
public Set<K> keySet() {
    return getCollection().getKeySet();
}

// 返回一个包含ArrayMap所有value的集合
@Override
public Collection<V> values() {
    return getCollection().getValues();
}

• 上一篇

  Android源码系列(12) -- SharedPreferences