传送门：Java（Android）数据结构汇总 -- 总纲

简介

这篇主要来整理下基于Map接口实现的数据结构类。Map集合主要用来存储键值对。它的相关实现类有java.util包的HashMap、LinkedHashMap、Hashtable、TreeMap、EnumMap、IdentityHashMap、WeakHashMap和android.util包的ArrayMap、SparseArray、SparseIntArray、SparseBooleanArray、SparseLongArray、LongSparseArray等。下面分别一一来讲解。

Java部分

一、HashMap

HashMap应该也是我们java中最常用的存储键值对的数据结构类了。它内部是以数组+链表（从1.8版本开始引入了红黑树）的形式来存放键值对的。

基本原理

HashMap是通过对key的hash值进行转换来定位每个key在内部数组上的位置。数组的每个元素又都是一个链表，这样如果一个位置有多个键值对的时候就可以依次存放在这个链表上。至于为什么每个位置可能会存在多个值，这个请看后面。

看了上面的原理介绍，可能还比较懵。没事，下面将一一具体来介绍。

具体实现

Key的Hash值计算分两步：

• 第一步：正常计算出key的hash值（调用key的hashCode()方法，如果key是null则其hash值是0）；
• 第二步：对得到的hash值进行扰乱，目的是为了让hash值能尽可能的均匀分布。

  我们认为HashMap的数组上每个位置只有一个元素是最理想的，扰乱操作的目的就是为了让hash值能尽可能的均匀分布（原因看后面如何将hash值转换为数组索引的介绍）。

为什么要用key的hash值而不直接用key，这里先不讲，看完下面的源码再说：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 计算key的HashCode
static final int hash(Object key) {
    int h;
    // 首先，如果key是null，则直接返回0（这里也说明HashMap支持null作为key）
    // 如果key不是null，就计算key的hashCode值并存放到h变量中
    // 最后进行扰乱操作，在1.8版本中是h ^ (h >>> 16)，在1.8版本之前还会有更多次的位运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 如果数组（table）还没有初始化，则进行数组的初始化操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 重点
    // 这里通过(n - 1) & hash计算将hash值转换成数组上的索引  --> 解释1（具体解释见后面）
    // 这里通过hash值计算出key在数组上位置，这样就可以直接在这个位置上的链表里面去查
    // 找有没有指定的key，而不需要在整个数组上去查找（这样大大减少了查询范围）
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果该位置还没有元素，则直接新建一个节点并存放在该位置
        tab[i] = newNode(hash, key, value, null);
    else {
        // 整个else的逻辑就是为了在该链表上查找是否存在相同的key，如果存在则将该节点赋值给e，如果没有找到e就为null

        // Node节点存储的值有key、key的hashcode、value、next（下一个节点的引用）四个数据
        Node<K,V> e; K k;

        // 判断链表的头节点是否和本次插入的key相同 --> 解释2
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 判断链表是否是红黑树
        else if (p instanceof TreeNode)
            // 在红黑树中查找是否存在相同的key
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍历链表，查找是否存在相同的key
            for (int binCount = 0; ; ++binCount) {
                // 整个链表都没有相同key，则新建一个node，并添加到链表结尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 判断链表的长度是否达到了TREEIFY_THRESHOLD，
                    // 如果达到就将链表转换成红黑树（红黑树查询速度比链表更快）
                    // 红黑树是1.8版本引入的
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // 如果找到了有相同key的节点，则跳出循环
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;

                p = e;
            }
        }

        // 如果e不为空，表示e所指向的节点的key和当前要插入的key相同，此时用新的value替换该节点的value，而不新建node节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;

    // 如果当前数组的长度超过了设定的阈值，则进行数组扩容
    if (++size > threshold)
        resize();

    afterNodeInsertion(evict);
    return null;
}

解释1：看下面几个问题：

• 问题1：为什么不直接使用key而要使用key的hash值？

  如果直接使用key，那么在查找的时候需要调用key的equals方法去逐个比较，对吧。首先逐个比较效率就不高（万一要查找的节点正好是最后一个，那岂不是要将整个集合都比较一遍？），再加上equals方法本身效率也不高，这样如果直接使用key的话整个HashMap的性能就很差。

  而用hash值可以直接定位到数组上的某个位置，这样只需要在这个位置的链表上进行查找就行了，从而大大缩小了查找范围和比较的次数。

• 问题2：那为什么又不直接用hash值作为数组上的索引？

  怕数组越界对吧。hash值的范围不可控，直接用hash值作为数组索引容易造成数组下标越界。为了解决这个问题，于是想出了使用hash值和当前数组长度进行取模运算，将结果作为数组的索引，即index = hash % length。index只会在0到length - 1之间，这样就不怕数组下标越界了。

