傳送門(mén)：Java（Android）數(shù)據(jù)結(jié)構(gòu)匯總 -- 總綱

簡(jiǎn)介

這篇主要來(lái)整理下基于Map接口實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類秫筏。Map集合主要用來(lái)存儲(chǔ)鍵值對(duì)庆械。它的相關(guān)實(shí)現(xiàn)類有java.util包的HashMap职辅、LinkedHashMap蹬挺、Hashtable刨裆、TreeMap澈圈、EnumMap、IdentityHashMap帆啃、WeakHashMap和android.util包的ArrayMap瞬女、SparseArray、SparseIntArray努潘、SparseBooleanArray诽偷、SparseLongArray、LongSparseArray等疯坤。下面分別一一來(lái)講解报慕。

Java部分

一、HashMap

HashMap應(yīng)該也是我們java中最常用的存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)類了贴膘。它內(nèi)部是以數(shù)組+鏈表（從1.8版本開(kāi)始引入了紅黑樹(shù)）的形式來(lái)存放鍵值對(duì)的卖子。

基本原理

HashMap是通過(guò)對(duì)key的hash值進(jìn)行轉(zhuǎn)換來(lái)定位每個(gè)key在內(nèi)部數(shù)組上的位置。數(shù)組的每個(gè)元素又都是一個(gè)鏈表刑峡，這樣如果一個(gè)位置有多個(gè)鍵值對(duì)的時(shí)候就可以依次存放在這個(gè)鏈表上洋闽。至于為什么每個(gè)位置可能會(huì)存在多個(gè)值玄柠，這個(gè)請(qǐng)看后面。

看了上面的原理介紹诫舅，可能還比較懵羽利。沒(méi)事，下面將一一具體來(lái)介紹刊懈。

具體實(shí)現(xiàn)

Key的Hash值計(jì)算分兩步：

• 第一步：正常計(jì)算出key的hash值（調(diào)用key的hashCode()方法这弧，如果key是null則其hash值是0）；
• 第二步：對(duì)得到的hash值進(jìn)行擾亂虚汛，目的是為了讓hash值能盡可能的均勻分布匾浪。

  我們認(rèn)為HashMap的數(shù)組上每個(gè)位置只有一個(gè)元素是最理想的，擾亂操作的目的就是為了讓hash值能盡可能的均勻分布（原因看后面如何將hash值轉(zhuǎn)換為數(shù)組索引的介紹）卷哩。

為什么要用key的hash值而不直接用key蛋辈，這里先不講，看完下面的源碼再說(shuō)：

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

// 計(jì)算key的HashCode
static final int hash(Object key) {
    int h;
    // 首先将谊，如果key是null冷溶，則直接返回0（這里也說(shuō)明HashMap支持null作為key）
    // 如果key不是null，就計(jì)算key的hashCode值并存放到h變量中
    // 最后進(jìn)行擾亂操作尊浓，在1.8版本中是h ^ (h >>> 16)逞频，在1.8版本之前還會(huì)有更多次的位運(yùn)算
    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;

    // 如果數(shù)組（table）還沒(méi)有初始化，則進(jìn)行數(shù)組的初始化操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 重點(diǎn)
    // 這里通過(guò)(n - 1) & hash計(jì)算將hash值轉(zhuǎn)換成數(shù)組上的索引  --> 解釋1（具體解釋見(jiàn)后面）
    // 這里通過(guò)hash值計(jì)算出key在數(shù)組上位置栋齿，這樣就可以直接在這個(gè)位置上的鏈表里面去查
    // 找有沒(méi)有指定的key苗胀，而不需要在整個(gè)數(shù)組上去查找（這樣大大減少了查詢范圍）
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果該位置還沒(méi)有元素，則直接新建一個(gè)節(jié)點(diǎn)并存放在該位置
        tab[i] = newNode(hash, key, value, null);
    else {
        // 整個(gè)else的邏輯就是為了在該鏈表上查找是否存在相同的key瓦堵，如果存在則將該節(jié)點(diǎn)賦值給e柒巫，如果沒(méi)有找到e就為null

        // Node節(jié)點(diǎn)存儲(chǔ)的值有key、key的hashcode谷丸、value、next（下一個(gè)節(jié)點(diǎn)的引用）四個(gè)數(shù)據(jù)
        Node<K,V> e; K k;

        // 判斷鏈表的頭節(jié)點(diǎn)是否和本次插入的key相同 --> 解釋2
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 判斷鏈表是否是紅黑樹(shù)
        else if (p instanceof TreeNode)
            // 在紅黑樹(shù)中查找是否存在相同的key
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 遍歷鏈表应结，查找是否存在相同的key
            for (int binCount = 0; ; ++binCount) {
                // 整個(gè)鏈表都沒(méi)有相同key刨疼，則新建一個(gè)node，并添加到鏈表結(jié)尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 判斷鏈表的長(zhǎng)度是否達(dá)到了TREEIFY_THRESHOLD鹅龄，
                    // 如果達(dá)到就將鏈表轉(zhuǎn)換成紅黑樹(shù)（紅黑樹(shù)查詢速度比鏈表更快）
                    // 紅黑樹(shù)是1.8版本引入的
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // 如果找到了有相同key的節(jié)點(diǎn)揩慕，則跳出循環(huán)
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;

                p = e;
            }
        }

        // 如果e不為空，表示e所指向的節(jié)點(diǎn)的key和當(dāng)前要插入的key相同扮休，此時(shí)用新的value替換該節(jié)點(diǎn)的value迎卤，而不新建node節(jié)點(diǎn)
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;

    // 如果當(dāng)前數(shù)組的長(zhǎng)度超過(guò)了設(shè)定的閾值，則進(jìn)行數(shù)組擴(kuò)容
    if (++size > threshold)
        resize();

    afterNodeInsertion(evict);
    return null;
}

解釋1：看下面幾個(gè)問(wèn)題：

