概述

HashMap是Java的一個(gè)集合類(lèi)，是我們?cè)陂_(kāi)發(fā)中經(jīng)常使用的。本文記錄個(gè)人閱讀源碼的一些步驟和理解。閱讀步驟大致為：變量-->構(gòu)造方法-->常用方法。
在JDK7中，HashMap的底層數(shù)據(jù)結(jié)構(gòu)為：數(shù)組+鏈表的形式。

image

在JDK8中，HashMap的底層數(shù)據(jù)結(jié)構(gòu)為：數(shù)組+鏈表+紅黑樹(shù)（TreeNode），增加紅黑樹(shù)的結(jié)構(gòu)。

image

變量

loadFactor 加載因子
默認(rèn)加載因子為0.75f,為何是0.75 而不是其他的值呢？
首先理解一下，什么是加載因子。
加載因子是表示Hsah表中元素的填滿(mǎn)的程度。如果加載因子越大,填滿(mǎn)的元素越多，所以空間利用率提高，但是沖突的機(jī)會(huì)加大了。反之亦然
沖突的機(jī)會(huì)越大，查找所需要的成本增加，查找時(shí)間也相應(yīng)的增加了。反之亦然。
結(jié)合前面兩條，我們必須在 "沖突的機(jī)會(huì)"與"空間利用率"之間尋找一種平衡與折衷。這種平衡與折衷本質(zhì)上是數(shù)據(jù)結(jié)構(gòu)中有名的"時(shí)間復(fù)雜度-空間復(fù)雜度"矛盾的平衡與折衷。
加載因子的值是可以大于1的。
threshold
threshold表示當(dāng)HashMap的size大于threshold時(shí)會(huì)執(zhí)行resize操作。
size
記錄數(shù)組的長(zhǎng)度
modCount
modCount是記錄HashMap發(fā)送結(jié)構(gòu)性變化的次數(shù)，比如擴(kuò)容、rehash。

另外大概了解一下HashMap的最大容量 1<<30也就是2的30次方，初始化容量為16。

構(gòu)造方法

HashMap(int, float)

為了方便閱讀，注釋直接寫(xiě)在了代碼里面。

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 初始化容量必須在 1<<30 以?xún)?nèi)
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
        // 調(diào)用了tableSizeFor方法，該方法是返回給定的`initialCapacity`值的向上取最近的2的冪。比如傳遞的值為12，返回16。
    this.threshold = tableSizeFor(initialCapacity);
}

HashMap(int)

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
該構(gòu)造方法，只是指定了初始化容量，使用默認(rèn)的加載因子，調(diào)用`HashMap(int, float)`方法。

常用方法

put 插入

put方法主要的實(shí)現(xiàn)過(guò)程如下，為了方便閱讀，將注釋寫(xiě)在了代碼中。

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)
        // 如果table為空，調(diào)用resize()方法，初始化一個(gè)table。
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 該節(jié)點(diǎn)不存在，新建節(jié)點(diǎn)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode) // 如果是p節(jié)點(diǎn)是紅黑樹(shù)節(jié)點(diǎn)，調(diào)用紅黑樹(shù)的put方法。
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { // 找到鏈表的最后一個(gè)節(jié)點(diǎn)，插入新的節(jié)點(diǎn)
                    p.next = newNode(hash, key, value, null);
                    // 如果binCount的大小大于等于TREEIFY_THRESHOLD-1（TREEIFY_THRESHOLD默認(rèn)為8），調(diào)用treeifyBin方法，后面單獨(dú)介紹該方法。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 鏈表中存在該節(jié)點(diǎn)，跳出循環(huá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;
            // 根據(jù)oblyIfAbsent是否更新值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 修改 modCount
    ++modCount;
    // 如果table大小大于了閾值，則需要擴(kuò)容。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

上面已經(jīng)介紹了put方法的主流程，接下來(lái)分析一下該方法中留下的幾個(gè)問(wèn)題。

treeifyBin方法

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
            // 判斷是否需要擴(kuò)容，MIN_TREEIFY_CAPACITY的值：64,也就是說(shuō)在大小為16、 32 的時(shí)候，不要進(jìn)行結(jié)構(gòu)轉(zhuǎn)換
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                // 將節(jié)點(diǎn)轉(zhuǎn)為樹(shù)節(jié)點(diǎn)
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p; // 將p樹(shù)節(jié)點(diǎn)指向hd樹(shù)節(jié)點(diǎn)
                else {
                    p.prev = tl; // 當(dāng)前p樹(shù)節(jié)點(diǎn)指向 p樹(shù)節(jié)點(diǎn)的前一樹(shù)節(jié)點(diǎn)
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

treeifyBin方法主要是把容器里的元素變成樹(shù)結(jié)構(gòu)。當(dāng)HashMap的內(nèi)部元素?cái)?shù)組中某個(gè)位置上存在多個(gè)hash值相同的鍵值對(duì)，這些Node已經(jīng)形成了一個(gè)鏈表，當(dāng)該鏈表的長(zhǎng)度大于等于7的時(shí)候，會(huì)調(diào)用該方法來(lái)進(jìn)行一個(gè)特殊處理。

