结构图

clipboard.png

public ArrayMap(int capacity, boolean identityHashCode) {
    mIdentityHashCode = identityHashCode;
    
    if (capacity < 0) {
        mHashes = EMPTY_IMMUTABLE_INTS;
        mArray = EmptyArray.OBJECT;
    } else if (capacity == 0) {
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
    } else {
        allocArrays(capacity);
    }
    mSize = 0;
}

初始化数组

private void allocArrays(final int size) {
    mHashes = new int[size];
    "实体数组的长度是hash数组的2倍"
    mArray = new Object[size<<1];

put部分

@Override
public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;
    "identityHashCode只是用来禁用hashcode覆盖"
    hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
    "查看该key在哪个位置或插入哪个位置"
    index = indexOf(key, hash);

关于hashcode禁止覆盖

public static int identityHashCode(Object x) {
    if (x == null) {
        return 0;
    }
    
    return Object.identityHashCode(x);
}
"hashcode的默认实现就是identityHashCode，如果有人覆盖了
hashcode方法，则用mIdentityHashCode =true可以解决"
public int hashCode() {
    return identityHashCode(this);
}

indexof

int indexOf(Object key, int hash) {
    "通过二分法查找位置"
    int index = binarySearchHashes(mHashes, N, hash);

二分查找

private static int binarySearchHashes(int[] hashes, int N, int hash) {
    "通过工具类二分法查找"
   return ContainerHelpers.binarySearch(hashes, N, hash);
}
static int binarySearch(int[] array, int size, int value) {
    "低位"
    int lo = 0;
    "高位"
    int hi = size - 1;
    while (lo <= hi) {
        "中间位"
        final int mid = (lo + hi) >>> 1;
        "拿中间值"
        final int midVal = array[mid];
        "中间值比要的值小则取右边"
        if (midVal < value) {
            lo = mid + 1;
            "中间值比要的值大取左边"
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            return mid;  // value found
        }
    }
    "如果没找到，返回他要被插入的位置取反
取反的目的是告诉调用方每找到，
但是你下次插入的时候可以用这个位置"
    return ~lo;  // value not present
}

查找后的处理

int indexOf(Object key, int hash) {
    
    "要么是找到的索引，要么是~插入的索引"
    int index = binarySearchHashes(mHashes, N, hash);
   "不存在就返回索引的取反"
    if (index < 0) {
        return index;
    }
    "存在返回真实值的索引"
    if (key.equals(mArray[index<<1])) {
        return index;
    }

    "key的hashcode重复了,向后查【1，2，2，2，2，3】的情况，mid=2先向后查，再向前查，查到返回"
    // 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.
    "此时返回的end是最后一个2的位置后面取反，也是要插入的位置"
    return ~end;
}

put之二

@Override
public V put(K key, V value) {
    "index<0取反就是要插入的位置，否则就是找到了"
    if (index >= 0) {
        index = (index<<1) + 1;
        "替换就行了"
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }
    "没找到就把要插入的位置算出来"
    index = ~index;

扩容逻辑 1.5倍

@Override
public V put(K key, V value) {
    //ignore
    "判断要不要扩容比如上次已经满了"
    if (osize >= mHashes.length) {
        "大于base_size*2的情况就是1。5倍扩容"
        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);
        "检查并发处理异常 调用该方法之前osize=mSize，如果不相等，说明这个方法没走完就有人改了"
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }
    
        if (mHashes.length > 0) {
            if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0");
            "copy"
            System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
            System.arraycopy(oarray, 0, mArray, 0, oarray.length);
        }
    
        freeArrays(ohashes, oarray, osize);
    }

数组腾出位置

@Override
public V put(K key, V value) {
    "给index后面的数组往后挪一个空格[1,2,3,4,]->[1,2, ,3,4]"
    if (index < osize) {
        if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index)
                + " to " + (index+1));
        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();
        }
    }
    "index赋植"
    mHashes[index] = hash;
    mArray[index<<1] = key;
    mArray[(index<<1)+1] = value;
    mSize++;

get

@Override
public V get(Object key) {
    "找到要索引，>=0表示取到，小于0表示没找到"
    final int index = indexOfKey(key);
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}
@Override
public int indexOfKey(Object key) {
    return key == null ? indexOfNull()
    "indexof还是二分法找，如果找到了key值相同就返回，key值不同hash一样就向前向后遍历，所以相同hash越多，性能越差"
            : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}