• 問(wèn)題1：為什么不直接使用key而要使用key的hash值玷坠？

  如果直接使用key蜗搔，那么在查找的時(shí)候需要調(diào)用key的equals方法去逐個(gè)比較劲藐，對(duì)吧。首先逐個(gè)比較效率就不高（萬(wàn)一要查找的節(jié)點(diǎn)正好是最后一個(gè)樟凄，那豈不是要將整個(gè)集合都比較一遍聘芜？），再加上equals方法本身效率也不高缝龄，這樣如果直接使用key的話整個(gè)HashMap的性能就很差汰现。

  而用hash值可以直接定位到數(shù)組上的某個(gè)位置，這樣只需要在這個(gè)位置的鏈表上進(jìn)行查找就行了叔壤，從而大大縮小了查找范圍和比較的次數(shù)瞎饲。

• 問(wèn)題2：那為什么又不直接用hash值作為數(shù)組上的索引？

  怕數(shù)組越界對(duì)吧炼绘。hash值的范圍不可控嗅战，直接用hash值作為數(shù)組索引容易造成數(shù)組下標(biāo)越界。為了解決這個(gè)問(wèn)題饭望，于是想出了使用hash值和當(dāng)前數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算仗哨，將結(jié)果作為數(shù)組的索引，即index = hash % length铅辞。index只會(huì)在0到length - 1之間厌漂，這樣就不怕數(shù)組下標(biāo)越界了。

• 問(wèn)題3：那為什么用的是(n - 1) & hash斟珊，而不是hash % n吶苇倡？

  其實(shí)早期版本就是用hash % n，但是為了追求效率囤踩，后來(lái)就改成了位運(yùn)算(n - 1) & hash（位運(yùn)速度比取模運(yùn)算快）旨椒。

• 問(wèn)題4：為什么(n - 1) & hash和hash % n是等價(jià)的？

  這里利用了HashMap的一個(gè)特性：HashMap規(guī)定其容量必須是2的n次方（最大為2³⁰次方）,那么n肯定就是2^xx次方了堵漱，用二進(jìn)制表示就是1000...00综慎，最前面是1，后面全是0(假設(shè)有k個(gè)0)勤庐，那么n-1就全變成1了111...1111（k-1個(gè)1）示惊，hash ^ (n - 1)得到的最大值就是n-1，最小值是0愉镰。效果和hash % n一樣米罚，只是改為位運(yùn)算了。位運(yùn)算比取模運(yùn)算更快丈探。

解釋2：注意這里的比較順序：

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

1. 為時(shí)還要比較p.hash == hash录择？

   因?yàn)槲覀兦懊媸峭ㄟ^(guò)hash取模來(lái)實(shí)現(xiàn)數(shù)組上的定位的，所以在數(shù)組上同一個(gè)位置的hash值不一定就相等，比如 25和33兩個(gè)hash值隘竭，他們對(duì)8取模結(jié)果都是1塘秦。所以需要進(jìn)行hash值的比較。

2. hash值相等了货裹，為什么還要進(jìn)一步比較key嗤形？

   因?yàn)閮蓚€(gè)不同的key計(jì)算出的hash值可能相同（也就是hash碰撞），所以為了解決這個(gè)問(wèn)題需要進(jìn)一步比較key弧圆。

3. 為什么要比較k == key赋兵，而不直接用equals方法？

   因?yàn)镠aspMap允許null作為key搔预，所以不能直接調(diào)用equals來(lái)比較霹期。

從上面的分析我們還能得出三個(gè)HashMap的特性：

1. null可以作為HashMap的key和value。因?yàn)閗ey是不能重復(fù)了拯田，所以也就只允許一個(gè)null作為key历造，但是允許多個(gè)value的值是null；
2. HashMap的key是根據(jù)其hash值隨機(jī)分布在數(shù)組上的船庇，所以HashMap的記錄是無(wú)序的吭产；
3. 我們?cè)贖ashMap的源碼中沒(méi)有看到任何同步相關(guān)的代碼，所以HashMap不是線程安全的鸭轮。

二臣淤、LinkedHashMap

LinkedHashMap繼承至HashMap，在HashMap的基礎(chǔ)上新增了一個(gè)雙向鏈表來(lái)實(shí)現(xiàn)了記錄的有序化窃爷。

大家不要被這個(gè)名字迷惑了邑蒋，是不是也和ArrayList跟LinkedList一樣一個(gè)是用數(shù)組實(shí)現(xiàn)的一個(gè)是用鏈表實(shí)現(xiàn)的吶？其實(shí)不是的按厘，LinkedHashMap的主要功能是實(shí)現(xiàn)了內(nèi)部元素的有序化（上面說(shuō)了HashMap的元素是無(wú)序的）医吊。

LinkedHashMap的有序有兩種模式：插入順序和訪問(wèn)順序。具體使用哪種順序模式是在構(gòu)造方法處指定的逮京。

插入順序：就是按照插入的時(shí)間排序卿堂，先插入的數(shù)據(jù)排在前面，后插入的數(shù)據(jù)排在后面懒棉。
訪問(wèn)順序：就是按照最近訪問(wèn)進(jìn)行排序御吞，訪問(wèn)時(shí)間越近的數(shù)據(jù)排在越靠后的位置，訪問(wèn)時(shí)間越遠(yuǎn)的數(shù)據(jù)越排在靠前的位置（實(shí)現(xiàn)方式就是當(dāng)元素每次被訪問(wèn)后就將其移動(dòng)到鏈表結(jié)尾）漓藕。LruCache就是基于此原理實(shí)現(xiàn)的。

來(lái)看這幾個(gè)構(gòu)造方法：

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用來(lái)指定是否使用訪問(wèn)順序模式享钞，true表示使用訪問(wèn)順序模式，否則使用插入順序模式，默認(rèn)使用插入順序模式栗竖。

具體實(shí)現(xiàn)

首先暑脆，LinkedHashMap新增了一個(gè)LinkedHashMapEntry，它繼承至HashMap的Node類狐肢，在其中增加了兩個(gè)自己用于鏈表維護(hù)的變量：

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
    // 新增了before添吗、after兩個(gè)字段，LinkedHashMap使用這兩個(gè)字段來(lái)維護(hù)自己的雙向鏈表
    LinkedHashMapEntry<K,V> before, after;
    LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

