HashMap源碼分析_JDK1.8版本

0xE7A38A 發(fā)布于2019-08-14 18:03 / 477人閱讀

摘要：源碼分析版本聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處聲明結(jié)構(gòu)圖示基本數(shù)據(jù)結(jié)構(gòu)本質(zhì)是一個(gè)散列表，存儲(chǔ)元素為鍵值對(duì)繼承，實(shí)現(xiàn)了接口的是線程不安全的，它的都可以為默認(rèn)裝填因子，如果當(dāng)前鍵值對(duì)個(gè)數(shù)最大容量裝填因子，進(jìn)行操作新加，鏈表最大長(zhǎng)度，當(dāng)桶中

HashMap源碼分析_JDK1.8版本 聲明

文章均為本人技術(shù)筆記，轉(zhuǎn)載請(qǐng)注明出處
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

HashMap聲明

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

HashMap結(jié)構(gòu)圖示

HashMap基本數(shù)據(jù)結(jié)構(gòu)

HashMap本質(zhì)是一個(gè)散列表，存儲(chǔ)元素為鍵值對(duì)；

HashMap繼承AbstractMap，實(shí)現(xiàn)了Map、Cloneable、java.io.Serializable接口；

HashMap的是線程不安全的，它的key、value都可以為null；

final int loadFacotr

static final float DEFAULT_LOAD_FACTOR: 默認(rèn)裝填因子0.75，如果當(dāng)前鍵值對(duì)個(gè)數(shù) >= HashMap最大容量*裝填因子，進(jìn)行rehash操作；

int threshold

static final int TREEIFY_THRESHOLD： JDK1.8 新加，Entry鏈表最大長(zhǎng)度，當(dāng)桶中節(jié)點(diǎn)數(shù)目大于該長(zhǎng)度時(shí)，將鏈表轉(zhuǎn)成紅黑樹(shù)存儲(chǔ)；

static final int UNTREEIFY_THRESHOLD：JDK1.8 新加，當(dāng)桶中節(jié)點(diǎn)數(shù)小于該長(zhǎng)度，將紅黑樹(shù)轉(zhuǎn)為鏈表存儲(chǔ)；

static final int DEFAULT_INITIAL_CAPACITY: 默認(rèn)鍵值隊(duì)個(gè)數(shù)為16；

transient Node[] table：鍵值對(duì)數(shù)組，長(zhǎng)度動(dòng)態(tài)增加，但是總為2的冪；用transient修飾表示對(duì)象序列化時(shí)該字段不可被序列化；

HashMap鍵值對(duì)描述：Node

JDK1.6用Entry描述鍵值對(duì)，JDK1.8中用Node代替Entry；

static class Node implements Map.Entry {
    // hash存儲(chǔ)key的hashCode
    final int hash;
    // final:一個(gè)鍵值對(duì)的key不可改變
    final K key;
    V value;
    // 一個(gè)桶中的鍵值對(duì)用鏈表組織
    Node next;
    ...
}

HashMap中鍵值對(duì)的存儲(chǔ)形式為鏈表節(jié)點(diǎn)，hashCode相同的節(jié)點(diǎn)（位于同一個(gè)桶）用鏈表組織；

public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
}

鍵值對(duì)元素hashCode = key的hashCode與value的hashCode，高16位與低16位按位異或運(yùn)算；

紅黑樹(shù)：TreeNode

static final class TreeNode extends LinkedHashMap.Entry

JDK1.8新增，用來(lái)支持桶的紅黑樹(shù)結(jié)構(gòu)實(shí)現(xiàn)

HashMap重要方法分析 HashMap添加/更新鍵值對(duì)：put/putVal方法

public V put(K key, V value)內(nèi)部調(diào)用putVal方法實(shí)現(xiàn)；

public V put(K key, V value) {
    // 倒數(shù)第二個(gè)參數(shù)false：表示允許舊值替換
    // 最后一個(gè)參數(shù)true：表示HashMap不處于創(chuàng)建模式
    return putVal(hash(key), key, value, false, true);
}

