Android ArrayMap 源码详解

分析源码之前先来介绍一下ArrayMap的存储结构,ArrayMap数据的存储不同于HashMap和SparseArray,在上一篇《Android SparseArray源码详解》中我们讲到SparseArray是以纯数组的形式存储的,一个数组存储的是key值一个数组存储的是value值,今天我们分析的ArrayMap和SparseArray有点类似,他也是以纯数组的形式存储,不过不同的是他的一个数组存储的是Hash值另一个数组存储的是key和value,其中key和value是成对出现的,key存储在数组的偶数位上,value存储在数组的奇数位上,我们先来看其中的一个构造方法

当capacity不为0的时候调用allocArrays方法分配数组大小,在分析allocArrays源码之前,我们先来看一下freeArrays方法,

BASE_SIZE的值为4,ArrayMap对于hashes.length为4和8的两种情况会进行缓存,上面的两种情况下原理都是一样的,我们就用下面的一种情况进行分析,缓存的数量也不是无线大的,当大于等于10(CACHE_SIZE)的时候也就不再进行缓存了,缓存的原理就是让array数组的第一个位置保存之前缓存的mBaseCache,第二个位置保存当前的hashes数组,其他的全部置为空,下面我们再来看一下之前的allocArrays方法,

如果分配的尺寸不为4或者8,就初始化,我们看到最下面两行mArray的大小是mHashes的两倍,这是因为mArray存储的是key和value两个值。如果分配的尺寸为4或者8,就判断之前对这两种情况是否进行了缓存,如果缓存过就从缓存中取,取出来的时候会把array的值置空,在上面的freeArrays方法中我们知道array的第一个位置和第二个位置保存的有值,其他的都置为空,在这里把array[0]和array[1]也置为了空,但是有一点奇葩的地方就是mHashes的值确保留了下来,无论是在freeArrays方法中还是在allocArrays方法中,都没有把他置为默认值。通过ArrayMap的源码发现,这里mHashes的值无论改不改变基本上都没有什么太大影响,因为put的时候如果存在就被替换了,但在indexOf的方法中如果存在还要在继续比较key的值,只有hash和key都一样才会返回。我们下面来看一下indexOf(Object key, int hash)这个方法,

这个方法很简单,就是根据二分法查找来确定hash值在数组中的位置,如果没找到就返回一个负数,注意下面还有两个循环,这是因为mHashes数组中的hash值不是唯一的,只有hash值相同并且key也相同才会返回所在的位置,否则就返回一个负数。下面就来看一下put(K key, V value)这个方法。

还有clear()方法和erase()方法,这两个区别就是clear()把所有的数据清空,并释放空间,erase()清空数据但没有释放空间,并且erase()只清mArray数据,mHashes数据并没有清空,这就是上面讲到的mHashes即使没清空也不会有影响,代码比较少就不在看了。在看一下和put类似的一个方法append(K key, V value)

我们看注释这个方法是隐藏的,没有开放,因为这个方法不稳定,如果调用可能就会出现问题,看上面的注释,意思是说这个方法存储数据的时候没有验证,因为在最后存储的时候,是直接存进去的,这就会有一个问题,如果之前存过相同的key和value,再调用这个方法,很可能会再次存入,就可能会有两个key和value完全一样的,我个人认为如果把上面的if (index > 0 && mHashes[index-1] > hash)改为if (index > 0 && mHashes[index-1] >= hash)应该就没问题了,因为如果有相同的就调用put方法把原来的替换,不明白他为什么要这样写,下面再看一个方法validate()

看上面的注释也是隐藏的,存储的时候可能会存在多个相同的key,这个方法就是用来验证的,这个方法很好理解,因为我们存储数据的时候是按照二分法查找然后存储的,如果hash值相同,那么存储的时候肯定是挨着的,在这里进行验证,对挨着相同hash值的数据进行key比较,如果key相同,则说明已经存在了,就会报异常。我们再来看最后一个方法

剩下的方法都比较简单,这里就不在一一分析。

1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部