源碼|jdk源碼之HashMap分析(一)

AndroidTraveler 發(fā)布于2019-08-16 12:42 / 1360人閱讀

摘要：看屬性有一個(gè)，所以是紅黑樹的節(jié)點(diǎn)。會(huì)在鏈表過長(zhǎng)的時(shí)候，將其重構(gòu)成紅黑樹，這個(gè)看后面的代碼。如果是紅黑樹的話，調(diào)用紅黑樹的查找函數(shù)來最終找到這個(gè)節(jié)點(diǎn)。該位置為平衡樹。但是這導(dǎo)致鏈表增長(zhǎng)，需要觸發(fā)鏈表重構(gòu)成平衡樹的判斷邏輯。

hash表是應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)，是對(duì)鍵值對(duì)數(shù)據(jù)結(jié)構(gòu)的一種重要實(shí)現(xiàn)。
它能夠?qū)㈥P(guān)鍵字key映射到內(nèi)存中的某一位置，查詢和插入都能達(dá)到平均時(shí)間復(fù)雜度為O(1)的性能。
HashMap是java對(duì)hash表的實(shí)現(xiàn)，它是非線程安全的，也即不會(huì)考慮并發(fā)的場(chǎng)景。

HashMap實(shí)現(xiàn)思路

hash表是常見的數(shù)據(jù)結(jié)構(gòu)，大學(xué)都學(xué)過，以前也曾用C語言實(shí)現(xiàn)過一個(gè)：
https://github.com/frapples/c...

偷點(diǎn)懶，這里就大概總結(jié)一下了，畢竟這篇博文jdk代碼才是重點(diǎn)。

在使用者的角度來看，HashMap能夠存儲(chǔ)給定的鍵值對(duì)，并且對(duì)于給定key的查詢和插入都達(dá)到平均時(shí)間復(fù)雜度為O(1)。

實(shí)現(xiàn)hash表的關(guān)鍵在于：

對(duì)于給定的key，如何將其對(duì)應(yīng)到內(nèi)存中的一個(gè)對(duì)應(yīng)位置。這通過hash算法做到。

通過一個(gè)數(shù)組保存數(shù)據(jù)，通過hash算法hash(K) % N來將關(guān)鍵字key映射數(shù)組對(duì)應(yīng)位置上。

hash算法存在hash沖突，也即多個(gè)不同的K被映射到數(shù)組的同一個(gè)位置上。如何解決hash沖突？有三種方法。

分離鏈表法。即用鏈表來保存沖突的K。

開放定址法。當(dāng)位置被占用時(shí)，通過一定的算法來試選其它位置。hash(i) = (hash(key) + d(i)) % N，i代表第i次試選。常用的有平方探測(cè)法，d(i) = i^2。

再散列。如果沖突，就再用hash函數(shù)再嵌套算一次，直到?jīng)]有沖突。

HashMap代碼分析 Node節(jié)點(diǎn)

先來看Node節(jié)點(diǎn)。這表明HashMap采用的是分離鏈表的方法實(shí)現(xiàn)。
Node為鏈表節(jié)點(diǎn)，其中存儲(chǔ)了鍵值對(duì)，key和value。

不過實(shí)際上，HashMap的真正思路更復(fù)雜，會(huì)用到平衡樹，這個(gè)后面再說。

    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        /* ... */
    }

還能發(fā)現(xiàn)，這是一個(gè)單鏈表。對(duì)于HashMap來說，單鏈表就已經(jīng)足夠了，雙向鏈表反而多一個(gè)浪費(fèi)內(nèi)存的字段。

除此之外，還能夠注意到節(jié)點(diǎn)額外保存了hash字段，為key的hash值。
仔細(xì)一想不難明白，HashMap能夠存儲(chǔ)任意對(duì)象，對(duì)象的hash值是由hashCode方法得到，這個(gè)方法由所屬對(duì)象自己定義，里面可能有費(fèi)時(shí)的操作。

而hash值在Hash表內(nèi)部實(shí)現(xiàn)會(huì)多次用到，因此這里將它保存起來，是一種優(yōu)化的手段。

TreeNode節(jié)點(diǎn)

這個(gè)TreeNode節(jié)點(diǎn)，實(shí)際上是平衡樹的節(jié)點(diǎn)。
看屬性有一個(gè)red，所以是紅黑樹的節(jié)點(diǎn)。

    static final class TreeNode extends LinkedHashMap.Entry {
        TreeNode parent;  // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node next) {
            super(hash, key, val, next);
        }
        /* ... */
    }

