ArrayMap数据结构分析
ArrayMap数据结构分析
ArrayMap是Android上特有的一个性能比较高的Map，和HashMap一样，也实现了Map接口。
这里只分析其数据结构部分，不分析其高效缓存部分。
分析
ArrayMap的结构是int[] mHashes，记录每个key的hash值；Object[] mArray记录Key和Value，对于每一组Key和Value，按照Key和Value的顺序排列。
put(K,V)时，首先根据K计算出来一个Hash值，然后在mHashes中使用二分查找来查找这个Hash值，既然能使用二分查找也就是说，这个mHashs数组是有序的，得到了index后，再在mArray中查找，其中index2表示key的位置，index2+1表示value的位置。
mHashes虽然是个有序的，但却是可以重复的；对于重复的mHashs，在mArray中进行匹配时是通过Key#equals()方法来判断是否相同的。
举个例子：
class SameHashObj(val num:Int){
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (other !is SameHashObj) return false
if (num != other.num) return false
return true
}
override fun hashCode(): Int {
return num%4
}
}SameHashObj持有一个int，equals就是比较num值是否相同；而hashCode()这里为了测试，对4取了个模。
进行下列代码：
val arrayMap=ArrayMap<SameHashObj,String>()
arrayMap[SameHashObj(0)] = "0"
arrayMap[SameHashObj(1)] = "1"
arrayMap[SameHashObj(2)] = "2"
arrayMap[SameHashObj(3)] = "3"
arrayMap[SameHashObj(4)] = "4"最终结构是这样的：
对于SameHashObj(0)和SameHashObj(4)，虽然hashCode都是0，但是其equals却不同，所以会出现上面的现象。
多说一点
ArrayMap一共有三个构造方法，其中有一个是hide的，如下：
public ArrayMap() {
this(0, false);
}
/**
* Create a new ArrayMap with a given initial capacity.
*/
public ArrayMap(int capacity) {
this(capacity, false);
}
/** {@hide} */
public ArrayMap(int capacity, boolean identityHashCode) {
mIdentityHashCode = identityHashCode;
// If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS
// instance instead of the usual EmptyArray.INT. The reference
// is checked later to see if the array is allowed to grow.
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;
}区别就是identityHashCode这个值的定义问题，我们一般能用到的就是false。下面试着用反射来初始化一个为true的ArrayMap，看看有啥变化。
结构如下图了：
可以看到mHashes数组，那是个啥鬼？
这个identityHashCode到底是啥作用呢？看名字，应该可以猜得出来，对于默认的情况，是允许mHashes中出现相同的值的，比如说上面的情况。
put()方法中有如下代码：
public V put(K key, V value) {
final int osize = mSize;
final int hash;
int index;
if (key == null) {
hash = 0;
index = indexOfNull();
} else {
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);
}
...
}如果mIdentityHashCode=true，那么会使用System.identityHashCode(key)来计算Key的hashCode，否则就是key的hashCode方法。
对于默认的情况，就会调用SameHashObj重写的hashCode()方法；对于true的情况下，最终会调用到没有重写hashCode()的情况，而默认的hashCode()方法返回的是每个对象的内存地址，所以自然每个不同的对象都是不同的，不管你hashCode()怎么实现，压根不去调你，就不会重复了。
参考
- ArrayMap
- 深度解读ArrayMap优势与缺陷
- 深入剖析 Android中的 ArrayMap