• 问题3：那为什么用的是(n - 1) & hash，而不是hash % n呐？

  其实早期版本就是用hash % n，但是为了追求效率，后来就改成了位运算(n - 1) & hash（位运速度比取模运算快）。

• 问题4：为什么(n - 1) & hash和hash % n是等价的？

  这里利用了HashMap的一个特性：HashMap规定其容量必须是2的n次方（最大为2³⁰次方）,那么n肯定就是2^xx次方了，用二进制表示就是1000...00，最前面是1，后面全是0(假设有k个0)，那么n-1就全变成1了111...1111（k-1个1），hash ^ (n - 1)得到的最大值就是n-1，最小值是0。效果和hash % n一样，只是改为位运算了。位运算比取模运算更快。

解释2：注意这里的比较顺序：

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

1. 为时还要比较p.hash == hash？

   因为我们前面是通过hash取模来实现数组上的定位的，所以在数组上同一个位置的hash值不一定就相等，比如 25和33两个hash值，他们对8取模结果都是1。所以需要进行hash值的比较。

2. hash值相等了，为什么还要进一步比较key？

   因为两个不同的key计算出的hash值可能相同（也就是hash碰撞），所以为了解决这个问题需要进一步比较key。

3. 为什么要比较k == key，而不直接用equals方法？

   因为HaspMap允许null作为key，所以不能直接调用equals来比较。

从上面的分析我们还能得出三个HashMap的特性：

1. null可以作为HashMap的key和value。因为key是不能重复了，所以也就只允许一个null作为key，但是允许多个value的值是null；
2. HashMap的key是根据其hash值随机分布在数组上的，所以HashMap的记录是无序的；
3. 我们在HashMap的源码中没有看到任何同步相关的代码，所以HashMap不是线程安全的。

二、LinkedHashMap

LinkedHashMap继承至HashMap，在HashMap的基础上新增了一个双向链表来实现了记录的有序化。

大家不要被这个名字迷惑了，是不是也和ArrayList跟LinkedList一样一个是用数组实现的一个是用链表实现的呐？其实不是的，LinkedHashMap的主要功能是实现了内部元素的有序化（上面说了HashMap的元素是无序的）。

LinkedHashMap的有序有两种模式：插入顺序和访问顺序。具体使用哪种顺序模式是在构造方法处指定的。

插入顺序：就是按照插入的时间排序，先插入的数据排在前面，后插入的数据排在后面。
访问顺序：就是按照最近访问进行排序，访问时间越近的数据排在越靠后的位置，访问时间越远的数据越排在靠前的位置（实现方式就是当元素每次被访问后就将其移动到链表结尾）。LruCache就是基于此原理实现的。

来看这几个构造方法：

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

其中，accessOrder用来指定是否使用访问顺序模式，true表示使用访问顺序模式，否则使用插入顺序模式，默认使用插入顺序模式。

具体实现

首先，LinkedHashMap新增了一个LinkedHashMapEntry，它继承至HashMap的Node类，在其中增加了两个自己用于链表维护的变量：

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
    // 新增了before、after两个字段，LinkedHashMap使用这两个字段来维护自己的双向链表
    LinkedHashMapEntry<K,V> before, after;
    LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

然后，LinkedHashMap重写了HashMap的newNode()方法（HashMap每次新增节点都是通过这个方法来创建一个节点）来实现每次新增数据的时候都能将新增的数据添加到自己维护的链表的结尾，从而保证了插入顺序：

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添加到链表末尾
    linkNodeLast(p);

    return p;
}

private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
    LinkedHashMapEntry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

其次，LinkedHashMap重写了HashMap的afterNodeRemoval()方法（HashMap在删除数据的时候会回调该方法）以保证数据的同步：

// 重写HashMap的afterNodeRemoval方法
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

最后，为了维护访问顺序，LinkedHashMap重写了get()、getOrDefault()和afterNodeAccess()三个方法（当HashMap修改了数据时，比如put了一个相同key不同value，会回调afterNodeAccess()方法）。具体代码如下：

// 重写HashMap的get方法
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;

    // 如果使用的访问顺序模式，则调用afterNodeAccess方法来移动节点到链表末尾
    if (accessOrder)
        afterNodeAccess(e);

    return e.value;
}

// 重写HashMap的getOrDefault方法
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;

    // 如果使用的访问顺序模式，则调用afterNodeAccess方法来移动节点到链表末尾
   if (accessOrder)
       afterNodeAccess(e);
   return e.value;
}

// 重写HashMap的afterNodeAccess方法，监听节点的修改
void afterNodeAccess(Node<K,V> e) { 
    LinkedHashMapEntry<K,V> last;

    // 如果使用的访问顺序模式且修改的不是最后一条数据，则将被修改的节点移动到链表末尾
    if (accessOrder && (last = tail) != e) {
        LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;

        // 先从链表中移除该节点
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;


        // 将该节点重新添加到链表结尾
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;

        ++modCount;
    }
}

