Android Map資料結構全面總結分析

2022-12-07 14:01:33

前言

上一篇講了Collection、Queue和Deque、List或Set，沒看的朋友可以去簡單看看，這一篇主要講和Map相關的資料結構。

Map

上篇有介紹過，Map是另一種資料結構，它獨立於Collection，它的是一個介面，它的抽象實現是AbstractMap，它內部是會通過Set來實現迭代器

Set<Map.Entry<K, V>> entrySet();

是和Set有關聯的，思想上主要以key-value的形式儲存資料，但是具體的實現會交給子類去實現。

ArrayMap

ArrayMap和ArraySet一樣，內部用兩個陣列實現int[] mHashes好Object[] mArray

不同於ArraySet的是，ArraySet的mHashes是用Object的hash，而ArrayMap的mHashes是用key的hash。

TreeMap

上一篇講的TreeSet內部也是用的TreeMap。TreeMap是一個紅黑樹的資料結構，如果不瞭解紅黑樹的話，直接看會比較懵逼，不過沒關係，我們可以往上一級去看，紅黑樹其實是一種二元搜尋樹，那什麼是二元搜尋樹呢？簡單來說，二元搜尋樹是任何一個節點的左子樹都小於當前節點，任何一個節點的右子樹都大於當前節點。

這樣講就更容易能理解了吧。那這棵樹的順序就是中序遍歷的順序，它也符合二分查詢的條件。如果還是不理解的話可以先去了解一下二元搜尋樹，這比紅黑樹更容易理解。二元搜尋樹在插入節點之後，要實現平衡，通常可以通過左旋和右旋去實現（這個演演算法這裡也不詳細說，感興趣的可以自己去了解，不感興趣的可以先記住這個概念）。而紅黑樹要達到平衡，通過左旋和右旋之外還有可能需要實現變色，這個相對於二元搜尋樹來說會相對更加複雜。但是沒關係，先記住這個概念。它的特點主要是查詢通過二分查詢，插入會通過左旋右旋和變色來維持平衡。

這裡也可以擴充套件一下紅黑樹的特徵，但是不會詳細的介紹

1. 結點是紅色或黑色

2. 根結點是黑色

3. 所有葉子都是黑色

4. 每個紅色結點的兩個子結點都是黑色

5. 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點

其內部的TreeMapEntry是它的結構體

static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    TreeMapEntry<K,V> left;
    TreeMapEntry<K,V> right;
    TreeMapEntry<K,V> parent;
    boolean color = BLACK;
    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    TreeMapEntry(K key, V value, TreeMapEntry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    /**
     * Returns the key.
     *
     * @return the key
     */
    public K getKey() {
        return key;
    }
    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    public V getValue() {
        return value;
    }
    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }
    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }
    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash;
    }
    public String toString() {
        return key + "=" + value;
    }
}

能看到除了key-value之外，還有left,right,parent表示左子節點，右子節點和父節點，還有一個boolean型別的color表示這個節點是紅色的還是黑色的。也可以簡單看看它的put方法

public V put(K key, V value) {
    TreeMapEntry<K,V> t = root;
    ......
    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);
    }
    ......
}

Comparator能實現自己的排序規則，一般都是預設的規則。通過compare去找到合適的位置插入紅黑樹，這段程式碼還是沒什麼難的地方，也不詳細去講了。

HashMap

這個相對而言就比較重要，因為用的比較多，所以可能會講的相對更詳細。可以先看看它的內部的資料結構，內部是一個節點陣列Node<K,V>[] table，每個節點又是一個連結串列（或紅黑樹）的結構。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

節點主要有3個重要的引數，key，value和key的hash。

那我們就先需要搞懂它的一個邏輯，它會想用Key去生成hash，再用hash去計算出這個節點在陣列中的下標。所以先看計算key的hash的方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

拿到key的hashcode，然後讓這個hashcode的高16位元和低16位元做互斥或運算。這個操作是為了什麼呢？這個是為了降低雜湊衝突的概率，那這裡又引出了什麼是hash衝突？

這裡直接說會比較難去理解，沒關係，我們先往下講如何通過hash去計算陣列的位置，理解完這個步驟之後我們再反回來講雜湊衝突這個事。

在HashMap的put方法中有一段程式碼

......
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
......

這個(n - 1) & hash就是計算陣列下標的方式，通過hash和陣列長度-1做與運算，來得到這個節點應該插入到陣列的哪個位置。那為何要用hash和陣列長度-1做與運算，這個陣列長度-1是什麼東西？這又要涉及到另一個知識點，所以說hashmap中的細節比較多。

首先這個hashmap的長度，必須是2的n次方，比如4,8,16,32。它內次擴容也是x2，這時候我們再去看長度-1，比如長度是16，那16-1是15，它對應的二進位制是1111，假如長度是32，那31的二進位制是11111。看到這裡相信你已經知道長度-1代表什麼了。講到長度，這裡又會涉及一個知識點是為什麼HashMap的預設長度是16，定8不行嗎？定32不行嗎？這個放到最後講。

我們回過來先繼續去說雜湊衝突這事，什麼是雜湊衝突？hash衝突的意思是兩個不同的物件，計算出來的雜湊值相同。放在HashMap中你也可以簡單理解成，兩個不同的key計算出的陣列下標相同。而HashMap中解決雜湊衝突的方法是上面的高16位元和低16位元做互斥或，和用鏈地址法（就是相同的話，節點用連結串列或者紅黑樹表示）

