Android HashMap ArrayMap SparseArray

基于 android-9.0.0_r34分析。

概述

hashmap是数组的扩展,数组通过下标可以在o(1)时间找到对应的数据,hashmap把整数的下标宽展到任意数据类型(有些其他的限制),同时优化存储,占用的空间大小和实际存储的数据正比。

java.util.HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
java.util.LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>

java标准的hashmap的实现,doc src

java.util.LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>

java标准的LinkedHashMap的实现,doc src

android.util.SparseArray<E> implements Cloneable 
android.util.SparseBooleanArray implements Cloneable
android.util.SparseIntArray implements Cloneable
android.util.SparseLongArray implements Cloneable

SparseArray系列的实现,严格说来这些不是map,其key值固定为Int类型,其可以比数组存储空间更高效存储稀疏数据,key值不连续,相邻的key之间有比较大的空隙的情况。doc src

android.util.ArrayMap<K, V> implements Map<K, V>
android.support.v4.util.ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V>
android.support.v4.util.SimpleArrayMap<K, V>

since API 19和support library,相比java版的hashmap的实现,采用了更高效的存储方式,减少存储空间占用,保守的存储扩展,hashmap没次扩容一倍,arraymap没次扩充之前的一半,key的搜寻采用二分查找方式,在查找效率上有下降,所以不适合大量的数据的存储,在support library增加了util.SimpleArrayMap类,该类是arraymap的精简版,没有实现标准的map接口。doc src

扩容缩容策略

HashMap

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

初始大小为16,当load factor 超过0.75后会进行扩容,扩容一倍。扩容后要把所有原有的数据重新hash到新的数组中,所以扩容操作比较费时。

//HashMap.java
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
       boolean evict) {
    if (++size > threshold)
        resize();
}
final Node<K,V>[] resize() {

    //初始化状态
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    
    int oldThr = threshold;
    //容量扩大为之前两倍 table size扩大两倍  threshold也扩大两倍
    if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
    }
    threshold = newThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //将旧的数组中所有值重新hash放到新表中
    ...
 }

内部数组table从不缩小,即使clear,也不会缩小table的大小。删除的数据如果位于树或链表上则直接释放,如果位于table里则把table对应的元素赋null。

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

SparseArray

SparseArray设计的出发点是提高内存利用效率,减小内存占用,在速度上做了妥协。基本结构为:

//SparseArray.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;
}
//android/internal/util/GrowingArrayUtils.java
public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

SimpleArrayMap/ArrayMap

SimpleArrayMap和SparseArray的设计思路相同,也是以节省内存空间为出发点的。

SimpleArrayMap的key本身是整数,所以不用处理hash值的冲突,SimpleArrayMap主要在hash值存储和冲突的处理上做了很多补充。 存储空间不够时,每次扩容的大小为原来大小的一半。

final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
        : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);

考虑到不断的重复申请释放内存对效率是一大影响,ArrayMap设计了静态的缓存机制。会对大小为4、8的mHashsmArray最多分别缓存个10个。

public class SimpleArrayMap<K, V> {
    /**
     * The minimum amount by which the capacity of a ArrayMap will increase.
     * This is tuned to be relatively space-efficient.
     */
    private static final int BASE_SIZE = 4;
    /**
     * Maximum number of entries to have in array caches.
     */
    private static final int CACHE_SIZE = 10;
    /**
     * Caches of small array objects to avoid spamming garbage.  The cache
     * Object[] variable is a pointer to a linked list of array objects.
     * The first entry in the array is a pointer to the next array in the
     * list; the second entry is a pointer to the int[] hash code array for it.
     */
    static Object[] mBaseCache;
    static int mBaseCacheSize;
    static Object[] mTwiceBaseCache;
    static int mTwiceBaseCacheSize;

mBaseCachemTwiceBaseCache结构相同,只是缓存的mHashs大小不一致。 移除元素时,缩小的策略和增加时相同,即每次缩小为当前大小的\(\frac{2}{3}\),如果当前的大小为BASE_SIZE BASE_SIZE*2时,会先检查缓存是否有空间,如果有放到缓存里,否则,直接释放。

if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
    // Shrunk enough to reduce size of arrays.  We don't allow it to
    // shrink smaller than (BASE_SIZE*2) to avoid flapping between
    // that and BASE_SIZE.
    final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
}

hash函数

hash函数的定义 h:U->{0,1,....m-1},即hash函数把key的变量空间变换为线性连续的[0,m)的整数空间,这样hanshmap的实现又回到了数组的形式。

HashMap

//HashMap.java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        ...
}

hash table大小为\( 2^n\),故取余操作可以用hash&(table size-1)得到。该算法hash后的值只于原值的低位有关,故做了将高位与低位异或的操作,让高位也影响低位,来趋近随机hash。 综合得:

  1. 通过ObjecthashCode方法把任意类型转化为一个int值。
  2. 通过取余获得该int值位于数组中的位置