三、TreeMap

TreeMap内部是使用红黑树来实现的。对红黑树不了解的可以看github上的这篇文章介绍：教你透彻了解红黑树。

它与HashMap的区别如下：

因为要对key进行排序，所以key必须要实现自然排序和定制排序中的一种。自然排序就是key要继承java.lang.Comparable接口，而定制排序则需要在创建TreeMap对象的时候指定一个实现了java.lang.Comparable接口的对象，源码如下：

public TreeMap() {
    // 如果使用这个构造方法，key就必须要实现Comparable接口
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    // 如果使用这个构造方法，则需要指定一个comparator对象，此时key就不需要实现Comparable接口
    this.comparator = comparator;
}

首先还是来看一下它的Entity类：

static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
    // 存放该节点值的变量（key和value）
    K key;
    V value;

    // 左子节点
    TreeMapEntry<K,V> left;
    // 右子节点
    TreeMapEntry<K,V> right;
    // 父节点
    TreeMapEntry<K,V> parent;
    // 该节点颜色
    boolean color = BLACK;
    ...
}

再来看看put方法：

public V put(K key, V value) {
    TreeMapEntry<K,V> t = root;
    if (t == null) {
        // compare(key, key); // type (and possibly null) check
        // 这里的if-else主要是对key的类型和是否是null值进行检查
        if (comparator != null) {
            if (key == null) {
                comparator.compare(key, key);
            }
        } else {
            if (key == null) {
                throw new NullPointerException("key == null");
            } else if (!(key instanceof Comparable)) {
                throw new ClassCastException(
                        "Cannot cast" + key.getClass().getName() + " to Comparable.");
            }
        }
         
        root = new TreeMapEntry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }

    int cmp;
    TreeMapEntry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
               t = t.left;
            else if (cmp > 0)
               t = t.right;
            else
               return t.setValue(value);
        } while (t != null);
    } else {
        if (key == null)
            throw new NullPointerException();
        
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
        
    TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

因为TreeMap的主要逻辑是红黑树，如果对红黑树不了解的需要先去学习下红黑树。这里因为篇幅原因就不多讲。

四、Hashtable

Hashtable和HashMap类似，不同之处是Hashtable实现了线程同步。目前已经不建议使用Hashtable了，这里就不多讲解了。如果需要线程同步，给的建议是使用java.util.concurrent包下的ConcurrentHashMap类来代替。下面是来自Hashtable的一段类注释：

If a thread-safe implementation is not needed, it is recommended to use {@link HashMap} in place of {@code Hashtable}. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use {@link java.util.concurrent.ConcurrentHashMap} in place of {@code Hashtable}.

五、EnumMap

EnumMap是一个特殊的Map，它的key被限定为只能是枚举型，并使用key的ordinal值作为其内部数组的下标。这样有两个好处：一是不需要再对key进行hash计算；二是因为使用的是ordinal值(每个枚举类里面的枚举常量的ordinal值有序且唯一)，所以每个位置对应唯一一个key，所以也就不再需要链表，直接用一个数组就能实现。因此EnumMap的效率比HashMap更高。

关于ordinal值：每个枚举型常量都有一个ordinal()方法，用于返回该枚举常量的序号（从0开始）。如：

 enum Light {
    RED, GREEN, YELLOW;
 }

则：RED.ordinal()为0， GREEN.ordinal()为1， YELLOW.ordinal()为2。

还是来看下源码：

public V put(K key, V value) {
    // 容错处理：检查key是否是指定的枚举类型
    typeCheck(key);

    // 可以看出，确实是直接使用key的ordinal值作为数组的下标索引。
    int index = key.ordinal();
    Object oldValue = vals[index];
    // EnumMap内部不直接存储null，如果是null则会用maskNull方法将其转换成一个内部特定的对象
    vals[index] = maskNull(value);
    // 为什么不直接存储null，看这里就明白了，如果某个位置的值为null，表示这个位置没有存储值，而不是存储了一个null值
    if (oldValue == null)
        // 如果当前位置以前的值是null，表示这个位置以前没有存储值，则会执行size++，否则就是值的替换，size就不会变
        size++;

    // 检查值如果是内部特定的对象，则用unmaskNull方法将其重新转换成null返回
    return unmaskNull(oldValue);
}

public V get(Object key) {
    return (isValidKey(key) ? unmaskNull(vals[((Enum<?>)key).ordinal()]) : null);
}

可以看出，EnumMap还是非常简单的。相比HashMap来说，它简化了存储逻辑，使得性能进一步得到了提升。缺点是限制了key只能是枚举型，只能使用枚举型。同样，EnumMap也不是线程安全的。

使用场景：在某些使用枚举型作为key的特定场景下用来代替HashMap，性能会得到进一步提升。

六、IdentityHashMap

IdentityHashMap也是一个特殊的Map，它要求两个key严格相等（key1==key2）才算是同一个key。而它的存储结构是数组。key-value在数组上是挨着存储的，比如table[0]=key，table[1]=value。来看它的一段源码就清楚了：

public V put(K key, V value) {
    // 如果key是null，则将其转换成一个内部固定对象NULL_KEY 
    final Object k = maskNull(key);

    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        // 这里将key映射到数组上的方式和HashMap一样：将key的hash值和数组长度进行取模运算来得出key在数组上的位置
        // 这里有个细微差别就是计算出的值是偶数（0、2、4、...）正好对应数组的奇数位（1、3、5、...），
        // 这样也保证了数组上的存储顺序为：key、value、key、value、...
        int i = hash(k, len);

        // 从i位置开始往后遍历数组，i = nextKeyIndex(i, len)相当于 i += 2
        for (Object item; (item = tab[i]) != null; i = nextKeyIndex(i, len)) {
            // 这里就是IdentityHashMap的主要特性了：只有当两个key1==key2才算是同一个key（即便equals方法相等也不算）
            if (item == k) {
                // 如果该位置和插入的key相等，那么将value存放在下一个位置（i+1）
                @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
        }

        final int s = size + 1;
        // Use optimized form of 3 * s.
        // Next capacity is len, 2 * current capacity.
        if (s + (s << 1) > len && resize(len))
            continue retryAfterResize;

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}

private static int nextKeyIndex(int i, int len) {
    return (i + 2 < len ? i + 2 : 0);
}

/**
 * Value representing null keys inside tables.
 */
static final Object NULL_KEY = new Object();

/**
 * Use NULL_KEY for key if it is null.
 */
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

七、WeakHashMap

WeakHashMap与java的对象引用体系有关。HashMap是直接持有key-value的强引用，只要HashMap不主动删除这些key-value（且HashMap本身不能被回收时），他们就不会被系统回收。而WeakHashMap则是持有key的一个弱引用，这样就可以被系统主动回收。

Java的对象引用系统有四种：强引用、软引用、弱引用和虚引用。

1. 强引用：就是平时我们直接对对象的引用，比如Object h = new Object()，这里的h就是一个强引用，在h不超出范围的情况下，只要h不被设置为null，这个对象就不会被系统回收；
2. 软引用：使用SoftReference来实现（具体用法这里不做介绍）。在系统执行gc的时候，如果检查到内存不足，则会回收SoftReference持有的对象。如果我们想在持有的对象被回收后做一些额外处理，则可以配合ReferenceQueue一起使用，将SoftReference对象和ReferenceQueue关联后，当SoftReference持有的对象被回收后会将SoftReference对象添加到ReferenceQueue中；
3. 弱引用：使用WeakReference来实现（具体用法这里不做介绍），在系统执行gc的时候，会回收SoftReference持有的对象。注意与软引用的区别，软引用是在内存不足时才被回收，而弱引用则是只要执行gc就会被回收。如果我们想在持有的对象被回收后做一些额外处理，则可以配合ReferenceQueue一起使用，将WeakReference对象和ReferenceQueue关联后，当WeakReference持有的对象呗回收后会将WeakReference对象添加到ReferenceQueue中；
4. 虚引用：使用PhantomReference来实现（具体用法这里不做介绍）。它和软引用以及弱引用不同，它必须配合ReferenceQueue一起使用，它不会主动清除引用，而是在对象将要被回收时会将其添加到队列（软引用和弱引用是在对象被回收之后才添加到队列）。

我们还是来看看它的源码实现，先看它的Entry类：

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
    V value;
    final int hash;
    Entry<K,V> next;

    Entry(Object key, V value, ReferenceQueue<Object> queue,  int hash, Entry<K,V> next) {
        super(key, queue);
        this.value = value;
        this.hash  = hash;
        this.next  = next;
    }
}

可以看出，Entry类继承至WeakReference，并将key作为WeakReference的引用对象。同时和一个ReferenceQueue进行了关联，这样当key被回收时WeakHashMap就能收到通知，将这个实体对象从链表中移除。

我们任何一个操作，比如调用get、put、size等方法的时候，都会自动调用expungeStaleEntries()方法来检查ReferenceQueue队列里是否有已经被回收的对象，如果有则将其移除，源码如下：

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

public int size() {
    if (size == 0)
        return 0;
    // 调用expungeStaleEntries方法，移除已经被回收的key-value
    expungeStaleEntries();
    return size;
}
   
public V get(Object key) {
    ...
    Entry<K,V>[] tab = getTable();
    .... 
}

public V put(K key, V value) {
    ...
    Entry<K,V>[] tab = getTable();
    ... 
}

private Entry<K,V>[] getTable() {
    expungeStaleEntries();
    return table;
}

private void expungeStaleEntries() {
    // 检查queue里面是否有元素，如果有则将其从链表中移除
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.lengt
            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

源码比较简单，这里就不多说了。有个需要注意的地方就是在使用WeakHashMap的时候其key外部不要有他的引用，否则就失去了WeakHashMap的意义（如果有其他引用则会导致key不能被回收）。还有个特别主意的地方就是如果key用的是一个字符串常量时，它是不会被回收的，因为系统会自动保留对该字符串对象的强引用。如：

WeakHashMap wak = new WeakHashMap();
// 这种写法是不会被回收的，因为"hello"是一个字符串常量，系统会自动保留对该字符串对象的强引用
wak.put("hello", obj);

总结

Android部分

一、ArrayMap

added in version 22.1.0 or android.support.v4

ArrayMap是android对HashMap在内存使用上的一个优化版本。内存优化主要体现在两个地方：

1. 每次扩容都是增加当前容量的0.5倍（当前容量大于两倍BASE_SIZE时），hashMap是增加当前容量的一倍；
2. 当容量的使用率不到1/3时会收缩容量，释放多余的空间。

ArrayMap内部是使用两个数组来实现的。一个数组用来保存key的hash值，另一个数组用来保存key和value（每相邻的两个位置表示一个键值对，前面的是key，后面的是value）。

另外，ArrayMap对两种基础容量数组进行了缓存，这样加快了数组的构建过程和内存的利用率（减少了频繁的内存申请释放）。

public final class ArrayMap<K, V> implements Map<K, V> {

    // 基础容量大小
    private static final int BASE_SIZE = 4;

    // 基础容量数组的缓存
    // 当需要扩容时，如果当前使用的是基础容量，则会将当前的mHashes和mArray进行缓存。
    // 当缩小容量到基础容量（或其他ArrayMap对象需要基础容量数组）时，会将其从缓存中取出使用。
    // 存储方式：mBaseCache有点像是一个链表，要缓存的mArray数组作为链表的节点，
    // mArray[0]指向上一个节点，mArray[1]存储当前的mHashes数组
    static Object[] mBaseCache;
    // 基础容量数组的当前缓存数量
    static int mBaseCacheSize;

    // 两倍基础容量数组的缓存
    // 原理同上
    static Object[] mTwiceBaseCache;
    // 两倍基础容量数组的当前缓存数量
    static int mTwiceBaseCacheSize;

    // 缓存的上限
    private static final int CACHE_SIZE = 10;

    // 用来存放key的hash值
    int[] mHashes;
    // 用来存放键值对
    Object[] mArray;
    // 键值对数量
    int mSize;
}

来看看put操作：

public V put(K key, V value) {
    final int osize = mSize;
    final int hash;
    int index;

    // 计算key的hash值以及hash值在mHashes数组上的索引
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        index = indexOf(key, hash);
    }

    // 如果索引不小于0，表示这个key存在，这直接替换原来的值
    if (index >= 0) {
        // key的hash值在mHashes数组上的索引是index，
        // 那么对应的key在mArray数组上的存储位置为index * 2，value在mArray数组上的存储位置为idnex * 2 + 1
        // 计算value的存储位置(index<<1) + 1也就是index * 2 + 1
        index = (index<<1) + 1;
        // 用新的值替换旧的值，并返回旧的值
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    // indexOf方法在查找位置的时候如果没有找到key的hash值时会返回最后一次查找的位置，
    // 目的是为了将新元素插入到这个位置。但是为了和是否有这个元素做区分，返回需要小于0，
    // 所以在返回之前对结果值进行了取反，让其变成一个负数，
    // 这里对该值再次取反，让其重新变成正数，会将新的键值对插入到该位置
    // 这样也保证了如果有相同的hash值，则这些相同的hash会保存在一起（相邻）
    index = ~index;

    // 如果数组已满，则需要扩容
    if (osize >= mHashes.length) {
        // 如果osize大于两倍基础大小，则扩容为现在的1.5倍（osize >> 1等价于 osize / 2）
        // 如果osize在基础大小的一倍到两倍之间，则扩容为基础大小的两倍
        // 如果osize小于基础大小，则扩容为基础大小
        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;

        // 新建n大小的数组并赋值给mHashes，新建n*2大小的数组并赋值给mArray
        allocArrays(n);

        // 检查是否有其他线程在操作该ArrayMap对象导致mSize发生了变化
        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);
        }

        // 释放两个旧的数组
        // 如果还没有达到缓存的最大值且ohashes的长度为基础长度或基础长度的二倍时，则将这两个数组缓存起来
        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);
        // mArray数组需要后移两位， 
        // index << 1表示起始位置， (index + 1) << 1表示移动后的起始位置，等价于(index << 1) + 2
        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;
}

