ArrayMap源码解析

public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> {
    MapCollections<K, V> mCollections;

    public ArrayMap() {
        super();
    }

    /**
     * 给定大小的ArrayMap
     */
    public ArrayMap(int capacity) {
        super(capacity);
    }

    /**
     * 通过一个ArrayMap或者SimpleArrayMap来实现一个ArrayMap
     */
    public ArrayMap(SimpleArrayMap map) {
        super(map);
    }

    /**
     * 得到Map集合
     */
    private MapCollections<K, V> getCollection() {
        if (mCollections == null) {
            mCollections = new MapCollections<K, V>() {
                @Override
                protected int colGetSize() {
                    return mSize;
                }

                //mArray存的是值，该变量在SimpleArrayMap中
                @Override
                protected Object colGetEntry(int index, int offset) {
                    return mArray[(index<<1) + offset];
                }

                //通过key得到位置索引
                @Override
                protected int colIndexOfKey(Object key) {
                    return indexOfKey(key);
                }

                //通过value得到位置索引
                @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;
    }

    /**
     * 通过调用MapCollections的containsAllHelper来判断该ArrayMap是否包含collection
     */
    public boolean containsAll(Collection<?> collection) {
        return MapCollections.containsAllHelper(this, collection);
    }

    /**
     * 将Map的类中的内容添加到ArrayMap中
     */
    @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());
        }
    }

    /**
     * 通过调用MapCollections的removeAllHelper来除掉collection中有的值
     */
    public boolean removeAll(Collection<?> collection) {
        return MapCollections.removeAllHelper(this, collection);
    }

    /**
     * 取ArrayMap和collection的交集
     */
    public boolean retainAll(Collection<?> collection) {
        return MapCollections.retainAllHelper(this, collection);
    }

    /**
     * 返回一个set用来遍历，注意：这是一个小效率非常低的方法，会产生很多平时变量
     *
     * Note: the semantics of this
     * Set are subtly different than that of a HashMap: most important,
     * the 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 Iterator.next.
     */
    @Override
    public Set<Entry<K, V>> entrySet() {
        return getCollection().getEntrySet();
    }

    /**
     * 返回一个set用来遍历key，注意：这是一个小效率非常低的方法，会产生很多平时变量
     */
    @Override
    public Set<K> keySet() {
        return getCollection().getKeySet();
    }

    /**
     * 返回一个Collections用来遍历value，注意：这是一个小效率非常低的方法，会产生很多平时变量
     */
    @Override
    public Collection<V> values() {
        return getCollection().getValues();
    }
}

public class SimpleArrayMap<K, V> {
  
    /**
     * 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;
  
    int[] mHashes;
    Object[] mArray;
    int mSize;

    /**
     * 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;
  
    /**
     * 创建一个空的ArrayMap，默认容量是0
     */
    public SimpleArrayMap() {
        mHashes = ContainerHelpers.EMPTY_INTS;//static final int[] EMPTY_INTS = new int[0];
        mArray = ContainerHelpers.EMPTY_OBJECTS;// static final Object[] EMPTY_OBJECTS = new Object[0];
        mSize = 0;
    }

    /**
     * 创建一个给定容量的ArrayMap
     */
    public SimpleArrayMap(int capacity) {
        if (capacity == 0) {
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
        } else {
            allocArrays(capacity);
        }
        mSize = 0;
    }

    /**
     * 通过一个ArrayMap来创建一个新的ArrayMap
     */
    public SimpleArrayMap(SimpleArrayMap map) {
        this();
        if (map != null) {
            putAll(map);
        }
    }
  
    /**
     * 扩容，分配新的数组
     */
 private void allocArrays(final int size) {
        //如果是8
        if (size == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
    //如果mTwiceBaseCache不为null
                if (mTwiceBaseCache != null) {
                 //将mTwiceBaseCache赋值给mArray
                    final Object[] array = mTwiceBaseCache;
                    mArray = array;
                    //将之前保存在0和1的拿出来
                    mTwiceBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    //清空
                    array[0] = array[1] = null;
                    mTwiceBaseCacheSize--;
                    return;
                }
            }
        } else if (size == BASE_SIZE) {//如果是4
            synchronized (ArrayMap.class) {
    //如果mBaseCache不为null
                if (mBaseCache != null) {
                 //将mBaseCache赋值给mArray
                    final Object[] array = mBaseCache;
                    mArray = array;
                    //将之前保存在0和1的拿出来
                    mBaseCache = (Object[])array[0];
                    mHashes = (int[])array[1];
                    //清空
                    array[0] = array[1] = null;
                    mBaseCacheSize--;
                    return;
                }
            }
        }
  //创建mHashes数组和mArray数组
        mHashes = new int[size];
        mArray = new Object[size<<1];
    }
  
    public void putAll(SimpleArrayMap<? extends K, ? extends V> array) {
        final int N = array.mSize;
        //确认目前数组放的下
        ensureCapacity(mSize + N);
        //当前数组没有值
        if (mSize == 0) {
            if (N > 0) {//将内容复制到mHash和mArray中
                System.arraycopy(array.mHashes, 0, mHashes, 0, N);
                System.arraycopy(array.mArray, 0, mArray, 0, N<<1);
                mSize = N;
            }
        } else {//如果原来就有值，那么直接通过for循环将信息写入
            for (int i=0; i<N; i++) {
                put(array.keyAt(i), array.valueAt(i));
            }
        }
    }
  
    /**
     * 判断目前数组是否够大
     */
    public void ensureCapacity(int minimumCapacity) {
        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);
        }
    }
  
 private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
        //如果是8
        if (hashes.length == (BASE_SIZE*2)) {
            synchronized (ArrayMap.class) {
                //此时mTwiceBaseCacheSize值为0，必然小于CACHE_SIZE
                if (mTwiceBaseCacheSize < CACHE_SIZE) {
                 //将现有的mTwiceBaseCache赋值给数组的第一个
                    array[0] = mTwiceBaseCache;
                    array[1] = hashes;
     //清除剩下的
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    //将数组赋值给mTwiceBaseCache，就是将mTwiceBaseCache替换掉了，原来的mTwiceBaseCache在该数组的第0位置上
                    mTwiceBaseCache = array;
                    mTwiceBaseCacheSize++;
                }
            }
        } else if (hashes.length == BASE_SIZE) {//如果是4
            synchronized (ArrayMap.class) {
                if (mBaseCacheSize < CACHE_SIZE) {
                 //将mBaseCache赋值给数组的第一个
                    array[0] = mBaseCache;
                    array[1] = hashes;
                    //清除剩下的
                    for (int i=(size<<1)-1; i>=2; i--) {
                        array[i] = null;
                    }
                    //将数组赋值给mBaseCache
                    mBaseCache = array;
                    mBaseCacheSize++;
                }
            }
        }
    }
}

