亚洲全黄无码一级在线看_国产剧情久久久性色_无码av一区二区三区无码_亚洲成a×人片在线观看

作者簡介：王磊，前360技術(shù)專家。本文選自：拉勾教育《Java 源碼剖析 34 講》

你好，我是你的 Java 面試課老師王磊，歡迎進(jìn)入第 02 課時的內(nèi)容“HashMap 底層實(shí)現(xiàn)原理是什么？它都做了哪些優(yōu)化？”

HashMap 是使用頻率最高的類型之一，同時也是面試經(jīng)常被問到的問題之一，這是因?yàn)?HashMap 的知識點(diǎn)有很多，同時它又屬于 Java 基礎(chǔ)知識的一部分，因此在面試中經(jīng)常被問到。

本課時的面試題是，HashMap 底層是如何實(shí)現(xiàn)的？在 JDK 1.8 中它都做了哪些優(yōu)化？

典型回答

在 JDK 1.7 中 HashMap 是以數(shù)組加鏈表的形式組成的，JDK 1.8 之后新增了紅黑樹的組成結(jié)構(gòu)，當(dāng)鏈表大于 8 時，鏈表結(jié)構(gòu)會轉(zhuǎn)換成紅黑樹結(jié)構(gòu)，它的組成結(jié)構(gòu)如下圖所示：

數(shù)組中的元素我們稱之為哈希桶，它的定義如下：

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;
    

可以看出每個哈希桶中包含了四個字段：hash、key、value、next，其中 next 表示鏈表的下一個節(jié)點(diǎn)。

JDK 1.8 之所以添加紅黑樹是因?yàn)橐坏╂湵磉^長，會嚴(yán)重影響 HashMap 的性能，而紅黑樹具有快速增刪改查的特點(diǎn)，這樣就可以有效的解決鏈表過長時操作比較慢的問題。

本文選自：拉勾教育《Java 源碼剖析 34 講》

考點(diǎn)分析

上面大體介紹了 HashMap 的組成結(jié)構(gòu)，但面試官想要知道的遠(yuǎn)遠(yuǎn)不止這些，和 HashMap 相關(guān)的面試題還有以下幾個：

JDK 1.8 HashMap 擴(kuò)容時做了哪些優(yōu)化？加載因子為什么是 0.75？當(dāng)有哈希沖突時，HashMap 是如何查找并確認(rèn)元素的？HashMap 源碼中有哪些重要的方法？ 知識拓展1.HashMap 源碼分析

聲明：本系列課程在未做特殊說明的情況下，都是以目前主流的 JDK 版本 1.8 為例來進(jìn)行源碼分析的。

HashMap 源碼中包含了以下幾個屬性：

// HashMap 初始化長度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


// HashMap 最大長度
static final int MAXIMUM_CAPACITY = 1 << 30; // 1073741824


// 默認(rèn)的加載因子 (擴(kuò)容因子)
static final float DEFAULT_LOAD_FACTOR = 0.75f;


// 轉(zhuǎn)換紅黑樹的臨界值，當(dāng)鏈表長度大于此值時，會把鏈表結(jié)構(gòu)轉(zhuǎn)換為紅黑樹結(jié)構(gòu)
static final int TREEIFY_THRESHOLD = 8;


// 轉(zhuǎn)換鏈表的臨界值，當(dāng)元素小于此值時，會將紅黑樹結(jié)構(gòu)轉(zhuǎn)換成鏈表結(jié)構(gòu)
static final int UNTREEIFY_THRESHOLD = 6;


// 最小樹容量
static final int MIN_TREEIFY_CAPACITY =

?什么是加載因子？加載因子為什么是 0.75？

加載因子也叫擴(kuò)容因子或負(fù)載因子，用來判斷什么時候進(jìn)行擴(kuò)容的，假如加載因子是 0.5，HashMap 的初始化容量是 16，那么當(dāng) HashMap 中有 16*0.5=8 個元素時，HashMap 就會進(jìn)行擴(kuò)容。

那加載因子為什么是 0.75 而不是 0.5 或者 1.0 呢？

這其實(shí)是出于容量和性能之間平衡的結(jié)果：

當(dāng)加載因子設(shè)置比較大的時候，擴(kuò)容的門檻就被提高了，擴(kuò)容發(fā)生的頻率比較低，占用的空間會比較小，但此時發(fā)生 Hash 沖突的幾率就會提升，因此需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)來存儲元素，這樣對元素的操作時間就會增加，運(yùn)行效率也會因此降低；而當(dāng)加載因子值比較小的時候，擴(kuò)容的門檻會比較低，因此會占用更多的空間，此時元素的存儲就比較稀疏，發(fā)生哈希沖突的可能性就比較小，因此操作性能會比較高。

所以綜合了以上情況就取了一個 0.5 到 1.0 的平均數(shù) 0.75 作為加載因子。

HashMap 源碼中三個重要方法：查詢、新增和數(shù)據(jù)擴(kuò)容。

先來看查詢源碼：

public V get(Object key) {
    Node<K,V> e;
    // 對 key 進(jìn)行哈希操作
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> 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;
        // 下一個節(jié)點(diǎn)非空判斷
        if ((e = first.next) != null) {
            // 如果第一節(jié)點(diǎn)是樹結(jié)構(gòu)，則使用 getTreeNode 直接獲取相應(yīng)的數(shù)據(jù)
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // 非樹結(jié)構(gòu)，循環(huán)節(jié)點(diǎn)判斷
                // hash 相等并且 key 相同，則返回此節(jié)點(diǎn)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

從以上源碼可以看出，當(dāng)哈希沖突時我們需要通過判斷 key 值是否相等，才能確認(rèn)此元素是不是我們想要的元素。?

OK，這節(jié)課就講到這里啦，下一課時我將分享“線程的狀態(tài)有哪些？它是如何工作的？”，記得按時來聽課哈。

本文選自：拉勾教育《Java 源碼剖析 34 講》

版權(quán)聲明：本文版權(quán)歸屬拉勾教育及該專欄作者，任何媒體、網(wǎng)站或個人未經(jīng)本網(wǎng)協(xié)議授權(quán)不得轉(zhuǎn)載、鏈接、轉(zhuǎn)貼或以其他方式復(fù)制發(fā)布/發(fā)表，違者必究。