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()怎么实现,压根不去调你,就不会重复了。
本文分享自 每天学点Android知识 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!