然后份名，LinkedHashMap重寫(xiě)了HashMap的newNode()方法（HashMap每次新增節(jié)點(diǎn)都是通過(guò)這個(gè)方法來(lái)創(chuàng)建一個(gè)節(jié)點(diǎn)）來(lái)實(shí)現(xiàn)每次新增數(shù)據(jù)的時(shí)候都能將新增的數(shù)據(jù)添加到自己維護(hù)的鏈表的結(jié)尾碟联，從而保證了插入順序：

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);

    // 調(diào)用linkNodeLast方法將這個(gè)新增的節(jié)點(diǎn)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重寫(xiě)了HashMap的afterNodeRemoval()方法（HashMap在刪除數(shù)據(jù)的時(shí)候會(huì)回調(diào)該方法）以保證數(shù)據(jù)的同步：

// 重寫(xiě)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;
}

最后僵腺，為了維護(hù)訪問(wèn)順序鲤孵，LinkedHashMap重寫(xiě)了get()、getOrDefault()和afterNodeAccess()三個(gè)方法（當(dāng)HashMap修改了數(shù)據(jù)時(shí)辰如，比如put了一個(gè)相同key不同value普监，會(huì)回調(diào)afterNodeAccess()方法）。具體代碼如下：

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

    // 如果使用的訪問(wèn)順序模式琉兜，則調(diào)用afterNodeAccess方法來(lái)移動(dòng)節(jié)點(diǎn)到鏈表末尾
    if (accessOrder)
        afterNodeAccess(e);

    return e.value;
}

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

    // 如果使用的訪問(wèn)順序模式凯正，則調(diào)用afterNodeAccess方法來(lái)移動(dòng)節(jié)點(diǎn)到鏈表末尾
   if (accessOrder)
       afterNodeAccess(e);
   return e.value;
}

// 重寫(xiě)HashMap的afterNodeAccess方法，監(jiān)聽(tīng)節(jié)點(diǎn)的修改
void afterNodeAccess(Node<K,V> e) { 
    LinkedHashMapEntry<K,V> last;

    // 如果使用的訪問(wèn)順序模式且修改的不是最后一條數(shù)據(jù)，則將被修改的節(jié)點(diǎn)移動(dòng)到鏈表末尾
    if (accessOrder && (last = tail) != e) {
        LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;

        // 先從鏈表中移除該節(jié)點(diǎn)
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;


        // 將該節(jié)點(diǎn)重新添加到鏈表結(jié)尾
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;

        ++modCount;
    }
}

三斗锭、TreeMap

TreeMap內(nèi)部是使用紅黑樹(shù)來(lái)實(shí)現(xiàn)的志于。對(duì)紅黑樹(shù)不了解的可以看github上的這篇文章介紹：教你透徹了解紅黑樹(shù)。

它與HashMap的區(qū)別如下：

因?yàn)橐獙?duì)key進(jìn)行排序奸汇，所以key必須要實(shí)現(xiàn)自然排序和定制排序中的一種。自然排序就是key要繼承java.lang.Comparable接口往声，而定制排序則需要在創(chuàng)建TreeMap對(duì)象的時(shí)候指定一個(gè)實(shí)現(xiàn)了java.lang.Comparable接口的對(duì)象擂找，源碼如下：

public TreeMap() {
    // 如果使用這個(gè)構(gòu)造方法，key就必須要實(shí)現(xiàn)Comparable接口
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    // 如果使用這個(gè)構(gòu)造方法浩销，則需要指定一個(gè)comparator對(duì)象贯涎，此時(shí)key就不需要實(shí)現(xiàn)Comparable接口
    this.comparator = comparator;
}

首先還是來(lái)看一下它的Entity類：

static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
    // 存放該節(jié)點(diǎn)值的變量（key和value）
    K key;
    V value;

    // 左子節(jié)點(diǎn)
    TreeMapEntry<K,V> left;
    // 右子節(jié)點(diǎn)
    TreeMapEntry<K,V> right;
    // 父節(jié)點(diǎn)
    TreeMapEntry<K,V> parent;
    // 該節(jié)點(diǎn)顏色
    boolean color = BLACK;
    ...
}

再來(lái)看看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主要是對(duì)key的類型和是否是null值進(jìn)行檢查
        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);
}

因?yàn)門(mén)reeMap的主要邏輯是紅黑樹(shù)，如果對(duì)紅黑樹(shù)不了解的需要先去學(xué)習(xí)下紅黑樹(shù)慢洋。這里因?yàn)槠蚓筒欢嘀v塘雳。

四、Hashtable

Hashtable和HashMap類似普筹，不同之處是Hashtable實(shí)現(xiàn)了線程同步败明。目前已經(jīng)不建議使用Hashtable了，這里就不多講解了太防。如果需要線程同步妻顶，給的建議是使用java.util.concurrent包下的ConcurrentHashMap類來(lái)代替。下面是來(lái)自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是一個(gè)特殊的Map讳嘱，它的key被限定為只能是枚舉型幔嗦，并使用key的ordinal值作為其內(nèi)部數(shù)組的下標(biāo)。這樣有兩個(gè)好處：一是不需要再對(duì)key進(jìn)行hash計(jì)算沥潭；二是因?yàn)槭褂玫氖?code>ordinal值(每個(gè)枚舉類里面的枚舉常量的ordinal值有序且唯一)邀泉，所以每個(gè)位置對(duì)應(yīng)唯一一個(gè)key，所以也就不再需要鏈表钝鸽，直接用一個(gè)數(shù)組就能實(shí)現(xiàn)汇恤。因此EnumMap的效率比HashMap更高。

關(guān)于ordinal值：每個(gè)枚舉型常量都有一個(gè)ordinal()方法寞埠，用于返回該枚舉常量的序號(hào)（從0開(kāi)始）屁置。如：

 enum Light {
    RED, GREEN, YELLOW;
 }

則：RED.ordinal()為0， GREEN.ordinal()為1仁连， YELLOW.ordinal()為2蓝角。

還是來(lái)看下源碼：