putVal方法分析：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    // 槽數(shù)組未初始化或者未擴(kuò)容，先調(diào)用resize()擴(kuò)容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /**
     * Hash函數(shù)，(n - 1) & hash 計(jì)算key將被放置的槽位；
     * (n - 1) & hash 本質(zhì)上是hash % n，位運(yùn)算更快
     */
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 空桶，創(chuàng)建新的鍵值對(duì)節(jié)點(diǎn)，放入槽數(shù)組中；
        tab[i] = newNode(hash, key, value, null);
    // 鍵值對(duì)已在對(duì)應(yīng)桶中
    else {
        Node e; K k;
        // 與桶中首元素比較，如果key不同發(fā)生Hash沖突，在桶中添加新元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 當(dāng)前桶中無(wú)該鍵值對(duì)，且桶是紅黑樹(shù)結(jié)構(gòu)，按照紅黑樹(shù)結(jié)構(gòu)插入
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        // 當(dāng)前桶中無(wú)該鍵值對(duì)，且桶是鏈表結(jié)構(gòu)，按照鏈表結(jié)構(gòu)插入到尾部
        else {
            for (int binCount = 0; ; ++binCount) {
                // 遍歷到鏈表尾部
                if ((e = p.next) == null) {
                    // 創(chuàng)建鏈表節(jié)點(diǎn)并插入尾部
                    p.next = newNode(hash, key, value, null);
                    // 檢查鏈表長(zhǎng)度是否達(dá)到閾值，達(dá)到將該槽位節(jié)點(diǎn)組織形式轉(zhuǎn)為紅黑樹(shù)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 鏈表節(jié)點(diǎn)的與put操作相同時(shí)，不做重復(fù)操作，跳出循環(huán)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 找到 or 新建一個(gè)key和hashCode與插入元素相等的鍵值對(duì)，進(jìn)行put操作
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            /**
             * onlyIfAbsent為false或舊值為null時(shí)，允許替換舊值
             * 否則無(wú)需替換
             */
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 更新結(jié)構(gòu)化修改信息
    ++modCount;
    // 鍵值對(duì)數(shù)目超過(guò)閾值時(shí)，進(jìn)行rehash
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

散列分布策略

鍵值對(duì)的槽位 = (容量 - 1) & hash(key)

鍵值對(duì)槽位是鍵值對(duì)在tab數(shù)組的索引，本質(zhì)上 = hash(key) % 容量，位運(yùn)算速度更快；

本質(zhì)上是除數(shù)取余法，盡可能的散列均勻；

Hash函數(shù)

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

計(jì)算key的hashCode, h = Objects.hashCode(key);

h >>> 16表示對(duì)h無(wú)符號(hào)右移16位，高位補(bǔ)0；然后h與h >>> 16按位異或；

HashMap更新舊鍵值對(duì) or 添加新鍵值對(duì)的核心思想：

根據(jù)鍵值對(duì)key的hashCode計(jì)算鍵值對(duì)的在HashMap中槽位，

判斷是否空桶 Or 是否發(fā)生Hash沖突（與桶中首元素不同）

解決Hash沖突：根據(jù)桶組織形式是紅黑樹(shù) Or 鏈表進(jìn)行對(duì)應(yīng)插入操作；

鏈表形式完成插入后，檢查是否超過(guò)鏈表閾值，超過(guò)將鏈表->紅黑樹(shù)；

最后檢查鍵值對(duì)總數(shù)是否超過(guò)閾值，超過(guò)調(diào)用resize()進(jìn)行rehash操作；

HashMap刪除鍵值對(duì)：remove/removeNode方法 remove方法分析

public V remove(Object key) {
    Node e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

remove()方法內(nèi)部調(diào)用removeNode()方法實(shí)現(xiàn)

removeNode方法分析：

final Node removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node[] tab; Node p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 待刪除元素在桶中，但不是桶中首元素
        else if ((e = p.next) != null) {
            // 待刪除元素在紅黑樹(shù)結(jié)構(gòu)的桶中
            if (p instanceof TreeNode)
                // 查找紅黑樹(shù)
                node = ((TreeNode)p).getTreeNode(hash, key);
            else {
                // 遍歷鏈表，查找待刪除元素
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // p保存待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，用于鏈表刪除操作
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        /**
         * matchValue為true：表示必須value相等才進(jìn)行刪除操作
         * matchValue為false：表示無(wú)須判斷value，直接根據(jù)key進(jìn)行刪除操作
         */
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 桶為紅黑數(shù)結(jié)構(gòu)，刪除節(jié)點(diǎn)
            if (node instanceof TreeNode)
                // movable參數(shù)用于紅黑樹(shù)操作
                ((TreeNode)node).removeTreeNode(this, tab, movable);
            // 待刪除節(jié)點(diǎn)是桶鏈表表頭，將子節(jié)點(diǎn)放進(jìn)桶位
            else if (node == p)
                tab[index] = node.next;
            // 待刪除節(jié)點(diǎn)在桶鏈表中間
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    // 待刪除元素不存在，返回null
    return null;
}

HashMap訪問(wèn)鍵值對(duì)：get/getNode方法 get方法

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

get方法通過(guò)指定key獲得對(duì)應(yīng)鍵值對(duì)，內(nèi)部調(diào)用getNode方法實(shí)現(xiàn)；

getNode方法

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) {
            // 紅黑樹(shù)查找
            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;
}

getNode方法查找過(guò)程和putVal一樣，先查找對(duì)應(yīng)桶的首元素，然后根據(jù)紅黑樹(shù)結(jié)構(gòu) Or 鏈表結(jié)構(gòu)對(duì)應(yīng)查找；

HashMap重散列操作：resize方法

final Node[] resize() {
    // 保存舊table，容量，閾值
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 舊table容量已超過(guò)最大容量，更新閾值為Integer.MAX_VALUE
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 調(diào)整新容量為舊容量2倍，左移一位實(shí)現(xiàn)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap == 0 && oldThr > 0
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // oldCap == 0 && oldThr == 0
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 紅黑樹(shù)桶進(jìn)行rehash操作
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                
                // 鏈表桶進(jìn)行rehash操作
                // 根據(jù)e.hash & oldCap)是否為0把鏈表分成兩個(gè)鏈表，進(jìn)行rehash
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node 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;
}

當(dāng)鍵值對(duì)總數(shù)超過(guò)閾值threshold, HashMap通過(guò)resize方法實(shí)現(xiàn)重散列/rehash

HashMap調(diào)整容量：tableSizeFor()

static final int tableSizeFor(int cap)：得到>=cap的2的最小冪值；
由指定容量參數(shù)的構(gòu)造器調(diào)用，計(jì)算rehash閾值threshold；

參考

[1] http://www.cnblogs.com/leesf456/p/5242233.html
[2] http://www.cnblogs.com/ToBeAProgrammer

云服務(wù)器 GPU云服務(wù)器 JDK1.8 寶塔卸載默認(rèn)的jdk1.8 linux服務(wù)器安裝jdk1.8 _HashMap

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

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

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

登陸后可評(píng)論

0條評(píng)論

0xE7A38A

男|高級(jí)講師

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

TA的文章

如何徹底卸載刪除Google Update服務(wù)?

閱讀 3926·2021-11-18 13:19
??國(guó)慶七天的總結(jié)

閱讀 1179·2021-10-11 10:58
移動(dòng)端用戶(hù)體驗(yàn)（UE）優(yōu)化歷程

閱讀 3291·2019-08-29 16:39
網(wǎng)絡(luò)操作回調(diào)函數(shù) http

閱讀 3140·2019-08-26 12:08
js異步解決方案 --- 回調(diào)函數(shù) vs promise vs generater/yield vs

閱讀 2034·2019-08-26 11:33
Undefined和Null

閱讀 2460·2019-08-23 18:30
【10】JavaScript 面向?qū)ο蟾呒?jí)——繼承模式

閱讀 1308·2019-08-23 18:21
【js】what is 繼承

閱讀 2522·2019-08-23 18:18

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

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

HashMap源碼分析_JDK1.8版本

散列分布策略

Hash函數(shù)

相關(guān)文章

**集合框架源碼學(xué)習(xí)之HashMap(JDK1.8)**

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

前百度面試官整理的——Java后端面試題（一）

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

ConcurrentHashMap源碼分析_JDK1.8版本

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

0條評(píng)論

0xE7A38A

男|高級(jí)講師

TA的文章

如何徹底卸載刪除Google Update服務(wù)?

??國(guó)慶七天的總結(jié)

移動(dòng)端用戶(hù)體驗(yàn)（UE）優(yōu)化歷程

網(wǎng)絡(luò)操作回調(diào)函數(shù) http

js異步解決方案 --- 回調(diào)函數(shù) vs promise vs generater/yield vs

Undefined和Null

【10】JavaScript 面向?qū)ο蟾呒?jí)——繼承模式

【js】what is 繼承

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

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

HashMap源碼分析_JDK1.8版本

散列分布策略

Hash函數(shù)

相關(guān)文章

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

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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