首页 > 热点专题

ArrayMap数据结构分析

文章作者:来源:www.maiyard.com.cn时间:2020-03-16



ArrayMap是安卓系统上一个独特的高性能地图,和HashMap一样,它也实现了地图界面。

这里只分析它的数据结构,而不是它的高效缓存。

analyze

ArrayMap的结构是在[] mHashes中,记录每个键的哈希值;对象[] mArray记录键和值,对于每组键和值,它们按键和值的顺序排列。当

put(K,V)时,首先根据K计算一个散列值,然后使用二进制搜索在mHashes中找到散列值。因为可以使用二进制搜索,也就是说,这个mhass数组是有序的,所以在获得索引之后,在mArray中进行搜索,其中index2表示键的位置,index2 1表示值的位置。

mHashes是有序的,但可重复;对于重复的mHashs,在mArray中匹配时,使用Key#equals()方法来判断它们是否相同。

例如:

SameHashObj持有一个整数,等于是比较数字值是否相同;这里的hashCode()用一个模块4进行测试。

执行下面的代码:

最终的结构是这样的:

对于SameHashHobJ(0)和SameHashHobJ(4),虽然hashCode是0,但它的等号是不同的,所以出现了上述现象。

say more

ArrayMap有三种构造方法,其中一种是隐藏,如下所示:

区别在于identityHashCode的定义是错误的。让我们尝试初始化一个反射为真的数组映射,看看发生了什么变化。

结构如下图所示:

MHAsSe数组可见。那是什么鬼?

这个身份哈希码到底在做什么?看名字,应该能猜到,对于默认情况,是允许相同的值出现在mHashes中,比如上面的情况。

put()方法有以下代码:

如果mIdentityHashCode=true,那么System.identityHashCode(键)将用于计算键的HashCode,否则它就是键的HashCode方法。

默认情况下,将调用由SameHashObj重写的hashCode()方法;在true的情况下,最终将在不重写hashCode()的情况下调用它。默认的hashCode()方法返回每个对象的内存地址,因此每个不同的对象自然是不同的。无论如何实现hashCode(),如果不进行任何调整,都不会重复。

参考

ArrayMap

深入了解ArrayMap

的优缺点,深入分析ArrayMap

在安卓系统中的应用,关注我的技术公开号码,和你一起学习。微信可以通过扫描下面的二维码发现:

-