public V put(K key, V value) {
    // 容錯(cuò)處理：檢查key是否是指定的枚舉類型
    typeCheck(key);

    // 可以看出，確實(shí)是直接使用key的ordinal值作為數(shù)組的下標(biāo)索引饭冬。
    int index = key.ordinal();
    Object oldValue = vals[index];
    // EnumMap內(nèi)部不直接存儲(chǔ)null使鹅，如果是null則會(huì)用maskNull方法將其轉(zhuǎn)換成一個(gè)內(nèi)部特定的對(duì)象
    vals[index] = maskNull(value);
    // 為什么不直接存儲(chǔ)null，看這里就明白了昌抠，如果某個(gè)位置的值為null患朱，表示這個(gè)位置沒(méi)有存儲(chǔ)值，而不是存儲(chǔ)了一個(gè)null值
    if (oldValue == null)
        // 如果當(dāng)前位置以前的值是null炊苫，表示這個(gè)位置以前沒(méi)有存儲(chǔ)值裁厅，則會(huì)執(zhí)行size++，否則就是值的替換侨艾，size就不會(huì)變
        size++;

    // 檢查值如果是內(nèi)部特定的對(duì)象执虹，則用unmaskNull方法將其重新轉(zhuǎn)換成null返回
    return unmaskNull(oldValue);
}

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

可以看出，EnumMap還是非常簡(jiǎn)單的唠梨。相比HashMap來(lái)說(shuō)袋励，它簡(jiǎn)化了存儲(chǔ)邏輯，使得性能進(jìn)一步得到了提升当叭。缺點(diǎn)是限制了key只能是枚舉型茬故，只能使用枚舉型。同樣蚁鳖，EnumMap也不是線程安全的磺芭。

使用場(chǎng)景：在某些使用枚舉型作為key的特定場(chǎng)景下用來(lái)代替HashMap，性能會(huì)得到進(jìn)一步提升醉箕。

六钾腺、IdentityHashMap

IdentityHashMap也是一個(gè)特殊的Map甘邀，它要求兩個(gè)key嚴(yán)格相等（key1==key2）才算是同一個(gè)key。而它的存儲(chǔ)結(jié)構(gòu)是數(shù)組垮庐。key-value在數(shù)組上是挨著存儲(chǔ)的，比如table[0]=key坞琴，table[1]=value哨查。來(lái)看它的一段源碼就清楚了：

public V put(K key, V value) {
    // 如果key是null，則將其轉(zhuǎn)換成一個(gè)內(nèi)部固定對(duì)象NULL_KEY 
    final Object k = maskNull(key);

    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        // 這里將key映射到數(shù)組上的方式和HashMap一樣：將key的hash值和數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算來(lái)得出key在數(shù)組上的位置
        // 這里有個(gè)細(xì)微差別就是計(jì)算出的值是偶數(shù)（0剧辐、2寒亥、4、...）正好對(duì)應(yīng)數(shù)組的奇數(shù)位（1荧关、3溉奕、5、...）忍啤，
        // 這樣也保證了數(shù)組上的存儲(chǔ)順序?yàn)椋簁ey加勤、value、key同波、value鳄梅、...
        int i = hash(k, len);

        // 從i位置開(kāi)始往后遍歷數(shù)組，i = nextKeyIndex(i, len)相當(dāng)于 i += 2
        for (Object item; (item = tab[i]) != null; i = nextKeyIndex(i, len)) {
            // 這里就是IdentityHashMap的主要特性了：只有當(dāng)兩個(gè)key1==key2才算是同一個(gè)key（即便equals方法相等也不算）
            if (item == k) {
                // 如果該位置和插入的key相等未檩，那么將value存放在下一個(gè)位置（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的對(duì)象引用體系有關(guān)。HashMap是直接持有key-value的強(qiáng)引用冤狡，只要HashMap不主動(dòng)刪除這些key-value（且HashMap本身不能被回收時(shí)）孙蒙，他們就不會(huì)被系統(tǒng)回收。而WeakHashMap則是持有key的一個(gè)弱引用悲雳，這樣就可以被系統(tǒng)主動(dòng)回收挎峦。

Java的對(duì)象引用系統(tǒng)有四種：強(qiáng)引用、軟引用怜奖、弱引用和虛引用浑测。

1. 強(qiáng)引用：就是平時(shí)我們直接對(duì)對(duì)象的引用，比如Object h = new Object()歪玲，這里的h就是一個(gè)強(qiáng)引用迁央，在h不超出范圍的情況下，只要h不被設(shè)置為null滥崩，這個(gè)對(duì)象就不會(huì)被系統(tǒng)回收岖圈；
2. 軟引用：使用SoftReference來(lái)實(shí)現(xiàn)（具體用法這里不做介紹）。在系統(tǒng)執(zhí)行g(shù)c的時(shí)候钙皮，如果檢查到內(nèi)存不足蜂科，則會(huì)回收SoftReference持有的對(duì)象顽决。如果我們想在持有的對(duì)象被回收后做一些額外處理，則可以配合ReferenceQueue一起使用导匣，將SoftReference對(duì)象和ReferenceQueue關(guān)聯(lián)后才菠，當(dāng)SoftReference持有的對(duì)象被回收后會(huì)將SoftReference對(duì)象添加到ReferenceQueue中；
3. 弱引用：使用WeakReference來(lái)實(shí)現(xiàn)（具體用法這里不做介紹）贡定，在系統(tǒng)執(zhí)行g(shù)c的時(shí)候赋访，會(huì)回收SoftReference持有的對(duì)象。注意與軟引用的區(qū)別缓待，軟引用是在內(nèi)存不足時(shí)才被回收蚓耽，而弱引用則是只要執(zhí)行g(shù)c就會(huì)被回收。如果我們想在持有的對(duì)象被回收后做一些額外處理旋炒，則可以配合ReferenceQueue一起使用步悠，將WeakReference對(duì)象和ReferenceQueue關(guān)聯(lián)后，當(dāng)WeakReference持有的對(duì)象唄回收后會(huì)將WeakReference對(duì)象添加到ReferenceQueue中瘫镇；
4. 虛引用：使用PhantomReference來(lái)實(shí)現(xiàn)（具體用法這里不做介紹）鼎兽。它和軟引用以及弱引用不同，它必須配合ReferenceQueue一起使用汇四，它不會(huì)主動(dòng)清除引用接奈，而是在對(duì)象將要被回收時(shí)會(huì)將其添加到隊(duì)列（軟引用和弱引用是在對(duì)象被回收之后才添加到隊(duì)列）。

我們還是來(lái)看看它的源碼實(shí)現(xiàn)通孽，先看它的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的引用對(duì)象背苦。同時(shí)和一個(gè)ReferenceQueue進(jìn)行了關(guān)聯(lián)互捌，這樣當(dāng)key被回收時(shí)WeakHashMap就能收到通知，將這個(gè)實(shí)體對(duì)象從鏈表中移除行剂。

我們?nèi)魏我粋€(gè)操作秕噪，比如調(diào)用get、put厚宰、size等方法的時(shí)候腌巾，都會(huì)自動(dòng)調(diào)用expungeStaleEntries()方法來(lái)檢查ReferenceQueue隊(duì)列里是否有已經(jīng)被回收的對(duì)象，如果有則將其移除铲觉，源碼如下：

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

public int size() {
    if (size == 0)
        return 0;
    // 調(diào)用expungeStaleEntries方法澈蝙，移除已經(jīng)被回收的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;
            }
        }
    }
}