get 取值

源碼中g(shù)et方法代碼如下，為了方便閱讀，在代碼中會(huì)寫(xiě)上相應(yīng)的注釋。

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

這段代碼比較簡(jiǎn)單，調(diào)用了getNode()方法，并傳入hash(key)和key，所以說(shuō)取值的過(guò)程在getNode中，下面看看該方法的具體實(shí)現(xiàn)：

final Node<K,V> getNode(int hash, Object key) {
    // 定義一個(gè)新的table數(shù)組、首節(jié)點(diǎn)
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判斷table數(shù)組是否為空，并且根據(jù)hash值算出 tab[(n - 1) & hash]是否為空，其中一個(gè)條件為空，說(shuō)明key沒(méi)有對(duì)應(yīng)的value值。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判斷首節(jié)點(diǎn)的hash和key是否都相等，如果都等，直接返回首節(jié)點(diǎn)
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 走到這兒，說(shuō)明是一個(gè)鏈表了或者紅黑樹(shù)了
        if ((e = first.next) != null) {
            // 判斷是否為紅黑樹(shù)
            if (first instanceof TreeNode)
                // 調(diào)用 紅黑樹(shù)的getTreeNode方法
                return ((TreeNode<K,V>)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ò)程相對(duì)而言是比較簡(jiǎn)單的，上面注釋基本上比較易懂的，在整個(gè)流程中，紅黑樹(shù)的取值方法，沒(méi)有說(shuō)到，接下來(lái)看看getTreeNode方法中主要流程。

final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

getTreeNode方法的實(shí)現(xiàn)過(guò)程如下：

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        // ph: p節(jié)點(diǎn)的hash值，pk:p節(jié)點(diǎn)的key值
        int ph, dir; K pk;
        // pl: p節(jié)點(diǎn)的左節(jié)點(diǎn)， pr：p節(jié)點(diǎn)的右節(jié)點(diǎn)
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            // p節(jié)點(diǎn)的hash值大于了 h（h是待get值的hash值），將左節(jié)點(diǎn)賦值給p節(jié)點(diǎn)
            p = pl;
        else if (ph < h)
            // p節(jié)點(diǎn)的hash值小于了 h（h是待get值的hash值），將右節(jié)點(diǎn)賦值給p節(jié)點(diǎn)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // 走到了這兒，說(shuō)明p.hash==h,只需要匹配key是否相等就好了。
            return p;
        else if (pl == null)
            // 左節(jié)點(diǎn)為空，將右節(jié)點(diǎn)賦值給p節(jié)點(diǎn)
            p = pr;
        else if (pr == null)
            // 右節(jié)點(diǎn)為空，將左節(jié)點(diǎn)賦值給p節(jié)點(diǎn)
            p = pl;
        // kc參數(shù)在首次使用比較鍵時(shí)緩存equivalentClassFor（key）。
        // comparableClassFor方法：只有當(dāng)傳入對(duì)象的運(yùn)行時(shí)類(lèi)型符合“class C implements Cormparable <C>”，則返回k的Class，否則返回null。
        // compareComparables方法: 如果pk匹配kc（k的篩選可比類(lèi)），則返回k.compareTo（pk），否則返回0。
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

在本文中，主要是對(duì)常用的方法get、put做了一個(gè)學(xué)習(xí)了解。

文章來(lái)源：JDK8:HashMap源碼學(xué)習(xí)

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

HashMap（jdk8）源碼閱讀

HashMap（jdk8）源碼閱讀

概述

變量

構(gòu)造方法

HashMap(int, float)

HashMap(int)

常用方法

put 插入

get 取值

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

HashMap（jdk8）源碼閱讀

概述

變量

構(gòu)造方法

HashMap(int, float)

HashMap(int)

常用方法

put 插入

get 取值

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av