public class SimpleArrayMap<K, V> {
  
    public V put(K key, V value) {
        //当前值的hash
        final int hash;
        //当前值的索引
        int index;
        if (key == null) {//如果key为null，那么hash为0
            hash = 0;
            index = indexOfNull();//找得到返回正数，找不到返回负数
        } else {//如果key不为null，那么hash就是keyhashCode值
            hash = key.hashCode();
            index = indexOf(key, hash);//找得到返回正数，找不到返回负数
        }
        //如果index的值是大于等于0的
        if (index >= 0) {
         //index*2+1，即value的位置
            index = (index<<1) + 1;
            //得到旧的value
            final V old = (V)mArray[index];
            //将新的value赋值进去
            mArray[index] = value;
            //返回旧的value
            return old;
        }
  //如果index为负，那么这里变为正数
        index = ~index;
        if (mSize >= mHashes.length) {//现有的值的数量与hash数组大小对比
         //mSize如果大于等于8，那么n=mSize+mSize/2;如果mSize小于8且大于等4，n=8；如果mSize小于4，n=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) {
                System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
                System.arraycopy(oarray, 0, mArray, 0, oarray.length);
            }
   //释放
            freeArrays(ohashes, oarray, mSize);
        }
  //将index后面的内容往后面移
        if (index < mSize) {
            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;
    }
  
    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;
        }
  //二分查找hash值对应的key
        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.
        //如果找到，判断key是否正确
        if (key.equals(mArray[index<<1])) {
            return index;
        }

        //找对应的key
        // 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;
    }

    int indexOfNull() {
        final int N = mSize;

        // Important fast case: if nothing is in here, nothing to look for.
        if (N == 0) {
            return ~0;
        }
  //二分查找hash值对应的key
        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.
        //如果找到，判断key是否正确
        if (null == mArray[index<<1]) {
            return index;
        }

        //找对应的key
        // 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;
    }
}

public class SimpleArrayMap<K, V> {

    public V removeAt(int index) {
        final Object old = mArray[(index << 1) + 1];
        if (mSize <= 1) {//清空
            freeArrays(mHashes, mArray, mSize);
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.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);
                //临时变量存放旧hash数组和array数组
                final int[] ohashes = mHashes;
                final Object[] oarray = mArray;
                //分配新的数组
                allocArrays(n);

                mSize--;
                //将原先的数组的index之前的值传进去
                if (index > 0) {
                    System.arraycopy(ohashes, 0, mHashes, 0, index);
                    System.arraycopy(oarray, 0, mArray, 0, index << 1);
                }
                //要删除的index值小于现在的大小
                if (index < mSize) {
                    //将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) {
                    //将index后面的往前移
                    System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
                    System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1,
                            (mSize - index) << 1);
                }
                //对应的位置设为null
                mArray[mSize << 1] = null;
                mArray[(mSize << 1) + 1] = null;
            }
        }
        return (V)old;
    }
}

public class SimpleArrayMap<K, V> {

    //清空
    public void clear() {
        if (mSize != 0) {
            freeArrays(mHashes, mArray, mSize);
            mHashes = ContainerHelpers.EMPTY_INTS;
            mArray = ContainerHelpers.EMPTY_OBJECTS;
            mSize = 0;
        }
    }
  
    //是否包含这个key
    public boolean containsKey(Object key) {
        return indexOfKey(key) >= 0;
    }
  
    //key的索引
    public int indexOfKey(Object key) {
        return key == null ? indexOfNull() : indexOf(key, key.hashCode());
    }
  
    //value的索引 
    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;
    }
  
    //是否包含这个value
    public boolean containsValue(Object value) {
        return indexOfValue(value) >= 0;
    }
  
    //通过key得到value
    public V get(Object key) {
        final int index = indexOfKey(key);
        return index >= 0 ? (V)mArray[(index<<1)+1] : null;
    }
  
    //得到index索引位置上的key
    public K keyAt(int index) {
        return (K)mArray[index << 1];
    }

    //得到index索引上的value
    public V valueAt(int index) {
        return (V)mArray[(index << 1) + 1];
    }
  
    //设置index索引上的value
    public V setValueAt(int index, V value) {
        index = (index << 1) + 1;
        V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    //通过key来删除
    public V remove(Object key) {
        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }
        return null;
    }
  
    //大小
    public int size() {
        return mSize;
    }
}