源碼比較簡(jiǎn)單撵幽，這里就不多說(shuō)了灯荧。有個(gè)需要注意的地方就是在使用WeakHashMap的時(shí)候其key外部不要有他的引用，否則就失去了WeakHashMap的意義（如果有其他引用則會(huì)導(dǎo)致key不能被回收）盐杂。還有個(gè)特別主意的地方就是如果key用的是一個(gè)字符串常量時(shí)逗载，它是不會(huì)被回收的哆窿，因?yàn)橄到y(tǒng)會(huì)自動(dòng)保留對(duì)該字符串對(duì)象的強(qiáng)引用。如：

WeakHashMap wak = new WeakHashMap();
// 這種寫(xiě)法是不會(huì)被回收的厉斟，因?yàn)?hello"是一個(gè)字符串常量挚躯，系統(tǒng)會(huì)自動(dòng)保留對(duì)該字符串對(duì)象的強(qiáng)引用
wak.put("hello", obj);

總結(jié)

Android部分

一、ArrayMap

added in version 22.1.0 or android.support.v4

ArrayMap是android對(duì)HashMap在內(nèi)存使用上的一個(gè)優(yōu)化版本擦秽。內(nèi)存優(yōu)化主要體現(xiàn)在兩個(gè)地方：

1. 每次擴(kuò)容都是增加當(dāng)前容量的0.5倍（當(dāng)前容量大于兩倍BASE_SIZE時(shí)）秧均，hashMap是增加當(dāng)前容量的一倍；
2. 當(dāng)容量的使用率不到1/3時(shí)會(huì)收縮容量号涯，釋放多余的空間。

ArrayMap內(nèi)部是使用兩個(gè)數(shù)組來(lái)實(shí)現(xiàn)的锯七。一個(gè)數(shù)組用來(lái)保存key的hash值链快，另一個(gè)數(shù)組用來(lái)保存key和value（每相鄰的兩個(gè)位置表示一個(gè)鍵值對(duì)，前面的是key眉尸，后面的是value）域蜗。

另外，ArrayMap對(duì)兩種基礎(chǔ)容量數(shù)組進(jìn)行了緩存噪猾，這樣加快了數(shù)組的構(gòu)建過(guò)程和內(nèi)存的利用率（減少了頻繁的內(nèi)存申請(qǐng)釋放）霉祸。

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

    // 基礎(chǔ)容量大小
    private static final int BASE_SIZE = 4;

    // 基礎(chǔ)容量數(shù)組的緩存
    // 當(dāng)需要擴(kuò)容時(shí)，如果當(dāng)前使用的是基礎(chǔ)容量袱蜡，則會(huì)將當(dāng)前的mHashes和mArray進(jìn)行緩存丝蹭。
    // 當(dāng)縮小容量到基礎(chǔ)容量（或其他ArrayMap對(duì)象需要基礎(chǔ)容量數(shù)組）時(shí)，會(huì)將其從緩存中取出使用坪蚁。
    // 存儲(chǔ)方式：mBaseCache有點(diǎn)像是一個(gè)鏈表奔穿，要緩存的mArray數(shù)組作為鏈表的節(jié)點(diǎn)，
    // mArray[0]指向上一個(gè)節(jié)點(diǎn)敏晤，mArray[1]存儲(chǔ)當(dāng)前的mHashes數(shù)組
    static Object[] mBaseCache;
    // 基礎(chǔ)容量數(shù)組的當(dāng)前緩存數(shù)量
    static int mBaseCacheSize;

    // 兩倍基礎(chǔ)容量數(shù)組的緩存
    // 原理同上
    static Object[] mTwiceBaseCache;
    // 兩倍基礎(chǔ)容量數(shù)組的當(dāng)前緩存數(shù)量
    static int mTwiceBaseCacheSize;

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

    // 用來(lái)存放key的hash值
    int[] mHashes;
    // 用來(lái)存放鍵值對(duì)
    Object[] mArray;
    // 鍵值對(duì)數(shù)量
    int mSize;
}