int indexOf(Object key, int hash) {
    final int N = mSize;

    // 如果当前还没有元素，则对0取反并返回，
    // 注意位运算法则：~0的结果为-1，所以上面put方法中的if (index >= 0)判断是不成立的
    // Important fast case: if nothing is in here, nothing to look for.
    if (N == 0) {
        return ~0;
    }

    // 对mHashes使用二分查找算法查找hash值的位置
    // binarySearch返回的是最后查找的位置，如果没有找到，同样对返回值进行了取反操作
    int index = binarySearchHashes(mHashes, N, hash);

    // 如果不存在这个hash值，则直接返回负数的index
    // If the hash code wasn't found, then we have no entry for this key.
    if (index < 0) {
        return index;
    }

    // 判断在mArray数组中该位置的key和当前要插入的key是否相等
    // 如果是则返回该key的在mHashes数组中的index
    // 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;

    // 当有多个key的hash值相同时，这些相同的hash值会相邻存储
    // 从当前位置开始往后在所有相邻的hash值范围内进行遍历，
    // 当超出这个范围（mHashes[end] != hash时）则停止遍历
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        // 如果找到相等的key时就停止遍历，并返回该位置
        if (key.equals(mArray[end << 1])) return end;
    }

    // Search for a matching key before the index.
    // 从当前位置开始往前在所有相邻的hash值范围内进行遍历
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        // 如果找到相等的key时就停止遍历，并返回该位置
        if (key.equals(mArray[i << 1])) return i;
    }

    // 如果都没找到key，此时end为最后一次遍历的位置，取反后返回
    // Key not found -- return negative value indicating where a
    // new entry for this key should go.  We use the end of the
    // hash chain to reduce the number of array entries that will
    // need to be copied when inserting.
    return ~end;
}

