ArrayMap 源码分析

ArrayMap结构

arrayMap中主要存储的数据的是两个数据

int[] mHashes; // 存储出的是每个key的hash值，并且在这些key的hash值在数组当中是从小到大排序的。
Object[] mArray; // 长度是mHashs的两倍，每两个元素分别是key和value，这两元素对应mHashs中的hash值。

    //如果key存在，则返回oldValue
    public V put(K key, V value) {
        //key的hash值
        final int hash;
        //下标
        int index;
        // 如果key为null，则hash值为0.
        if (key == null) {
            hash = 0;
            //寻找null的下标
            index = indexOfNull();
        } else {
            //根据mIdentityHashCode 取到 hash值
            hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
            //根据hash值和key 找到合适的index
            index = indexOf(key, hash);
        }
        //如果index>=0,说明是替换（改）操作
        if (index >= 0) {
            //只需要更新value 不需要更新key。因为key已经存在
            index = (index<<1) + 1;
            //返回旧值
            final V old = (V)mArray[index];
            mArray[index] = value;
            return old;
        }
        //index<0,说明是插入操作。 对其取反，得到应该插入的下标
        index = ~index;
        //如果需要扩容
        if (mSize >= mHashes.length) {
            //如果容量大于8，则扩容一半。
            //否则容量大于4，则扩容到8.
            //否则扩容到4
            final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
                    : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
            //临时数组
            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);
        }
        //如果index在中间，则需要移动数组，腾出中间的位置
        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);
        }
        //hash数组，就按照下标存哈希值
        mHashes[index] = hash;
        //array数组，根据下标，乘以2存key，乘以2+1 存value
        mArray[index<<1] = key;
        mArray[(index<<1)+1] = value;
        mSize++;//修改size
        return null;
    }

    //根据key和key的hash值，返回index
    int indexOf(Object key, int hash) {
        //N为当前集合size 
        final int N = mSize;
        //如果当前集合是空的，返回~0
        if (N == 0) {
            return ~0;
        }
        //根据hash值，通过二分查找，查找到目标index
        int index = ContainerHelpers.binarySearch(mHashes, N, hash);
        //如果index《0，说明该hash值之前没有存储过数据
        if (index < 0) {
            return index;
        }
        //如果index>=0,说明该hash值，之前存储过数据，找到对应的key，比对key是否相等。相等的话，返回index。说明要替换。
        if (key.equals(mArray[index<<1])) {
            return index;
        }
        //以下两个for循环是在出现hash冲突的情况下，找到正确的index的过程：
        //从index+1,遍历到数组末尾，找到hash值相等，且key相等的位置，返回
        int end;
        for (end = index + 1; end < N && mHashes[end] == hash; end++) {
            if (key.equals(mArray[end << 1])) return end;
        }

        //从index-1,遍历到数组头，找到hash值相等，且key相等的位置，返回
        for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
            if (key.equals(mArray[i << 1])) return i;
        }
        // key没有找到，返回一个负数。代表应该插入的位置
        return ~end;
    }

扩容优化

freeArrays方法中，传入的是oldhashes和oldarray，和新的mSize。当长度不够用，我们需要废弃掉老的数组，使用新的数组的时候，把老的数组句柄（包含mHashes和mArray）的数据缓存到 mArray 的前两个位置，其他的数据清空，如果长度是 4，则使用 mBaseCache，如果是 8 ，则使用 mTwiceBaseCache。
这些缓存空间是留给其它的ArrayMap的，而不是当前的ArrayMap的。

最后编辑于：2019.06.04 22:10:31