除此之外，還能發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)有prev屬性，此外，它還在父類那里繼承了一個(gè)next屬性。
這兩個(gè)屬性是干嘛的？通過后面代碼可以發(fā)現(xiàn)，這個(gè)TreeNode不僅用來組織紅黑樹，還用來組織雙向鏈表。。。

HashMap會(huì)在鏈表過長(zhǎng)的時(shí)候，將其重構(gòu)成紅黑樹，這個(gè)看后面的代碼。

屬性字段

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node[] table;
    transient Set> entrySet;
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;

最重要的是table、size、loadFactor這三個(gè)字段：

table可以看出是個(gè)節(jié)點(diǎn)數(shù)組，也即hash表中用于映射key的數(shù)組。由于鏈表是遞歸數(shù)據(jù)結(jié)構(gòu)，這里數(shù)組保存的是鏈表的頭節(jié)點(diǎn)。

size，hash表中元素個(gè)數(shù)。

loadFactor，裝填因子，控制HashMap擴(kuò)容的時(shí)機(jī)。

至于entrySet字段，實(shí)際上是個(gè)緩存，給entrySet方法用的。
而modCount字段的意義和LinkedList一樣，前面已經(jīng)分析過了。

最后，threshold這個(gè)字段，含義是不確定的，像女孩子的臉一樣多變。。。
坦誠的說這樣做很不好，可能java為了優(yōu)化時(shí)省點(diǎn)內(nèi)存吧，看后面的代碼就知道了，這里總結(jié)下：

如果table還沒有被分配，threshold為初始的空間大小。如果是0，則是默認(rèn)大小，DEFAULT_INITIAL_CAPACITY。

如果table已經(jīng)分配了，這個(gè)值為擴(kuò)容閾值，也就是table.length * loadFactor。

