Android知识点 ArrayMap SparseArray

ArrayMap SparseArray

问题：ArrayMap SparseArray的数据结构是怎么样的？

双数组结构。ArrayMap第一个数组元素是key的hashValue，对应第二个数组的一对key-value。通过二分查找进行插入。 SparseArray第一个数组是int类型的key，第二个数组元素是value

为了更进一步优化key是int类型的Map，Android再次提供效率更高的数据结构SparseArray，可避免自动装箱过程。对于key为其他类型则可使用ArrayMap。HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的，而SparseArray和ArrayMap性能略逊于HashMap，但更节省内存。

ArrayMap

ArrayMap相比HashMap内存更少，速度更慢。 ArraySet， ArrayList类似。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" cid="n6" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-color: rgb(51, 51, 51); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 10px 10px 30px; width: inherit; background-position: initial initial; background-repeat: initial initial;" lang="Java">public final class ArrayMap<K, V> implements Map<K, V> {

private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true;

private static final int BASE_SIZE = 4; // 容量增量的最小值
private static final int CACHE_SIZE = 10; // 缓存数组的上限

static Object[] mBaseCache; //用于缓存大小为4的ArrayMap
static int mBaseCacheSize;
static Object[] mTwiceBaseCache; //用于缓存大小为8的ArrayMap
static int mTwiceBaseCacheSize;

final boolean mIdentityHashCode;
int[] mHashes; //由key的hashcode所组成的数组
Object[] mArray; //由key-value对所组成的数组，是mHashes大小的2倍
int mSize; //成员变量的个数
}</pre>

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" cid="n21" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-color: rgb(51, 51, 51); font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 10px 10px 30px; width: inherit; background-position: initial initial; background-repeat: initial initial;" lang="Java">public class SparseArray<E> implements Cloneable {
private static final Object DELETED = new Object();
private boolean mGarbage = false; //标记是否存在待回收的键值对

private int[] mKeys;
private Object[] mValues;
private int mSize;
}</pre>

SparseArray使用二分查找来找到key对应的插入位置，保证mKeys数组从小到大的排序。

SparseArray对应的key只能是int类型，它不会对key进行装箱操作。它使用了两个数组，一个保存key，一个保存value。从内存使用上来说，SparseArray不需要保存key所对应的哈希值，所以比ArrayMap还能再节省1/3的内存。

image

SparseArray，key是int类型的Map，更加memory-efficient。

SparseArray

如果当前数组内容已填充满时，则会先进行扩容，再通过System.arraycopy来进行数据拷贝，最后在相应位置写入数据。

将修改已有键值对和插入新的键值对合在一个put()方法中，主要是依赖indexOf()过程中采用的二分查找法，在mHashes数组中查找值等于hash的key，当找到相应key时则返回正值，但找不到key则返回负值，按位取反所对应的值代表的是需要插入的位置index。

Put原理

为了减少频繁地创建和回收，特意设计了两个缓存池，分别缓存大小为4和8的ArrayMap对象。

缓存

mHashes是一个记录所有key的hashcode值组成的数组，是从小到大的排序方式；
mArray是一个记录着key-value键值对所组成的数组，是mHashes大小的2倍；