來(lái)看看put操作：

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

    // 計(jì)算key的hash值以及hash值在mHashes數(shù)組上的索引
    if (key == null) {
        hash = 0;
        index = indexOfNull();
    } else {
        hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
        index = indexOf(key, hash);
    }

    // 如果索引不小于0贱田，表示這個(gè)key存在，這直接替換原來(lái)的值
    if (index >= 0) {
        // key的hash值在mHashes數(shù)組上的索引是index嘴脾，
        // 那么對(duì)應(yīng)的key在mArray數(shù)組上的存儲(chǔ)位置為index * 2男摧，value在mArray數(shù)組上的存儲(chǔ)位置為idnex * 2 + 1
        // 計(jì)算value的存儲(chǔ)位置(index<<1) + 1也就是index * 2 + 1
        index = (index<<1) + 1;
        // 用新的值替換舊的值，并返回舊的值
        final V old = (V)mArray[index];
        mArray[index] = value;
        return old;
    }

    // indexOf方法在查找位置的時(shí)候如果沒(méi)有找到key的hash值時(shí)會(huì)返回最后一次查找的位置译打，
    // 目的是為了將新元素插入到這個(gè)位置耗拓。但是為了和是否有這個(gè)元素做區(qū)分，返回需要小于0扶平，
    // 所以在返回之前對(duì)結(jié)果值進(jìn)行了取反帆离，讓其變成一個(gè)負(fù)數(shù)，
    // 這里對(duì)該值再次取反结澄，讓其重新變成正數(shù)哥谷，會(huì)將新的鍵值對(duì)插入到該位置
    // 這樣也保證了如果有相同的hash值岸夯，則這些相同的hash會(huì)保存在一起（相鄰）
    index = ~index;

    // 如果數(shù)組已滿，則需要擴(kuò)容
    if (osize >= mHashes.length) {
        // 如果osize大于兩倍基礎(chǔ)大小们妥，則擴(kuò)容為現(xiàn)在的1.5倍（osize >> 1等價(jià)于 osize / 2）
        // 如果osize在基礎(chǔ)大小的一倍到兩倍之間猜扮，則擴(kuò)容為基礎(chǔ)大小的兩倍
        // 如果osize小于基礎(chǔ)大小，則擴(kuò)容為基礎(chǔ)大小
        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);

        // 保存當(dāng)前的兩個(gè)數(shù)組引用
        final int[] ohashes = mHashes;
        final Object[] oarray = mArray;

        // 新建n大小的數(shù)組并賦值給mHashes监婶，新建n*2大小的數(shù)組并賦值給mArray
        allocArrays(n);

        // 檢查是否有其他線程在操作該ArrayMap對(duì)象導(dǎo)致mSize發(fā)生了變化
        if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
            throw new ConcurrentModificationException();
        }

        // 如果擴(kuò)容成功旅赢，則將舊數(shù)組中的元素復(fù)制到新數(shù)組中
        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);
        }

        // 釋放兩個(gè)舊的數(shù)組
        // 如果還沒(méi)有達(dá)到緩存的最大值且ohashes的長(zhǎng)度為基礎(chǔ)長(zhǎng)度或基礎(chǔ)長(zhǎng)度的二倍時(shí)，則將這兩個(gè)數(shù)組緩存起來(lái)
        freeArrays(ohashes, oarray, osize);
    }

    // 如果插入的位置在數(shù)組中間惑惶，則將從插入位置開(kāi)始的元素集體后移一位
    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數(shù)組需要后移兩位煮盼， 
        // index << 1表示起始位置， (index + 1) << 1表示移動(dòng)后的起始位置带污，等價(jià)于(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();
        }
    }

    // 將鍵值對(duì)插入到數(shù)組中
    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;

    // 如果當(dāng)前還沒(méi)有元素僵控，則對(duì)0取反并返回，
    // 注意位運(yùn)算法則：~0的結(jié)果為-1鱼冀，所以上面put方法中的if (index >= 0)判斷是不成立的
    // Important fast case: if nothing is in here, nothing to look for.
    if (N == 0) {
        return ~0;
    }

    // 對(duì)mHashes使用二分查找算法查找hash值的位置
    // binarySearch返回的是最后查找的位置报破，如果沒(méi)有找到，同樣對(duì)返回值進(jìn)行了取反操作
    int index = binarySearchHashes(mHashes, N, hash);

    // 如果不存在這個(gè)hash值千绪，則直接返回負(fù)數(shù)的index
    // If the hash code wasn't found, then we have no entry for this key.
    if (index < 0) {
        return index;
    }

    // 判斷在mArray數(shù)組中該位置的key和當(dāng)前要插入的key是否相等
    // 如果是則返回該key的在mHashes數(shù)組中的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;

    // 當(dāng)有多個(gè)key的hash值相同時(shí)充易，這些相同的hash值會(huì)相鄰存儲(chǔ)
    // 從當(dāng)前位置開(kāi)始往后在所有相鄰的hash值范圍內(nèi)進(jìn)行遍歷，
    // 當(dāng)超出這個(gè)范圍（mHashes[end] != hash時(shí)）則停止遍歷
    for (end = index + 1; end < N && mHashes[end] == hash; end++) {
        // 如果找到相等的key時(shí)就停止遍歷荸型，并返回該位置
        if (key.equals(mArray[end << 1])) return end;
    }

    // Search for a matching key before the index.
    // 從當(dāng)前位置開(kāi)始往前在所有相鄰的hash值范圍內(nèi)進(jìn)行遍歷
    for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) {
        // 如果找到相等的key時(shí)就停止遍歷盹靴，并返回該位置
        if (key.equals(mArray[i << 1])) return i;
    }

    // 如果都沒(méi)找到key，此時(shí)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;
}

再來(lái)看看remove操作：

public V remove(Object key) {
    final int index = indexOfKey(key);
    // 如果存在該key鹉究，則移除對(duì)應(yīng)的鍵值對(duì)，并返回value
    if (index >= 0) {
        return removeAt(index);
    }

    // 如果不存在該key踪宠，則返回null
    return null;
}

public int indexOfKey(Object key) {
    // 查找key的hash值在mHashes數(shù)組上的索引（indexOf方法前面已經(jīng)講過(guò)了）
    return key == null ? indexOfNull()
                : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode());
}

public V removeAt(int index) {
    // 獲取key在mHashes數(shù)組上的位置在mArray數(shù)組里對(duì)應(yīng)的value值
    final Object old = mArray[(index << 1) + 1];
    // 當(dāng)前鍵值對(duì)的數(shù)量
    final int osize = mSize;
    final int nsize;
    if (osize <= 1) {
        // 如果當(dāng)前最多只有一對(duì)數(shù)據(jù)自赔，則這對(duì)數(shù)據(jù)移除后，將mHashes和mArray設(shè)置為空
        // 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;
        // 如果當(dāng)前數(shù)組容量大于兩倍基礎(chǔ)容量柳琢，且當(dāng)前使用量不到總?cè)萘康?/3绍妨，則進(jìn)行容量收縮操作，
        // 以便釋放暫時(shí)用不到的內(nèi)存
        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.
            // 如果當(dāng)前使用量大于兩倍基礎(chǔ)容量柬脸，則將數(shù)組的容量縮小為當(dāng)前使用量的1.5倍他去，
            // 否則將數(shù)組容量縮小為兩倍基礎(chǔ)容量
            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;
            // 重新申請(qǐng)兩個(gè)較小的數(shù)組，復(fù)制給mHashes和mArray
            allocArrays(n);

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

            // 如果要?jiǎng)h除的元素在數(shù)組中間（不是第一個(gè)元素）倒堕，則先將數(shù)組中index之前的元素復(fù)制到新數(shù)組中
            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);
            }
            // 如果要?jiǎng)h除的元素在數(shù)組中間（不是最后一個(gè)元素）灾测，則將idnex之后的元素復(fù)制到新數(shù)組中
            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 {
            // 如果不需要收縮容量，且刪除的不是最后一個(gè)元素垦巴，則將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);
            }
            // 將要?jiǎng)h除的位置設(shè)置為null
            mArray[nsize << 1] = null;
            mArray[(nsize << 1) + 1] = null;
        }
    }
    
    // 檢查是否有多線程操作
    if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) {
        throw new ConcurrentModificationException();
    }

    // 重新設(shè)置尺寸并返回刪除的值
    mSize = nsize;
    return (V)old;
}