鏈地址法比較容易理解，主要還是為什麼hash的高16位元和低16位元做互斥或能降低雜湊衝突的概率。那是因為平常計算的時候，高16位元是不會參與計算的，我舉個例子，假如兩個不同的key計算出來的hash值，高16位元不同，低16位元相同，陣列長度是16，這時候你這兩個hash與15做與運算，得到的結果相同吧，那不就衝突了？如果我把高16位元和低16位元先做互斥或，這時候會讓高16位元參與到運算中，所以他們計算出的結果就會不同。

此時可能有人會想，那為什麼不把32位元的hash分4段做互斥或，4段8位元做互斥或，這樣不就更充分嗎？這樣確實能更先降低陣列長度是16情況下的雜湊衝突概率，但是你要考慮整形的最大值，當陣列的長度-1達到16位元時，這樣做就會出現問題。

通過Key計算出陣列的位置，如果這個位置沒節點，就把這個節點放入，如果有節點，就遍歷這個節點的連結串列，所以我們看put方法具體的操作

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 判斷陣列中沒結點的話建立結點然後新增進取    
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 判斷結點的hash和key是相等的話直接改值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
        // 判斷是紅黑樹的情況（後面會說）
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        // 判斷是連結串列的情況，迴圈遍歷連結串列找到hash和key相同的結點
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                // 沒找到的情況下建立一個新的結點放到連結串列末尾
                    p.next = newNode(hash, key, value, null);
                    // 判斷是否需要將連結串列轉成紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到相同的key，直接替換value然後結束流程
        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;
}

從中能看出put內部的主要操作是判斷對應陣列的位置是否有結點，沒有的話直接放進去，有的話遍歷這個結點的連結串列或者紅黑樹，找到hash和key相同的結點替換掉，如果沒有，則新建結點放到尾部，如果連結串列的長度到達8,將連結串列轉成紅黑樹。最後再判斷是否要擴容。

這段程式碼還是比較容易理解的，先講講最後的afterNodeInsertion，勾點函數，雖然在這裡面沒有任何程式碼，但從設計的角度去看，這是一個比較好的設計，可以增強擴充套件性。

比較重要的操作就是轉紅黑樹的操作，可以看看它的常數定義

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

可以看到這裡小於6個的時候轉回連結串列，轉的操作在resize的split方法。說到resize，我們也可以看看，這個方法也算重點

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    ......
    int newCap, newThr = 0;
    if (oldCap > 0) {
        ......
        // 重點是newCap = oldCap << 1
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            ......
    }
    ......
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                // 單結點情況下的擴容
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                // 紅黑樹情況下的擴容
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                // 連結串列情況下的擴容
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

我這裡遮蔽了一些程式碼，只保留重點的程式碼，能簡單的看出擴容的操作就是建立另一個陣列，然後給新陣列賦值後覆蓋舊陣列。如果看過上一篇文章的ArrayList，那就能很容易知道，短時間頻繁的擴容會導致記憶體抖動，所以為什麼初始長度不定2,不定4,不定8 。然後看最主要的擴容操作newCap = oldCap << 1，新的長度是舊的長度左移動一位，其實就是x2，所以上面有說hashmap的長度都是2的n次方。

然後看看3種不同情況的擴容，先看單結點的情況，如果陣列中對應的位置只有一個結點，那就重新計算它的下標，然後換個位置。

再先看如果是連結串列的情況。它會把連結串列拆分成兩條連結串列，分別放到陣列的newTab[j]和newTab[j + oldCap] ，這個大概的思路是這樣，詳細的話多看幾次程式碼也能很容易理解。最後再來看紅黑樹的情況。呼叫split方法

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

這裡只需要簡單理解，TreeNode這個資料結構是繼承Node的，for迴圈中的操作其實就和連結串列中的操作一樣，分成low和height兩部分，然後判斷小於UNTREEIFY_THRESHOLD也就是6的情況下，轉成Node結點，也就是樹轉回連結串列。

總結

這次主要講了ArrayMap、TreeMap和HashMap3個資料結構，因為這3個用得比較多，但並不是Map中只有這3個，比如Map中還有IdentityHashMap、WeakHashMap這些，但是比較常用的就是這3種，其中最重要的是HashMap。

HashMap中比較重要的是它的一些設計的思想，比如如何去解決和降低雜湊衝突，為什麼預設的大小是16，其次要了解它的一個工作原理，我這裡主要是以put方法來舉例，當中就涉及到像鏈地址法，連結串列轉紅黑樹，擴容等操作。和LinkedList一樣，我也十分建議沒看過HashMap原始碼的人能去看看，體驗一下它內部的一些程式碼設計思想和細節的處理。

通過這兩篇文章，平常比較常用的資料結構基本都講完了，下一篇就開始講講和執行緒安全相關的資料結構。

以上就是Android Map資料結構全面總結分析的詳細內容，更多關於Android Map資料結構的資料請關注it145.com其它相關文章！

Android Map資料結構全面總結分析

目錄

前言

Map

ArrayMap

TreeMap

HashMap

總結

熱門文章