再来看看remove操作：

public V remove(Object key) {
    final int index = indexOfKey(key);
    // 如果存在该key，则移除对应的键值对，并返回value
    if (index >= 0) {
        return removeAt(index);
    }

    // 如果不存在该key，则返回null
    return null;
}

public int indexOfKey(Object key) {
    // 查找key的hash值在mHashes数组上的索引（indexOf方法前面已经讲过了）
    return key == null ? indexOfNull()
                : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}

public V removeAt(int index) {
    // 获取key在mHashes数组上的位置在mArray数组里对应的value值
    final Object old = mArray[(index << 1) + 1];
    // 当前键值对的数量
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        // 如果当前最多只有一对数据，则这对数据移除后，将mHashes和mArray设置为空
        // Now empty.
        if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0");
        freeArrays(mHashes, mArray, osize);
        mHashes = EmptyArray.INT;
        mArray = EmptyArray.OBJECT;
        nsize = 0;
    } else {
        nsize = osize - 1;
        // 如果当前数组容量大于两倍基础容量，且当前使用量不到总容量的1/3，则进行容量收缩操作，
        // 以便释放暂时用不到的内存
        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.
            // 如果当前使用量大于两倍基础容量，则将数组的容量缩小为当前使用量的1.5倍，
            // 否则将数组容量缩小为两倍基础容量
            final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2);

            if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n);

            final int[] ohashes = mHashes;
            final Object[] oarray = mArray;
            // 重新申请两个较小的数组，复制给mHashes和mArray
            allocArrays(n);

            // 检查是否有多线程操作
            if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
                throw new ConcurrentModificationException();
            }

            // 如果要删除的元素在数组中间（不是第一个元素），则先将数组中index之前的元素复制到新数组中
            if (index > 0) {
                if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
                System.arraycopy(ohashes, 0, mHashes, 0, index);
                System.arraycopy(oarray, 0, mArray, 0, index << 1);
            }
            // 如果要删除的元素在数组中间（不是最后一个元素），则将idnex之后的元素复制到新数组中
            if (index < nsize) {
                if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize + " to " + index);
                System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1);
            }
        } else {
            // 如果不需要收缩容量，且删除的不是最后一个元素，则将index之后的元素集体前移一位
            if (index < nsize) {
                if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize + " to " + index);
                System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index);
                System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, (nsize - index) << 1);
            }
            // 将要删除的位置设置为null
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    
    // 检查是否有多线程操作
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }

    // 重新设置尺寸并返回删除的值
    mSize = nsize;
    return (V)old;
}

