ArrayMap

结构：

1.int[] mHashs，存储元素的hashCode()，数组内元素有序.

2.Object[] mArray，存储Key,Value，Key，Value ，不需要额外的Entry结构

// 二分查找，找hash 在hashes中的位置，没找到时index <0
private static int binarySearchHashes(int[] hashes, int N, int hash) {}

找到后 比较 那个位置的key 是否与put进来的key相同，相同则修改，不同则发生冲突

put

putput(K key, V value)

1. 计算index，表示key在mHashs中的位置或应该插入的位置
2. 如果oldsize 大于等于 mHashs的长度，则进行扩容，并拷贝原来的数据到新开的2个数组中,并调用freeArray
3. 如果index没有超过oldsize，将index及后面的元素往后挪
4. 判断是否并发操作产生了异常
5. mHashs 和mArray插入，size++

hash就是key.hashCode()

找到的hash的Index为0，但是key发生冲突 。算出的Index 为1 ,返回~1 ，就是-2。

oSize < mHashes.length ( 1 < 4)

index 不小于 osize ( 1 不小于 1)

直接在Index处插入

get

public V getpublic V get(Object key) {
	final int index = indexOfKey(key);
    return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}

仍然是二分查找，找不到返回Null。

remove

public V remove(public V remove(Object key) {
        final int index = indexOfKey(key);
        if (index >= 0) {
            return removeAt(index);
        }

        return null;
}
public V removeAt(int index) {...}

• 如果oldSize为1(删之前就1个元素)，。。。
• mHashes长度大于8时
• mHashes长度小于8时
  • 如果删除的是最后一个元素，仅将size–，mArray对应2个位置赋值为null即可
  • 如果删除的不是最后一个元素，还需要将待删除位置index后面的元素全部往前挪一个位置，包括mHashs和mArray

原来mHashs数组中元素个数 oSize >= mHashes.length 时

进行扩容allocArrays(final int size) {}。

• oSize >= 2 * 4 1.5倍扩容，

• 4 <= oSize < 8 扩容为8;

• oSize < 4 扩容为4

容量	0	0~3	4~7	8~	12
mHashs	0	4	8	12	18
mArray	0	4	8	12	18

扩容后拷贝。

如何保证有序的？

通过indexof方法，二分查找，找不到时 ，返回的是将要插入的位置. 找不到的时候返回的是负数。

freeArrays()

freeArrays(final int[] hashes, final Object[] array, final int freeArrays(final int[] hashes, final Object[] array, final int size) {}