最后再來(lái)看看釋放數(shù)組和申請(qǐng)數(shù)組的操作：

// 釋放數(shù)組
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    // 如果要釋放的數(shù)組長(zhǎng)度正好是兩倍基礎(chǔ)容量大小則進(jìn)行緩存操作
    if (hashes.length == (BASE_SIZE*2)) {
        // 因?yàn)榫彺嬖陟o態(tài)變量中的媳搪，所以這里需要加鎖做線程同步
        synchronized (ArrayMap.class) {
            // 如果還沒(méi)有達(dá)到最大的緩存容量則進(jìn)行緩存铭段，否則就放棄不緩存
            if (mTwiceBaseCacheSize < CACHE_SIZE) {
                // 緩存的時(shí)候?qū)rray作為一個(gè)節(jié)點(diǎn)，array[0]用來(lái)指向以前的緩存節(jié)點(diǎn)秦爆，array[1]用來(lái)存放hashes數(shù)組
                array[0] = mTwiceBaseCache;
                array[1] = hashes;
                // 將array[2]開(kāi)始到最后的位置里的元素清空
                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");
            }
        }
    } 
    // 對(duì)一倍基礎(chǔ)容量的數(shù)組進(jìn)行緩存序愚，邏輯和上面的一樣
    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");
            }
        }
    }
}

// 申請(qǐng)數(shù)組
private void allocArrays(final int size) {
    if (mHashes == EMPTY_IMMUTABLE_INTS) {
        throw new UnsupportedOperationException("ArrayMap is immutable");
    }
 
    // 如果申請(qǐng)的是兩倍基礎(chǔ)容量大小的數(shù)組，則檢查是否有緩存數(shù)組可用
    if (size == (BASE_SIZE*2)) {
        // 因?yàn)榫彺鏁r(shí)靜態(tài)變量等限，所以需要加鎖進(jìn)行線程同步
        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;
            }
        }
    } 
    // 如果申請(qǐng)的是基礎(chǔ)容量大小的數(shù)組爸吮，則檢查是否有緩存數(shù)組可用
    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];
}

可見(jiàn)，ArrayMap對(duì)數(shù)組進(jìn)行了動(dòng)態(tài)調(diào)整望门，需要擴(kuò)容的時(shí)候進(jìn)行擴(kuò)容形娇，不需要的時(shí)候進(jìn)行了縮容操作來(lái)及時(shí)釋放暫時(shí)不用的內(nèi)存。并且對(duì)基礎(chǔ)容量數(shù)組進(jìn)行了緩存筹误，減少了內(nèi)存申請(qǐng)的次數(shù)埂软。從而在內(nèi)存的使用方面帶來(lái)了客觀的提升。

但是我們發(fā)現(xiàn)纫事，上面查找key的時(shí)候使用的是二分查找，這就導(dǎo)致ArrayMap比HashMap的速度要慢所灸，而且刪除數(shù)據(jù)的時(shí)候也可能會(huì)對(duì)數(shù)組進(jìn)行重新調(diào)整丽惶，所以在使用大量數(shù)據(jù)的時(shí)候ArrayMap的效率比HashMap要低50%。因此官方建議是在小數(shù)據(jù)量（1000以內(nèi)）的情況下使用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提供的一個(gè)特殊的HashMap。相對(duì)HashMap侠驯，它在內(nèi)存使用方面做了一些優(yōu)化抡秆，主要體現(xiàn)為：

1. 其內(nèi)部使用了矩陣壓縮算法來(lái)優(yōu)化了稀疏數(shù)組；
2. 它的key是int類型吟策，避免了HashMap的自動(dòng)裝箱（將int轉(zhuǎn)換成Integer）儒士；
3. 避免了使用一個(gè)額外的實(shí)體對(duì)象來(lái)存儲(chǔ)鍵值對(duì)。

和上面的ArrayMap一樣檩坚，其內(nèi)部也是使用兩個(gè)數(shù)組來(lái)進(jìn)行存儲(chǔ)的着撩。其定義如下：

public class SparseArray<E> implements Cloneable {
    // 存放key的數(shù)組
    private int[] mKeys;
    // 存放value的數(shù)組
    private Object[] mValues;
    // 鍵值對(duì)數(shù)量
    private int mSize;

    private boolean mGarbage = false;
}

我們來(lái)看看put操作：