最后再来看看释放数组和申请数组的操作：

// 释放数组
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    // 如果要释放的数组长度正好是两倍基础容量大小则进行缓存操作
    if (hashes.length == (BASE_SIZE*2)) {
        // 因为缓存在静态变量中的，所以这里需要加锁做线程同步
        synchronized (ArrayMap.class) {
            // 如果还没有达到最大的缓存容量则进行缓存，否则就放弃不缓存
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                // 缓存的时候将array作为一个节点，array[0]用来指向以前的缓存节点，array[1]用来存放hashes数组
                array[0] = mTwiceBaseCache;
                array[1] = hashes;
                // 将array[2]开始到最后的位置里的元素清空
                for (int i=(size<<1)-1; i>=2; i--) {
                    array[i] = null;
                }
                // 更新mTwiceBaseCache和mTwiceBaseCacheSize
                mTwiceBaseCache = array;
                mTwiceBaseCacheSize++;
                if (DEBUG) Log.d(TAG, "Storing 2x cache " + array
                       + " now have " + mTwiceBaseCacheSize + " entries");
            }
        }
    } 
    // 对一倍基础容量的数组进行缓存，逻辑和上面的一样
    else if (hashes.length == BASE_SIZE) {
        synchronized (ArrayMap.class) {
            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");
            }
        }
    }
}