構(gòu)造函數(shù)

    /**
     * Constructs an empty HashMap with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

第一個(gè)構(gòu)造函數(shù)是重點(diǎn)，它接收兩個(gè)參數(shù)initialCapacity代表初始的table也即hash桶數(shù)組的大小，loadFactor可以自定義擴(kuò)容閾值。

  this.threshold = tableSizeFor(initialCapacity);

這里也用到了類似前面ArrayList的“延遲分配”的思路，一開始table是null，只有在第一次插入數(shù)據(jù)時(shí)才會(huì)真正分配空間。
這樣，由于實(shí)際場(chǎng)景中會(huì)出現(xiàn)大量空表，而且很可能一直都不添加元素，這樣“延遲分配”的優(yōu)化技巧能夠節(jié)約內(nèi)存空間。
這里就體現(xiàn)出threshold的含義了，hash桶數(shù)組的空間未分配時(shí)它保存的是table初始的大小。

tableSizeFor函數(shù)是將給定的數(shù)對(duì)齊到2的冪。這個(gè)函數(shù)用位運(yùn)算優(yōu)化過，我沒怎么研究具體的思路。。。
但是由此可以知道，hash桶數(shù)組的初始大小一定是2的冪，實(shí)際上，hash桶數(shù)組大小總是為2的冪。

get函數(shù) hash二次運(yùn)算

先從get函數(shù)看起。

    public V get(Object key) {
        Node e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

我們發(fā)現(xiàn)，調(diào)用getNode時(shí)：

        return (e = getNode(hash(key), key)) == null ? null : e.value;

其中調(diào)用了hash這個(gè)靜態(tài)函數(shù)：

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

也就是說，用于HashMap的hash值，還需要經(jīng)過這個(gè)函數(shù)的二次計(jì)算。那這個(gè)二次計(jì)算的目的是什么呢？
通過閱讀注釋：

Computes key.hashCode() and spreads (XORs) higher bits of hash

to lower. Because the table uses power-of-two masking, sets of

hashes that vary only in bits above the current mask will

always collide. (Among known examples are sets of Float keys

holding consecutive whole numbers in small tables.) So we

apply a transform that spreads the impact of higher bits

downward. There is a tradeoff between speed, utility, and

quality of bit-spreading. Because many common sets of hashes

are already reasonably distributed (so don"t benefit from

spreading), and because we use trees to handle large sets of

collisions in bins, we just XOR some shifted bits in the

cheapest possible way to reduce systematic lossage, as well as

to incorporate impact of the highest bits that would otherwise

never be used in index calculations because of table bounds.

嗯。。。大概意思是說，由于hash桶數(shù)組的大小是2的冪次方，對(duì)其取余只有低位會(huì)被使用。這個(gè)特點(diǎn)用二進(jìn)制寫法研究一下就發(fā)現(xiàn)了：如1110 1100 % 0010 0000 為 0000 1100，高位直接被忽略掉了。

也即高位的信息沒有被利用上，會(huì)加大hash沖突的概率。于是，一種思路是把高位的信息混合到低位上去，提高區(qū)分度。就是上面這個(gè)hash函數(shù)了。

getNode函數(shù)

    final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

get函數(shù)調(diào)用了getNode，它接受給定的key，定位出對(duì)應(yīng)的節(jié)點(diǎn)。這里檢查了table為null的情況。此外first = tab[(n - 1) & hash]實(shí)際上就是first = tab[hash % n]的優(yōu)化，這個(gè)細(xì)節(jié)太多，等會(huì)再分析。

代碼雖然有點(diǎn)多，但是大部分都是一些特別情況的檢查。首先是根據(jù)key的hash值來計(jì)算這個(gè)key放在了hash桶數(shù)組的哪個(gè)位置上。找到后，分三種情況處理：

這個(gè)位置上只有一個(gè)元素。

這個(gè)位置上是一個(gè)鏈表。

這個(gè)位置上是一棵紅黑樹。

三種情況三種不同的處理方案。比較奇怪的是為什么1不和2合并。。。

如果是紅黑樹的話，調(diào)用紅黑樹的查找函數(shù)來最終找到這個(gè)節(jié)點(diǎn)。
如果是鏈表的話，則遍歷鏈表找到這個(gè)節(jié)點(diǎn)。值得關(guān)注的是對(duì)key的比較：

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

類似于hashCode方法，equals方法也是所屬對(duì)象自定義的，比較可能比較耗時(shí)。
所以這里先比較Node節(jié)點(diǎn)保存的hash值和引用，這樣盡量減少調(diào)用equals比較的時(shí)機(jī)。

模運(yùn)算的優(yōu)化

回到剛才的位運(yùn)算：

first = tab[(n - 1) & hash]

這個(gè)位運(yùn)算，實(shí)際上是對(duì)取余運(yùn)算的優(yōu)化。由于hash桶數(shù)組的大小一定是2的冪次方，因此能夠這樣優(yōu)化。

思路是這樣的，b_i是b二進(jìn)制第i位的值：

b % 2ⁱ = (2^Nb_N + 2^N-1 b_N-1+ ... + 2ⁱb_i + ... 2⁰b₀) % 2ⁱ

設(shè)x >= i，則一定有2^xb_x % 2ⁱ = 0

所以，上面的式子展開后就是：
b % 2ⁱ = 2^i-1b_i-1 + 2^i-2b_i-2 + ... 2⁰b₀

反映到二進(jìn)制上來說，以8位二進(jìn)制舉個(gè)例子：

顯然2的冪次方N的二進(jìn)制位是只有一個(gè)1的。8的二進(jìn)制為00001000，1在第3位。

任何一個(gè)數(shù)B余這個(gè)數(shù)N，反映二進(jìn)制上，就是高于等于第3位的置0，低于的保留。如10111010 % 00001000 = 00000010

這樣，就不難理解上面的(n - 1) & hash了。以上面那個(gè)例子，
00001000 - 1 = 00000111，這樣減一之后，需要保留的對(duì)應(yīng)位為全是1，需要置0的對(duì)應(yīng)位全都是0。把它與B作與運(yùn)算，就能得到結(jié)果。

put函數(shù)

沒想到寫這個(gè)比想象中的費(fèi)時(shí)間。。。還有很多其他事情要做呢
這個(gè)put函數(shù)太長(zhǎng)了，容我偷個(gè)懶直接貼代碼和我自己的注釋吧

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

    // onlyIfAbsent含義是如果那個(gè)位置已經(jīng)有值了，是否替換
    // evict什么鬼？table處于創(chuàng)造模式？先不管
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // table為null或者沒有值的時(shí)候reisze()，因此這個(gè)函數(shù)還負(fù)責(zé)初始分配
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 定位hash桶。如果是空鏈表的話（即null），直接新節(jié)點(diǎn)插入：
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                // 如果hash桶掛的是二叉樹，調(diào)用TreeNode的putTreeVal方法完成插入
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 如果掛的是鏈表，插入實(shí)現(xiàn)
                // 遍歷鏈表，順便binCount變量統(tǒng)計(jì)長(zhǎng)度
                for (int binCount = 0; ; ++binCount) {
                    // 情況一：到尾巴了，就插入一條
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 插入會(huì)導(dǎo)致鏈表變長(zhǎng)
                        // 可以發(fā)現(xiàn)，TREEIFY_THRESHOLD是個(gè)閾值，超過了就調(diào)用treeifyBin把鏈表換成二叉樹
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 情況二：找到已經(jīng)存在一個(gè)節(jié)點(diǎn)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 情況二的處理
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果hash桶數(shù)組的大小超過了閾值threshold，就resize()，可見resize負(fù)責(zé)擴(kuò)容
        if (++size > threshold)
            resize();
        // evice的含義得看afterNodeInsertion函數(shù)才能知道
        afterNodeInsertion(evict);
        return null;
    }

思路大概是這樣的邏輯：

判斷table是否分配，如果沒有就先分配空間，和前面提到的“延時(shí)分配”對(duì)應(yīng)起來。

同樣，根據(jù)hash值定位hash桶數(shù)組的位置。然后：

該位置為null。直接創(chuàng)建一個(gè)節(jié)點(diǎn)插入。

該位置為平衡樹。調(diào)用TreeNode的一個(gè)方法完成插入，具體邏輯在這個(gè)方法里。

該位置為鏈表。遍歷鏈表，進(jìn)行插入。會(huì)出現(xiàn)兩種情況：

遍歷到鏈表尾，說明這個(gè)key不存在，應(yīng)該直接在鏈表尾插入。但是這導(dǎo)致鏈表增長(zhǎng)，需要觸發(fā)鏈表重構(gòu)成平衡樹的判斷邏輯。

找到一個(gè)key相同的節(jié)點(diǎn)，多帶帶拎出來處理，得看onlyIfAbsent的參數(shù)。

完畢之后，這個(gè)時(shí)候hash表中可能多了一個(gè)元素。也只有多了一個(gè)元素的情況下控制流才能走到這。這時(shí)維護(hù)size字段，并且觸發(fā)擴(kuò)容的判斷邏輯。

在這里我有幾點(diǎn)疑惑：

為什么null的情況、一個(gè)節(jié)點(diǎn)的情況、單鏈表的情況不合并在一起處理？因?yàn)樾阅埽?/p>

為什么采用尾插法不用頭插法？頭插法根據(jù)局部性原理豈不是更好嗎？

在遍歷鏈表時(shí)會(huì)同時(shí)統(tǒng)計(jì)鏈表長(zhǎng)度，然后鏈表如果被插入，會(huì)觸發(fā)樹化邏輯：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

TREEIFY_THRESHOLD的值是8，也就是說，插入后的鏈表長(zhǎng)度如果超過了8，則會(huì)將這條鏈表重構(gòu)為紅黑樹，以提高定位性能。

在插入后，如果hash表中元素個(gè)數(shù)超過閾值，則觸發(fā)擴(kuò)容邏輯：

    if (++size > threshold)
        resize();

記得前面說過，threshold在table已經(jīng)分配的時(shí)候，代表是擴(kuò)容閾值，即table.length * loadFactor。

最后

考慮到篇幅夠長(zhǎng)了，還是拆分成兩篇比較好，剩下的留到下一篇博文再寫吧。

云服務(wù)器 GPU云服務(wù)器源碼中文說明之第一源碼網(wǎng) 源碼分析 webrtc源碼分析

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/71574.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

AndroidTraveler

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

python2.7

閱讀 1425·2023-04-25 23:42
nacos啟動(dòng)遇到的錯(cuò)誤，日志報(bào)錯(cuò)because dumpservice bean construc

閱讀 3134·2021-11-19 09:40
PacificRack舊套餐下架,新套餐首付5折首月2.5美元起

閱讀 3620·2021-10-19 11:44
[1054]Airtest的探索使用

閱讀 3828·2021-10-14 09:42
商城系統(tǒng)的可行性與需求

閱讀 2032·2021-10-13 09:39
如何部署在云主機(jī)-云主機(jī)怎么使用？

閱讀 3957·2021-09-22 15:43
css不常見屬性之pointer-events

閱讀 744·2019-08-30 15:54
動(dòng)手寫 js 沙箱

閱讀 1528·2019-08-26 13:32

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

源碼|jdk源碼之HashMap分析(一)

相關(guān)文章

java源碼

**源碼|jdk源碼之LinkedHashMap分析**

**源碼|jdk源碼之HashMap分析(二)**

HashMap源碼分析(一):JDK源碼分析系列

HashMap 源碼詳細(xì)分析(JDK1.8)

發(fā)表評(píng)論

0條評(píng)論

AndroidTraveler

男|高級(jí)講師

TA的文章

python2.7

nacos啟動(dòng)遇到的錯(cuò)誤，日志報(bào)錯(cuò)because dumpservice bean construc

PacificRack舊套餐下架,新套餐首付5折首月2.5美元起

[1054]Airtest的探索使用

商城系統(tǒng)的可行性與需求

如何部署在云主機(jī)-云主機(jī)怎么使用？

css不常見屬性之pointer-events

動(dòng)手寫 js 沙箱

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！

源碼|jdk源碼之HashMap分析(一)

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購！