公众号:字节数组
希望对你有所帮助 🤣🤣
本系列文章会陆续对 Java 和 Android 的集合框架(JDK 1.8,Android SDK 30)中的几个常见容器结合源码进行介绍,了解不同容器在数据结构、适用场景、优势点 上的不同,希望对你有所帮助 🤣🤣
本篇文章再来分析下 SparseArray 和 ArrayMap 这两个 Android 系统独有的集合框架类,这两个容器在使用上类似于 HashMap,都是用于存储键值对。由于 Android 系统对于内存比较敏感,所以 SparseArray 和 ArrayMap 在内存使用方面会比较克制,这里就来分析下其实现原理和优势点
一、SparseArray 使用 Android Studio 的同学可能遇到过一个现象,就是如果在代码中声明了 Map<Integer,Object>
类型变量的话,Android Studio 会提示:Use new SparseArray<Object>(...) instead for better performance ...
,即用 SparseArray< Object > 性能更优,可以用来替代 HashMap
这里就来介绍下 SparseArray 的内部原理,看看它相比 HashMap 有什么性能优势
1、基本概念 SparseArray 的使用方式:
1 2 3 4 5 SparseArray<String> sparseArray = new SparseArray <>(); sparseArray.put(100 ,"leavesC" ); sparseArray.remove(100 ); sparseArray.get(100 ); sparseArray.removeAt(29 );
SparseArray< E > 相当于 Map< Integer , E > ,key 值固定为 int 类型,在初始化时只需要声明 value 的数据类型即可,其内部用两个数组分别来存储 key 和 value:int[] mKeys ; Object[] mValues
mKeys 和 mValues 按照如下规则对应起来:
假设要向 SparseArray 存入 key 为 10,value 为 200 的键值对,则先将 10 存到 mKeys 中,假设 10 在 mKeys 中对应的索引值是 2,则将 value 存入 mValues[2] 中
mKeys 中的元素值按照递增的方法进行存储,每次存放新的键值对时都通过二分查找的方式将 key 插入到 mKeys 中
当要从 SparseArray 取值时,先通过二分查找法找到 key 在 mKeys 中对应的索引,然后根据该索引从 mValues 中取值
从以上可以看出来的一点就是:SparseArray 避免了 HashMap 每次存取值时的装箱拆箱操作,key 值保持为基本数据类型 int,减少了性能开销
2、类声明 SparseArray 本身并没有直接继承于任何类,内部也没有使用到 Java 原生的集合框架,所以 SparseArray 是 Android 系统自己实现的一个集合容器类
1 public class SparseArray <E> implements Cloneable
3、全局变量 mGarbage
是 SparseArray 的一个优化点之一,用于标记当前是否有需要垃圾回收(GC)的元素 ,当该值被置为 true 时,意味着当前存在无效元素,需要进行垃圾回收,但回收操作并不会马上进行,而是在后续操作中再统一进行
1 2 3 4 5 6 7 8 9 10 11 12 13 14 private static final Object DELETED = new Object ();private boolean mGarbage = false ;private int [] mKeys;private Object[] mValues;private int mSize;
4、构造函数 key 数组和 value 数组的默认大小都是 10,如果在初始化时已知最终数据量的大小,则可以直接指定初始容量,这样可以避免后续的扩容操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public SparseArray () { this (10 ); } public SparseArray (int initialCapacity) { if (initialCapacity == 0 ) { mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int [mValues.length]; } mSize = 0 ; }
5、添加元素 添加元素的方法有几个,主要看 put(int key, E value)
方法就可以,该方法用于存入 key 和 value 组成的键值对
按照前面所说的 SparseArray 存储键值对的规则,put
方法会先判断当前 mKeys 中是否已经有相同的 key 值,有的话就用 value 覆盖 mValues 中的旧值。如果不存在相同 key 值,在将 key 插入到 mKeys 后需要在 mValues 的相同索引位置插入 value。由于 mKeys 是按照大小对元素值进行排序存储的,所以将 key 插入到 mKeys 可能会导致元素重新排序,从而连锁导致 mValues 也需要重新排序
put
方法从 mKeys 查找 key 用的是 ContainerHelpers 类提供的二分查找方法:binarySearch
,用于获取 key 在 mKeys 中的当前索引(存在该 key 的话)或者是应该存放的位置的索引(不存在该 key),方法的返回值可以分为三种情况:
如果 mKeys 中存在对应的 key,则直接返回对应的索引值
如果 mKeys 中不存在对应的 key
假设 mKeys 中存在”值比 key 大且大小与 key 最接近的值的索引”为 presentIndex,则此方法的返回值为 ~presentIndex
如果 mKeys 中不存在比 key 还要大的值的话,则返回值为 ~mKeys.length
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 static int binarySearch (int [] array, int size, int value) { int lo = 0 ; int hi = size - 1 ; while (lo <= hi) { final int mid = (lo + hi) >>> 1 ; final int midVal = array[mid]; if (midVal < value) { lo = mid + 1 ; } else if (midVal > value) { hi = mid - 1 ; } else { return mid; } } return ~lo; }
可以看到,如果 mKeys 存在目标 key,那么返回值即对应的索引位置。如果不存在目标 key,其返回值也指向了应该让 key 存入的位置,因为当不存在目标 key 时,将计算出的索引值进行 ~ 运算后返回值一定是负数,从而与“找得到目标 key 的情况(返回值大于等于0)”的情况区分开。从这里可以看出该方法的巧妙之处,单纯的一个返回值就可以区分出多种情况,且通过这种方式来存放数据可以使得 mKeys 的内部值一直是按照值递增的方式来排序的
再来具体看看 put 方法的逻辑
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 public void put (int key, E value) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0 ) { mValues[i] = value; } else { i = ~i; if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return ; } if (mGarbage && mSize >= mKeys.length) { gc(); i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); mSize++; } } public void setValueAt (int index, E value) { if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) { throw new ArrayIndexOutOfBoundsException (index); } if (mGarbage) { gc(); } mValues[index] = value; } public void append (int key, E value) { if (mSize != 0 && key <= mKeys[mSize - 1 ]) { put(key, value); return ; } if (mGarbage && mSize >= mKeys.length) { gc(); } mKeys = GrowingArrayUtils.append(mKeys, mSize, key); mValues = GrowingArrayUtils.append(mValues, mSize, value); mSize++; }
6、移除元素 上文说了,布尔变量 mGarbage
用于标记当前是否有待垃圾回收(GC)的元素 ,当该值被置为 true 时,即意味着当前状态需要进行垃圾回收,但回收操作并不马上进行,而是在后续操作中再完成
以下几个方法在移除元素时,都只是切断了 mValues 对 value 的引用,而 mKeys 并没有进行回收,这个操作会留到 gc()
进行处理
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 public void delete (int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0 ) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true ; } } } public void remove (int key) { delete(key); } public E removeReturnOld (int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0 ) { if (mValues[i] != DELETED) { final E old = (E) mValues[i]; mValues[i] = DELETED; mGarbage = true ; return old; } } return null ; } public void removeAt (int index) { if (index >= mSize && UtilConfig.sThrowExceptionForUpperArrayOutOfBounds) { throw new ArrayIndexOutOfBoundsException (index); } if (mValues[index] != DELETED) { mValues[index] = DELETED; mGarbage = true ; } } public void removeAtRange (int index, int size) { final int end = Math.min(mSize, index + size); for (int i = index; i < end; i++) { removeAt(i); } } public void clear () { int n = mSize; Object[] values = mValues; for (int i = 0 ; i < n; i++) { values[i] = null ; } mSize = 0 ; mGarbage = false ; }
7、查找元素 查找元素的方法较多,逻辑都挺简单的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 @SuppressWarnings("unchecked") public E get (int key, E valueIfKeyNotFound) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; } } public E get (int key) { return get(key, null ); } @SuppressWarnings("unchecked") public E valueAt (int index) { if (mGarbage) { gc(); } return (E) mValues[index]; } public int keyAt (int index) { if (mGarbage) { gc(); } return mKeys[index]; } public int indexOfKey (int key) { if (mGarbage) { gc(); } return ContainerHelpers.binarySearch(mKeys, mSize, key); } public int indexOfValue (E value) { if (mGarbage) { gc(); } for (int i = 0 ; i < mSize; i++) { if (mValues[i] == value) { return i; } } return -1 ; } public int indexOfValueByValue (E value) { if (mGarbage) { gc(); } for (int i = 0 ; i < mSize; i++) { if (value == null ) { if (mValues[i] == null ) { return i; } } else { if (value.equals(mValues[i])) { return i; } } } return -1 ; }
8、垃圾回收 因为 SparseArray 中会出现只移除 key 和 value 两者之一的情况,导致当前数组中的有效数据并不是全都紧挨着排列在一起的,即存在无效值,因此 gc()
方法会根据 mValues 中到底存在多少有效数据,将 mKeys 和 mValues 中的数据进行重新排列,将有意义的元素值紧挨着排序在一起
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 private void gc () { int n = mSize; int o = 0 ; int [] keys = mKeys; Object[] values = mValues; for (int i = 0 ; i < n; i++) { Object val = values[i]; if (val != DELETED) { if (i != o) { keys[o] = keys[i]; values[o] = val; values[i] = null ; } o++; } } mGarbage = false ; mSize = o; }
9、优劣势总结 从上文的介绍来看,SparseArray 的主要优势有以下几点:
避免了基本数据类型 int 的装箱拆箱操作
和 HashMap 中每个存储结点都是一个类对象不同,SparseArray 不需要用于包装 key 的结构体,单个元素的存储成本更加低廉
在数据量不大的情况下,查找效率较高(二分查找法)
延迟了垃圾回收的时机,只在需要的时候才一次性进行
劣势有以下几点:
具有特定的适用范围,key 只能是 int 类型
插入键值对时可能需要移动大量的数组元素
数据量较大时,查找效率(二分查找法)会明显降低,需要经过多次折半查找才能定位到目标数据。而 HashMap 在没有哈希冲突的情况下只需要进行一次哈希计算即可定位到目标元素,有哈希冲突时也只需要对比链表或者红黑树上的元素即可
10、关联类 SparseArray 属于泛型类,所以即使 value 是基本数据类型也会被装箱和拆箱,如果想再省去这一部分开销的话,可以使用 SparseBooleanArray、SparseIntArray 和 SparseLongArray 等三个容器类,这三个容器的实现原理和 SparseArray 相同,但是 value 还是属于基本数据类型
此外,系统还提供了 LongSparseArray 这个容器类,其实现原理和 SparseArray 类似,但是 key 固定为 long 类型,value 通过泛型来声明,对于日常开发中比较有用的一点是可以用来根据 viewId 来存储 view 对象
二、ArrayMap ArrayMap 属于泛型类,继承了 Map 接口,其使用方式和 HashMap 基本一样,但在内部逻辑上有着很大差异,所以需要了解其实现原理后才能明白 ArrayMap 到底适用于哪些场景
1 public final class ArrayMap <K, V> implements Map <K, V>
1、存储机制 ArrayMap 中包含以下两个数组。mHashes 用于存储键值对中 key 的哈希值,mArray 则用于存储 key 和 value,即每个键值对会一起被存入 mArray 中
1 2 3 4 5 int [] mHashes;Object[] mArray;
当向 ArrayMap 插入键值对时,会先计算出 key 的哈希值,将 keyHash 按照大小顺序存入 mHashes 中,拿到其位置索引 index。然后将 key 存入 mArray 的 index<<1 位置,将 value 存入 mArray 的 (index<<1 + 1) 位置,即 key 和 value 会存储在相邻的位置。从这个位置对应关系来看,mArray 的所需容量至少也需要是 mHashes 的两倍,且每个 key-value 的排列关系也是和 keyHash 的排列保持一致
当要通过 key 对象向 ArrayMap 取值时,就先计算出 keyHash,然后通过二分查找法找到 keyHash 在 mHashes 中的位置索引 index,然后在 (index<<1 + 1)位置从 mArray 拿到 value
2、添加元素 有几个用于添加元素的方法,当中重点看 put
方法即可,其它添加元素的方法都需要依靠该方法来实现。前文有讲到,key-value 最终是会相邻着存入 mArray 中的,而 key-value 在 mArray 中的位置是由 keyHash 和 mHashes 来共同决定的,put
方法的整体逻辑如下所述:
根据二分查找法获取到 keyHash 在 mHashes 中的索引位置 index
如果 index 大于等于 0,说明在 mArray 中 key 已存在,那么直接覆盖旧值即可,结束流程
如果 index 小于 0,说明在 mArray 中 key 不存在,~index 此时代表的是 keyHash 按照递增顺序应该插入 mHashes 的位置
判断是否需要扩容,需要的话则进行扩容。如果符合缓存标准的话,则会缓存扩容前的数组
对最终的数组进行数据迁移,插入 key-value 和 keyHash
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 @Override 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); } if (index >= 0 ) { index = (index<<1 ) + 1 ; final V old = (V)mArray[index]; mArray[index] = value; return old; } index = ~index; if (osize >= mHashes.length) { final int n = osize >= (BASE_SIZE*2 ) ? (osize+(osize>>1 )) : (osize >= BASE_SIZE ? (BASE_SIZE*2 ) : BASE_SIZE); if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); final int [] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(n); if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { throw new ConcurrentModificationException (); } if (mHashes.length > 0 ) { if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0" ); System.arraycopy(ohashes, 0 , mHashes, 0 , ohashes.length); System.arraycopy(oarray, 0 , mArray, 0 , oarray.length); } freeArrays(ohashes, oarray, osize); } if (index < osize) { if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index) + " to " + (index+1 )); System.arraycopy(mHashes, index, mHashes, index + 1 , osize - index); System.arraycopy(mArray, index << 1 , mArray, (index + 1 ) << 1 , (mSize - index) << 1 ); } if (CONCURRENT_MODIFICATION_EXCEPTIONS) { if (osize != mSize || index >= mHashes.length) { throw new ConcurrentModificationException (); } } mHashes[index] = hash; mArray[index<<1 ] = key; mArray[(index<<1 )+1 ] = value; mSize++; return null ; }
append
方法也是用于添加元素的,带有一点“追加”的意思,如果外部可以确定本次插入的 key 的 hash 值比当前所有已有值都大的话,那么就可以直接向 mHashes 的尾部插入数据,从而节省了二分查找的过程。所以 append
方法会先和 mHashes 的最后一个元素值进行对比,如果 keyHash 比该值大的话就说明可以直接保存到尾部,校验不通过的话还是会调用 put
方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public void append (K key, V value) { int index = mSize; final int hash = key == null ? 0 : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()); if (index >= mHashes.length) { throw new IllegalStateException ("Array is full" ); } if (index > 0 && mHashes[index-1 ] > hash) { RuntimeException e = new RuntimeException ("here" ); e.fillInStackTrace(); Log.w(TAG, "New hash " + hash + " is before end of array hash " + mHashes[index-1 ] + " at index " + index + " key " + key, e); put(key, value); return ; } mSize = index+1 ; mHashes[index] = hash; index <<= 1 ; mArray[index] = key; mArray[index+1 ] = value; }
3、获取元素 获取元素的方法主要看 indexOf(Object key, int hash)
方法即可,只要理解了该方法是如何获取 keyIndex 的,那么就能够对 ArrayMap 的存储结构有更明确的认知
indexOf
方法用于获取和 key,hash 均能对应上的元素的哈希值在 mHashes 中的索引位置。我们知道,keyHash 是存储在 mHashes 中的,而 key-value 又是存储在 mArray 中的,但我们无法只根据 keyHash 就准确对应上 key-value,因为不同的 key 有可能有相同的 hash 值,即需要考虑哈希冲突的情况,所以 indexOf
方法除了需要对比 hash 值大小是否相等外还需要对比 key 的相等性
通过二分查找法获取到 mHashes 中和 hash 相等的值的索引 index
如果 index 小于 0,说明不存在该 key,那么就返回 index,~index 就是 hash 插入 mHashes 后的位置索引。结束流程
index 大于等于 0,说明 key 有可能存在,之所以说可能,因为存在 key 不同但 hash 值相等的情况
判断 mArray 中 index<<1 位置的元素是否和 key 相等,如果相等说明已经找到了目标位置,返回 index。结束流程
此时可以确定发生了哈希冲突,那么就需要对 mArray 进行相等性对比了,而之所以要分为两个 for 循环也是为了减少遍历次数,因为相同 hash 值是会靠拢在一起的,所以分别向两侧进行遍历查找。如果 key 和 keyHash 的相等性均校验通过,那么就返回对应的索引。结束流程
会执行到这里,说明还是没有找到和 key 相等的元素值,那么就拿到 hash 应该存入 mHashes 后的索引,~ 运算后返回
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 int indexOf (Object key, int hash) { final int N = mSize; if (N == 0 ) { return ~0 ; } int index = binarySearchHashes(mHashes, N, hash); if (index < 0 ) { return index; } if (key.equals(mArray[index<<1 ])) { return index; } int end; for (end = index + 1 ; end < N && mHashes[end] == hash; end++) { if (key.equals(mArray[end << 1 ])) return end; } for (int i = index - 1 ; i >= 0 && mHashes[i] == hash; i--) { if (key.equals(mArray[i << 1 ])) return i; } return ~end; }
4、缓存机制 ArrayMap 内部包含了对 mHashes 和 mArray 这两个数组进行缓存的机制,避免由于频繁创建数组而造成内存抖动,这一点还是比较有意义的。在 Android 系统中 Bundle 是使用得很频繁的一个类,其内部就通过 ArrayMap 来存储键值对,这可以从 Bundle 的父类 BaseBundle 看到。所以 ArrayMap 的数组缓存机制在我看来更多的是面对系统运行时的优化措施
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class BaseBundle { @UnsupportedAppUsage ArrayMap<String, Object> mMap = null ; public void putBoolean (@Nullable String key, boolean value) { unparcel(); mMap.put(key, value); } void putByte (@Nullable String key, byte value) { unparcel(); mMap.put(key, value); } void putChar (@Nullable String key, char value) { unparcel(); mMap.put(key, value); } ··· }
put
方法内部就使用到了数组的缓存和复用机制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 @Override public V put (K key, V value) { ··· if (osize >= mHashes.length) { final int n = osize >= (BASE_SIZE*2 ) ? (osize+(osize>>1 )) : (osize >= BASE_SIZE ? (BASE_SIZE*2 ) : BASE_SIZE); if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); final int [] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(n); if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { throw new ConcurrentModificationException (); } if (mHashes.length > 0 ) { if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0" ); System.arraycopy(ohashes, 0 , mHashes, 0 , ohashes.length); System.arraycopy(oarray, 0 , mArray, 0 , oarray.length); } freeArrays(ohashes, oarray, osize); } ··· return null ; }
缓存数组 实现数组缓存逻辑对应的是 freeArrays
方法,该方法就用于缓存 mHashes 和 mArray。每当 ArrayMap 完成数组扩容后就会调用此方法对扩容前的数组进行缓存,但也不是所有数组都会进行缓存,而是有着数组长度和缓存总数这两方面的限制
首先,ArrayMap 包含了多个全局的静态变量和静态常量用于控制及实现数组缓存。从freeArrays
方法可以看出来,if 和 else 语句块的逻辑是基本完全一样的,其区别只在于触发缓存的条件和使用的缓存池不一样
例如,如果 hashes 的数组长度是 BASE_SIZE * 2,且当前缓存总数没有超出 CACHE_SIZE,那么缓存的数组就保存在 mTwiceBaseCache 所构造的的单向链表中。mTwiceBaseCache 采用单向链表的结构来串联多个数组,要缓存的 mArray 的第一个数组元素值会先指向 mTwiceBaseCache,第二个数组元素值会指向 mHashes,之后 mArray 会成为单向链表的新的头结点,即 mArray 成为了新的 mTwiceBaseCache。在这种缓存机制下,最终 mTwiceBaseCache 指向的其实是本次缓存的 mArray,mArray 的第一个元素值指向的又是上一次缓存的 mArray,第二个元素值指向的是本次缓存的 mHashes,从而形成了一个单向链表结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 static Object[] mBaseCache;static int mBaseCacheSize;static Object[] mTwiceBaseCache;static int mTwiceBaseCacheSize;private static final int BASE_SIZE = 4 ;private static final int CACHE_SIZE = 10 ;private static final Object sBaseCacheLock = new Object ();private static final Object sTwiceBaseCacheLock = new Object ();private static void freeArrays (final int [] hashes, final Object[] array, final int size) { if (hashes.length == (BASE_SIZE*2 )) { synchronized (sTwiceBaseCacheLock) { if (mTwiceBaseCacheSize < CACHE_SIZE) { array[0 ] = mTwiceBaseCache; array[1 ] = hashes; for (int i=(size<<1 )-1 ; i>=2 ; i--) { array[i] = null ; } mTwiceBaseCache = array; mTwiceBaseCacheSize++; if (DEBUG) Log.d(TAG, "Storing 2x cache " + array + " now have " + mTwiceBaseCacheSize + " entries" ); } } } else if (hashes.length == BASE_SIZE) { synchronized (sBaseCacheLock) { if (mBaseCacheSize < CACHE_SIZE) { array[0 ] = mBaseCache; array[1 ] = hashes; for (int i=(size<<1 )-1 ; i>=2 ; i--) { array[i] = null ; } mBaseCache = array; mBaseCacheSize++; if (DEBUG) Log.d(TAG, "Storing 1x cache " + array + " now have " + mBaseCacheSize + " entries" ); } } } }
复用数组 缓存数组的目的自然就是为了后续复用,数组的复用逻辑对应的是 allocArrays
方法,该方法用于为 mHashes 和 mArray 申请一个更大容量的数组空间,通过复用数组或者全新初始化来获得
在进行数组缓存的时候会判断数组长度,只有当长度是 BASE_SIZE * 2 或 BASE_SIZE 时才会进行缓存,那么自然只有当数组的目标长度 size 是这两个值之一才符合复用条件了。allocArrays
方法取出缓存的逻辑也很简单,只需要取出单向链表的头结点赋值给 mHashes 和 mArray,同时使链表的第二个结点成为新的头结点即可。如果不符合复用条件或者复用失败,那么就还是需要重新构建两个新的数组对象
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 static Object[] mBaseCache;static int mBaseCacheSize;static Object[] mTwiceBaseCache;static int mTwiceBaseCacheSize;private static final int BASE_SIZE = 4 ;private static final int CACHE_SIZE = 10 ;private static final Object sBaseCacheLock = new Object ();private static final Object sTwiceBaseCacheLock = new Object ();private void allocArrays (final int size) { if (mHashes == EMPTY_IMMUTABLE_INTS) { throw new UnsupportedOperationException ("ArrayMap is immutable" ); } if (size == (BASE_SIZE*2 )) { synchronized (sTwiceBaseCacheLock) { if (mTwiceBaseCache != null ) { final Object[] array = mTwiceBaseCache; mArray = array; try { mTwiceBaseCache = (Object[]) array[0 ]; mHashes = (int []) array[1 ]; if (mHashes != null ) { array[0 ] = array[1 ] = null ; mTwiceBaseCacheSize--; if (DEBUG) { Log.d(TAG, "Retrieving 2x cache " + mHashes + " now have " + mTwiceBaseCacheSize + " entries" ); } return ; } } catch (ClassCastException e) { } Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0 ] + " [1]=" + array[1 ]); mTwiceBaseCache = null ; mTwiceBaseCacheSize = 0 ; } } } else if (size == BASE_SIZE) { synchronized (sBaseCacheLock) { if (mBaseCache != null ) { final Object[] array = mBaseCache; mArray = array; try { mBaseCache = (Object[]) array[0 ]; mHashes = (int []) array[1 ]; if (mHashes != null ) { array[0 ] = array[1 ] = null ; mBaseCacheSize--; if (DEBUG) { Log.d(TAG, "Retrieving 1x cache " + mHashes + " now have " + mBaseCacheSize + " entries" ); } return ; } } catch (ClassCastException e) { } Slog.wtf(TAG, "Found corrupt ArrayMap cache: [0]=" + array[0 ] + " [1]=" + array[1 ]); mBaseCache = null ; mBaseCacheSize = 0 ; } } } mHashes = new int [size]; mArray = new Object [size<<1 ]; }
总结 上文说了,只有长度为 BASE_SIZE 或者 BASE_SIZE * 2 的数组才会被缓存复用,而 mHashes 和 mArray 的扩容操作也会尽量使得扩容后的数组长度就是这两个值之一,这可以从 put
方法计算扩容后容量的算法看出来
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 @Override public V put (K key, V value) { final int osize = mSize; final int hash; ··· if (osize >= mHashes.length) { final int n = osize >= (BASE_SIZE*2 ) ? (osize+(osize>>1 )) : (osize >= BASE_SIZE ? (BASE_SIZE*2 ) : BASE_SIZE); if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); final int [] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(n); ··· freeArrays(ohashes, oarray, osize); } ··· return null ; }
所以说,虽然 ArrayMap 的构造函数中并没有直接将 BASE_SIZE 作为数组的默认长度,但是在扩容过程中会尽量往 BASE_SIZE 和 BASE_SIZE * 2 这两个值靠拢,这就有利于尽量实现数组复用
此外,ArrayMap 的扩容操作在申请内存时也显得比较克制,在数组长度超出 BASE_SIZE * 2 后,只是扩容到当前的 1.5 倍,且也只在 mHashes 容量不足时才会触发扩容机制。而 HashMap 在达到负载因子设定的比例后(此时数组未满)就会触发扩容机制,而且也是按照扩充到两倍容量的方式进行扩容。所以说,ArrayMap 对于内存空间的利用效率会更高一些
5、优劣势总结 ArrayMap 的适用场景可以从它的缓存机制就看出来一些,它会缓存容量为 4 或者 8 的数组并进行后续复用,而这两个值可以说都是比较小的。Android 系统对于内存比较敏感,需要存储键值对时面对的往往是使用频率高但数据量小的场景。例如我们在跳转到 Activity 时往往是通过 Bundle 来存储跳转参数,但数据量一般都很少,所以 Bundle 内部就使用到了 ArrayMap 来存储键值对。ArrayMap 在内存申请时相比 HashMap 会比较克制,键值对会以更加紧密的数据结构存储在一起,对内存利用率会更高一些
而相对的,ArrayMap 的这种存储结构也导致了其查找效率相比 HashMap 要低很多。在数据量大时,ArrayMap 可能需要通过多次二分查找才能定位到元素,而 HashMap 在没有哈希冲突的情况下只需要经过一次哈希计算即可定位到元素,即使有哈希冲突也只需要遍历发生冲突的部分元素即可
所以说, ArrayMap 适用于数据量较小的场景,此时查找效率也不会受多大影响,而内存利用率能够显著提高。如果数据量较大,那就可以考虑使用 HashMap 来替代了
6、关联类 系统还包含了一个用于存储不重复元素值的集合框架类:ArraySet,从名字就可以猜到 ArraySet 实现了 Set 接口。ArraySet 内部一样使用两个数组来存储 hash 和 value,即 mHashes 和 mArray,在实现逻辑上基本和 ArrayMap 一样,只是会在存值的时候判断 value 是否重复而已,这里就不再赘述了