// 申请数组
private void allocArrays(final int size) {
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
        throw new UnsupportedOperationException("ArrayMap is immutable");
    }
 
    // 如果申请的是两倍基础容量大小的数组，则检查是否有缓存数组可用
    if (size == (BASE_SIZE*2)) {
        // 因为缓存时静态变量，所以需要加锁进行线程同步
        synchronized (ArrayMap.class) {
            // 有缓存
            if (mTwiceBaseCache != null) {
                final Object[] array = mTwiceBaseCache;
                mArray = array;
                mTwiceBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mTwiceBaseCacheSize--;
                if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes
                            + " now have " + mTwiceBaseCacheSize + " entries");
                return;
            }
        }
    } 
    // 如果申请的是基础容量大小的数组，则检查是否有缓存数组可用
    else if (size == BASE_SIZE) {
        synchronized (ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[])array[0];
                mHashes = (int[])array[1];
                array[0] = array[1] = null;
                mBaseCacheSize--;
                if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes
                            + " now have " + mBaseCacheSize + " entries");
                return;
            }
        }
    }

    mHashes = new int[size];
    mArray = new Object[size<<1];
}

可见，ArrayMap对数组进行了动态调整，需要扩容的时候进行扩容，不需要的时候进行了缩容操作来及时释放暂时不用的内存。并且对基础容量数组进行了缓存，减少了内存申请的次数。从而在内存的使用方面带来了客观的提升。

但是我们发现，上面查找key的时候使用的是二分查找，这就导致ArrayMap比HashMap的速度要慢，而且删除数据的时候也可能会对数组进行重新调整，所以在使用大量数据的时候ArrayMap的效率比HashMap要低50%。因此官方建议是在小数据量（1000以内）的情况下使用ArrayMap。下面是一段该类的官方注释：

Note that this implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.

二、SparseArray

SparseArray：added in API level 1
SparseArrayCompat：android.support.v4

SparseArray也是android提供的一个特殊的HashMap。相对HashMap，它在内存使用方面做了一些优化，主要体现为：

1. 其内部使用了矩阵压缩算法来优化了稀疏数组；
2. 它的key是int类型，避免了HashMap的自动装箱（将int转换成Integer）；
3. 避免了使用一个额外的实体对象来存储键值对。

和上面的ArrayMap一样，其内部也是使用两个数组来进行存储的。其定义如下：

public class SparseArray<E> implements Cloneable {
    // 存放key的数组
    private int[] mKeys;
    // 存放value的数组
    private Object[] mValues;
    // 键值对数量
    private int mSize;

    private boolean mGarbage = false;
}

我们来看看put操作：