public void put(int key, E value) {
    // 通過(guò)二分查找，在mKeys數(shù)組中查找key的位置
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        // 如果存在key則直接將value放到mValues數(shù)組對(duì)應(yīng)的位置
        // 此時(shí)該位置的value可能是當(dāng)初插入的值匾委，也可能是被刪除后標(biāo)記成的DELETED對(duì)象（見(jiàn)后面的delete方法）拖叙，
        // 但這并不重要，直接用新的值覆蓋即可
        mValues[i] = value;
    } else {
        i = ~i;

        // 如果該位置value的值是一個(gè)內(nèi)部固定的對(duì)象DELETED赂乐，
        // 則說(shuō)明該位置的鍵值對(duì)被移除了薯鳍，那么將新的鍵值對(duì)直接存放在該位置
        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        // 當(dāng)刪除了數(shù)組中間的鍵值對(duì)，會(huì)將mGarbage變量設(shè)置true（刪除的鍵值對(duì)會(huì)標(biāo)記為DELETED）挨措，
        // 如果此時(shí)數(shù)組滿了挖滤，則需要回收這些被標(biāo)記為DELETED的位置崩溪，騰出來(lái)給新的鍵值對(duì)使用
        if (mGarbage && mSize >= mKeys.length) {
            // gc方法的作用就是將數(shù)組后面的元素往前移動(dòng)，覆蓋那些被標(biāo)記為DELETED的位置
            gc();

            // 數(shù)組被調(diào)整后壶辜，重新執(zhí)行二分查找悯舟，來(lái)查找key的位置
            // 注意，這里不是為了真正找到有相同的key（前面已經(jīng)找過(guò)了砸民，執(zhí)行到這里說(shuō)明數(shù)組中是不存在相同key的）抵怎，
            // 而是為了找到新的鍵值對(duì)的插入點(diǎn)
            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        // 將新的鍵值對(duì)插入到數(shù)組中
        // 這里的GrowingArrayUtils.insert方法的步驟如下：
        // 1，檢查指定數(shù)組的容量是否足夠岭参，不夠則會(huì)進(jìn)行擴(kuò)容
        // 2反惕，如果插入的位置在數(shù)組中間，則會(huì)將插入點(diǎn)及之后的元素后移一位
        // 3演侯，在指定的插入點(diǎn)插入新的元素
        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

再來(lái)看看remove操作：

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

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

    // 如果找到了則將要?jiǎng)h除的位置的value設(shè)置為內(nèi)部的一個(gè)固定對(duì)象DELETED姿染，標(biāo)記為已刪除
    if (i >= 0) {
        if (mValues[i] != DELETED) {
            mValues[i] = DELETED;
            // 這里不移動(dòng)數(shù)組中的元素，而是將mGarbage設(shè)置為true秒际，然后等數(shù)組容量不足時(shí)再一起移動(dòng)
            mGarbage = true;
        }
    }
}

再來(lái)看看上面的gc方法具體是怎么實(shí)現(xiàn)的：

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

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

   // 很簡(jiǎn)單悬赏，就是遍歷整個(gè)數(shù)組，將值是DELETED后面的元素前移娄徊，覆蓋掉DELETED所在位置
    for (int i = 0; i < n; i++) {
        Object val = values[i];

        if (val != DELETED) {
           // o表示移動(dòng)過(guò)程中闽颇，移動(dòng)后的最后一個(gè)有效元素（值不是DELETED）的下下一個(gè)位置
           // 如果o不等于i，則將i位置的元素移動(dòng)到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

同樣寄锐，因?yàn)镾parseArray采用了二分查找兵多，所以在大數(shù)據(jù)下，速度沒(méi)有HashMap快橄仆。官方也是建議在數(shù)據(jù)不超過(guò)1000條的情況下才用來(lái)代替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%.

總結(jié)

備注：上面ArrayMap和SparseArray的慢是在大量數(shù)據(jù)的情況下怠褐，當(dāng)數(shù)據(jù)少于1000的時(shí)候速度和HashMap是差不多的。

三您宪、SparseIntArray

added in API level 1
SparseIntArray是SparseArray的一個(gè)特例惫搏，它的鍵和值都是int類型。相比SparseArray蚕涤，它的值也避免了自動(dòng)裝箱筐赔。所以性能比SparseArray高些。

四揖铜、SparseBooleanArray

added in API level 1
SparseBooleanArray也是SparseArray的一個(gè)特例茴丰，它的鍵是int類型的，值是boolean類型。相比SparseArray贿肩，它的值也避免了自動(dòng)裝箱峦椰。所以性能比SparseArray高些。

五汰规、SparseLongArray

added in API level 18
SparseLongArray也是SparseArray的一個(gè)特例汤功，它的鍵是int類型的，值是long類型溜哮。相比SparseArray滔金，它的值也避免了自動(dòng)裝箱。所以性能比SparseArray高些茂嗓。

六餐茵、LongSparseArray

added in API level 16 or in android.support.v4
LongSparseArray和SparseArray類似，只是它的鍵是long類型的述吸。其他和SparseArray無(wú)差別忿族。

總結(jié)

java為我們提供了四種主要類用來(lái)存儲(chǔ)鍵值對(duì)。其中：

• HashMap高效的實(shí)現(xiàn)了存儲(chǔ)鍵值對(duì)的基本功能蝌矛；
• LinkedHashMap在HashMap的基礎(chǔ)上增加了鍵值對(duì)的有序性（插入順序和訪問(wèn)順序）道批；
• TreeMap在HashMap的基礎(chǔ)上增加了鍵值對(duì)的自定義順序；
• Hashtable在HashMap的基礎(chǔ)上增加了線程同步入撒。

另外隆豹，java還提供了三種HashMap的特殊類：

• EnumMap的key被限定為只能是enum；
• IdentityHashMap的key必須絕對(duì)相等（必須是同一個(gè)對(duì)象）衅金；
• WeakHashMap實(shí)現(xiàn)了多key-value的弱引用。

android提供了兩種對(duì)HashMap的內(nèi)存使用做了優(yōu)化的類：ArrayMap和SparseArray簿煌。ArrayMap和HashMap一樣氮唯，key和value都是Object。SparseArray的key被限定為int姨伟。他們都是以犧牲性能為代價(jià)來(lái)優(yōu)化了內(nèi)存的使用惩琉。官方建議是當(dāng)數(shù)據(jù)不超過(guò)1000條的時(shí)候使用他們來(lái)代替HashMap（這種情況下性能差不多）。

同樣夺荒，針對(duì)SparseArray瞒渠，android也提供了幾種特殊類：

• SparseIntArray的鍵是int類型， 值也是int類型技扼；
• SparseBooleanArray的鍵是int類型伍玖，值是boolean類型；
• SparseLongArray的鍵是int類型剿吻，值是long類型窍箍；
• LongSparseArray的鍵是long類型，值是Object類型。

關(guān)于Map接口的數(shù)據(jù)結(jié)構(gòu)類基本就這些了椰棘，還是那句話：只要大家明白了它們各自的實(shí)現(xiàn)原理也就知道了它們各自的區(qū)別和適合的使用場(chǎng)景纺棺。