Android源码系列(13) -- ArrayMap

一、类签名

ArrayMap 是通用的键值对映射数据结构，相比 HashMap 有更高内存利用率。因为 ArrayMap 使用数组结构保存映射：一个整形数组存放哈希值，一个 Object 数组存放 Key 和 Value。

使用数组能避免为每个放入 Map 的entry创建额外对象(对比HashMap#Node)，并能更有力地控制数组扩展的大小。

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

相比传统 HashMap，ArrayMap 速度更慢且不存放大量items的场景。因为ArrayMap通过二分查找搜索item，添加或移除元素需要操作数组的entries。容器仅持有数百个items时，两者性能差距不大。

ArrayMap_HASH_UML

为更平衡的内存利用率，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);
    }
}

五、静态方法

在保存hash的数组中，通过二分查找找出目标hash的索引值

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) {
    if (hashes.length == (BASE_SIZE*2)) {
        // hashes.length == 8
        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;
                array[1] = hashes;
                // 置空数组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
    // 返回这个key的新条目可以直接插入的索引位置，值为负数
    // 方法直接使用哈希链的尾部位置，减少因插入而导致拷贝数组条目的数量
    return ~end;
}

int indexOfNull() {
    final int N = mSize;

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

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

    // 哈希值没有命中，表示此kay没有对应的条目
    if (index < 0) {
        return index;
    }

    // 该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
    // 返回这个key的新条目可以直接插入的索引位置，值为负数
    // 方法直接使用哈希链的尾部位置，减少因插入而导致拷贝数组条目的数量
    return ~end;
}

// 分配数组空间
private void allocArrays(final int size) {
    // 若mHashes为EMPTY_IMMUTABLE_INTS，表示此ArrayMap是不可变的，并抛出异常
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
        throw new UnsupportedOperationException("ArrayMap is immutable");
    }

    if (size == (BASE_SIZE*2)) {
        // size == 8，从缓存中复用数组
        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 为 oldHashes
        final int[] ohashes = mHashes;
        // oarray 为 oldArray 
        final Object[] oarray = mArray;
        // osize 为 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];
}

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

// 根据key的索引在数组中设置新值，已有旧值作为结果返回
public V setValueAt(int index, V value) {
    // 计算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
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        // key和hash查找索引
        index = indexOf(key, hash);
    }

    if (index >= 0) {
        // 已有key在mArray数组的索引
        index = (index<<1) + 1;
        // 取出旧值
        final V old = (V)mArray[index];
        // 数组相同位置存入新值
        mArray[index] = value;
        // 返回旧值
        return old;
    }

    index = ~index;
    if (osize >= mHashes.length) {
        // 计算n值：
        //   1. osize < BASE_SIZE   返回 BASE_SIZE
        //   2. BASE_SIZE <= osize < BASE_SIZE*2 返回 BASE_SIZE*2
        //   3. BASE_SIZE*2 <= osize               返回 osize+(osize>>1)
        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;
    // kay的hash
    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) {
        return;
    }

    int basehash = mHashes[0]; // 初始index为0
    int basei = 0;

    // 先通过检查所有哈希值，看是否重复，如果哈希值不重复就算验证通过
    // 初始i为1，和index为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];
            // 出现相同key
            if (cur == prev) {
                throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur);
            }
            
            // 出现相同key
            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) {
        // 原ArrayMap没有元素，批量插入所有新元素
        if (N > 0) {
            System.arraycopy(array.mHashes, 0, mHashes, 0, N);
            System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
            mSize = N;
        }
    } else {
        // 原ArrayMap有元素，逐个插入新元素
        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) {
    // 旧value的值old
    final Object old = mArray[(index << 1) + 1];
    // 原ArrayMap元素数量
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        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;
}