public void put(int key, E value) {
    // 通过二分查找，在mKeys数组中查找key的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        // 如果存在key则直接将value放到mValues数组对应的位置
        // 此时该位置的value可能是当初插入的值，也可能是被删除后标记成的DELETED对象（见后面的delete方法），
        // 但这并不重要，直接用新的值覆盖即可
        mValues[i] = value;
    } else {
        i = ~i;

        // 如果该位置value的值是一个内部固定的对象DELETED，
        // 则说明该位置的键值对被移除了，那么将新的键值对直接存放在该位置
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        // 当删除了数组中间的键值对，会将mGarbage变量设置true（删除的键值对会标记为DELETED），
        // 如果此时数组满了，则需要回收这些被标记为DELETED的位置，腾出来给新的键值对使用
        if (mGarbage && mSize >= mKeys.length) {
            // gc方法的作用就是将数组后面的元素往前移动，覆盖那些被标记为DELETED的位置
            gc();

            // 数组被调整后，重新执行二分查找，来查找key的位置
            // 注意，这里不是为了真正找到有相同的key（前面已经找过了，执行到这里说明数组中是不存在相同key的），
            // 而是为了找到新的键值对的插入点
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        // 将新的键值对插入到数组中
        // 这里的GrowingArrayUtils.insert方法的步骤如下：
        // 1，检查指定数组的容量是否足够，不够则会进行扩容
        // 2，如果插入的位置在数组中间，则会将插入点及之后的元素后移一位
        // 3，在指定的插入点插入新的元素
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

再来看看remove操作：

public void remove(int key) {
    delete(key);
}

public void delete(int key) {
    // 查找要删除的key的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    // 如果找到了则将要删除的位置的value设置为内部的一个固定对象DELETED，标记为已删除
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            // 这里不移动数组中的元素，而是将mGarbage设置为true，然后等数组容量不足时再一起移动
            mGarbage = true;
        }
    }
}

再来看看上面的gc方法具体是怎么实现的：

private void gc() {
    // Log.e("SparseArray", "gc start with " + mSize);

    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;

   // 很简单，就是遍历整个数组，将值是DELETED后面的元素前移，覆盖掉DELETED所在位置
    for (int i = 0; i < n; i++) {
        Object val = values[i];

        if (val != DELETED) {
           // o表示移动过程中，移动后的最后一个有效元素（值不是DELETED）的下下一个位置
           // 如果o不等于i，则将i位置的元素移动到o位置
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }

            o++;
        }
    }

    mGarbage = false;
    mSize = o;

    // Log.e("SparseArray", "gc end with " + mSize);
}

这里的gc方法如果看不懂的话可以看下面这张图：

SparseArray.png

同样，因为SparseArray采用了二分查找，所以在大数据下，速度没有HashMap快。官方也是建议在数据不超过1000条的情况下才用来代替HashMap：

Note that this container keeps its mappings in an array data structure, using a binary search to find keys. The implementation is not intended to be appropriate for data structures that may contain large numbers of items. It is generally slower than a traditional HashMap, since lookups require a binary search and adds and removes require inserting and deleting entries in the array. For containers holding up to hundreds of items, the performance difference is not significant, less than 50%.

总结

备注：上面ArrayMap和SparseArray的慢是在大量数据的情况下，当数据少于1000的时候速度和HashMap是差不多的。

三、SparseIntArray

added in API level 1
SparseIntArray是SparseArray的一个特例，它的键和值都是int类型。相比SparseArray，它的值也避免了自动装箱。所以性能比SparseArray高些。

四、SparseBooleanArray

added in API level 1
SparseBooleanArray也是SparseArray的一个特例，它的键是int类型的，值是boolean类型。相比SparseArray，它的值也避免了自动装箱。所以性能比SparseArray高些。

五、SparseLongArray

added in API level 18
SparseLongArray也是SparseArray的一个特例，它的键是int类型的，值是long类型。相比SparseArray，它的值也避免了自动装箱。所以性能比SparseArray高些。

六、LongSparseArray

added in API level 16 or in android.support.v4
LongSparseArray和SparseArray类似，只是它的键是long类型的。其他和SparseArray无差别。

总结

java为我们提供了四种主要类用来存储键值对。其中：

• HashMap高效的实现了存储键值对的基本功能；
• LinkedHashMap在HashMap的基础上增加了键值对的有序性（插入顺序和访问顺序）；
• TreeMap在HashMap的基础上增加了键值对的自定义顺序；
• Hashtable在HashMap的基础上增加了线程同步。

另外，java还提供了三种HashMap的特殊类：

• EnumMap的key被限定为只能是enum；
• IdentityHashMap的key必须绝对相等（必须是同一个对象）；
• WeakHashMap实现了多key-value的弱引用。

android提供了两种对HashMap的内存使用做了优化的类：ArrayMap和SparseArray。ArrayMap和HashMap一样，key和value都是Object。SparseArray的key被限定为int。他们都是以牺牲性能为代价来优化了内存的使用。官方建议是当数据不超过1000条的时候使用他们来代替HashMap（这种情况下性能差不多）。

同样，针对SparseArray，android也提供了几种特殊类：

• SparseIntArray的键是int类型， 值也是int类型；
• SparseBooleanArray的键是int类型，值是boolean类型；
• SparseLongArray的键是int类型，值是long类型；
• LongSparseArray的键是long类型，值是Object类型。

关于Map接口的数据结构类基本就这些了，还是那句话：只要大家明白了它们各自的实现原理也就知道了它们各自的区别和适合的使用场景。