SimpleArrayMap/ArrayMap

使用的hash函数和HashMap相同。

public V put(K key, V value) {
    final int hash;
    hash = key.hashCode();
}

冲突解决方式

HashMap

采用了数组后面加挂单链表的方式解决冲突。当单链表长度超过8(TREEIFYTHRESHOLD),单链表会被转换为红黑树存储,当红黑树的节点小于6(UNTREEIFYTHRESHOLD),树会被重新转化为单链表。树化后也继续保持了之前的单链表结构,可以继续按单链表遍历。

SimpleArrayMap/ArrayMap

没有采用HashMap的链表模式解决冲突,因为链表节点本身占用的存储空间比较大,在mArray中交替存储keyvalue而不是新建一个数据结构封装也是处于节省内存的考虑。 考虑到hash必然会有冲突,这时hash后的hash值是相同的但key本身并不相同。这时相同的hash值在mHashs中按单调增存储的模式下必然是连续在一起的,这时要采用向当前位置后部和前部分别搜索hash值相同的位置,看key值是否相同。

int indexOf(Object key, int hash) {
    final int N = mSize;
     //二分查找
    int index = ContainerHelpers.binarySearch(mHashes, N, hash);
    // If the hash code wasn't found, then we have no entry for this key.
    //没找到
    if (index < 0) {
        return index;
    }
    //找到了,比较key值是否相同
    // If the key at the returned index matches, that's what we want.
    if (key.equals(mArray[index<<1])) {
        return index;
    }
    // Search for a matching key after the index.
    //向后搜索
    int end;
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        if (key.equals(mArray[end << 1])) return end;
    }
    // Search for a matching key before the index.
    //向前搜索
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        if (key.equals(mArray[i << 1])) return i;
    }
    // 没找到,返回如果key值存在应该在的位置的按位取反,方便插入
    return ~end;
}

遍历策略,顺序保持

hashmap

//HashMap.java
public void forEach(BiConsumer<? super K, ? super V> action) {
    Node<K,V>[] tab;
    if (size > 0 && (tab = table) != null) {
        for (int i = 0; (i < tab.length && mc == modCount); ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e.key, e.value);
        }
    }
}

遍历顺序为从table表的第0个元素开始,如果有相同的hash值的链表,遍历链表,树也保存了链表结构,可以统一按链表遍历,该遍历无法保证遍历的顺序和数据插入顺序一致。

LinkedHashMap

LinkedHashMap通过继承复用了HashMap实现. 扩展Node数据结构增加双链表的指针。

//LinkedHashMap
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
    LinkedHashMapEntry<K,V> before, after;
}

通过复写Node的创建,让table数组里实际存储的数据为LinkedHashMapEntry,然后通过HashMap留的桩点,在插入、删除等操作时,维护双向链表和元素的插入顺序一致。

//hashmap
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}
//LinkedHashMap 覆写
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMapEntry<K,V> p =
        new LinkedHashMapEntry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

HashMap通过下面几个桩函数给LinkedHashMap提供调整链表的机会。

//HashMap
V put(K key, V value) -> void afterNodeInsertion(boolean evict) { }
V remove(Object key)  -> void afterNodeRemoval(Node<K,V> p) { }

这样LinkedHashMap提供了按插入顺序遍历,或者按访问顺序遍历的遍历方式

//LinkedHashMap
public void forEach(BiConsumer<? super K, ? super V> action) {
    for (LinkedHashMapEntry<K,V> e = head; modCount == mc && e != null; e = e.after)
        action.accept(e.key, e.value);
}

SparseArray

遍历采用从[0-mSize)遍历mKeysmValues,无法保证按插入顺序访问。

public int keyAt(int index) {
    if (mGarbage) {
        gc();
    }
    return mKeys[index];
}

SimpleArrayMap/ArrayMap

遍历策略和SparseArray相同,并不能保证遍历的顺序和插入的顺序一致。

总结

可以看到从效率和功能上,HashMapLinkedHashMap功能很强大,查找的效率也很高,通过hash和红黑树,保证了查找的效率,缺点就时占用内存很多,SparseArray ArrayMap则是在减少内存占用上做了深入优化,但二分查找,插入扩容时,数组的多次拷贝,损失了一定效率,在数据量比较小是ArrayMap有优势,如果数据量比较大效率则会比HashMap差,google文档上的表述是在存储几百个元素时,其效率下降不会超过50%。


\[\nabla\cdot E = \frac{\rho}{\epsilon_0}\] \[\nabla \times E = -\frac{\partial B}{\partial t}\] \[\nabla \cdot B = 0 \] \[ c^2 \nabla \times B = \frac{\partial E}{\partial t}+\frac{j}{\epsilon_0}\]