簡介

HashMap最早出現(xiàn)在JDK1.2中，底層基于散列算法實現(xiàn)。HashMap 允許 null 鍵和 null 值，是非線程安全類，在多線程環(huán)境下可能會存在問題。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了和順免費建站歡迎大家使用！

1.8版本的HashMap數(shù)據(jù)結(jié)構(gòu)：

為什么有的是鏈表有的是紅黑樹？

默認(rèn)鏈表長度大于8時轉(zhuǎn)為樹

結(jié)構(gòu)

Node是HhaspMap中的一個靜態(tài)內(nèi)部類 ：

//Node是單向鏈表，實現(xiàn)了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    //構(gòu)造函數(shù)
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // getter and setter ... toString ...
    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;
    }
}

TreeNode 是紅黑樹的數(shù)據(jù)結(jié)構(gòu)。

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

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

類定義

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 

變量

/**
 * 默認(rèn)初始容量16(必須是2的冪次方)
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * 最大容量，2的30次方
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默認(rèn)加載因子，用來計算threshold
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 鏈表轉(zhuǎn)成樹的閾值，當(dāng)桶中鏈表長度大于8時轉(zhuǎn)成樹 
   threshold = capacity * loadFactor
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 進(jìn)行resize操作時，若桶中數(shù)量少于6則從樹轉(zhuǎn)成鏈表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對應(yīng)的table的最小大小

 當(dāng)需要將解決 hash 沖突的鏈表轉(zhuǎn)變?yōu)榧t黑樹時，
 需要判斷下此時數(shù)組容量，
 若是由于數(shù)組容量太?。ㄐ∮凇IN_TREEIFY_CAPACITY　）
 導(dǎo)致的 hash 沖突太多，則不進(jìn)行鏈表轉(zhuǎn)變?yōu)榧t黑樹操作，
 轉(zhuǎn)為利用　resize() 函數(shù)對　hashMap 擴(kuò)容
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/**
 保存Node<K,V>節(jié)點的數(shù)組
 該表在首次使用時初始化，并根據(jù)需要調(diào)整大小。 分配時，
 長度始終是2的冪。
 */
transient Node<K,V>[] table;

/**
 * 存放具體元素的集
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 記錄 hashMap 當(dāng)前存儲的元素的數(shù)量
 */
transient int size;

/**
 * 每次更改map結(jié)構(gòu)的計數(shù)器
 */
transient int modCount;

/**
 * 臨界值 當(dāng)實際大小(容量*填充因子)超過臨界值時，會進(jìn)行擴(kuò)容
 */
int threshold;

/**
 * 負(fù)載因子：要調(diào)整大小的下一個大小值（容量*加載因子）。
 */
final float loadFactor;

構(gòu)造方法

/**
 * 傳入初始容量大小，使用默認(rèn)負(fù)載因子值 來初始化HashMap對象
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 默認(rèn)容量和負(fù)載因子
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
 * 傳入初始容量大小和負(fù)載因子 來初始化HashMap對象
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 初始容量不能小于0，否則報錯
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 初始容量不能大于最大值，否則為最大值                                       
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //負(fù)載因子不能小于或等于0，不能為非數(shù)字    
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 初始化負(fù)載因子                                       
    this.loadFactor = loadFactor;
    // 初始化threshold大小
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 找到大于或等于 cap 的最小2的整數(shù)次冪的數(shù)。
 */
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;
}

tableSizeFor方法詳解：

用位運算找到大于或等于 cap 的最小2的整數(shù)次冪的數(shù)。比如10，則返回16

1. 讓cap-1再賦值給n的目的是使得找到的目標(biāo)值大于或等于原值。例如二進(jìn)制0100,十進(jìn)制是4,若不減1而直接操作，答案是0001 0000十進(jìn)制是16，明顯不符合預(yù)期。

2. 對n右移1位：001xx…xxx，再位或：011xx…xxx

3. 對n右移2位：00011…xxx，再位或：01111…xxx

4. 對n右移4位…

5. 對n右移8位…

6. 對n右移16位,因為int最大就2^32所以移動1、2、4、8、16位并取位或,會將最高位的1后面的位全變?yōu)?。

7. 再讓結(jié)果n+1，即得到了2的整數(shù)次冪的值了。

附帶一個實例：

loadFactor 負(fù)載因子

對于 HashMap 來說，負(fù)載因子是一個很重要的參數(shù)，該參數(shù)反應(yīng)了 HashMap 桶數(shù)組的使用情況。通過調(diào)節(jié)負(fù)載因子，可使 HashMap 時間和空間復(fù)雜度上有不同的表現(xiàn)。

當(dāng)我們調(diào)低負(fù)載因子時，HashMap 所能容納的鍵值對數(shù)量變少。擴(kuò)容時，重新將鍵值對存儲新的桶數(shù)組里，鍵的鍵之間產(chǎn)生的碰撞會下降，鏈表長度變短。此時，HashMap 的增刪改查等操作的效率將會變高，這里是典型的拿空間換時間。

相反，如果增加負(fù)載因子（負(fù)載因子可以大于1），HashMap 所能容納的鍵值對數(shù)量變多，空間利用率高，但碰撞率也高。這意味著鏈表長度變長，效率也隨之降低，這種情況是拿時間換空間。至于負(fù)載因子怎么調(diào)節(jié)，這個看使用場景了。

一般情況下，我們用默認(rèn)值就可以了。大多數(shù)情況下0.75在時間跟空間代價上達(dá)到了平衡所以不建議修改。

查找

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 獲取hash值
static final int hash(Object key) {
    int h;
    // 拿到key的hash值后與其五符號右移16位取與
    // 通過這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進(jìn)行異或，以此加大低位信息的隨機(jī)性，變相的讓高位數(shù)據(jù)參與到計算中。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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) {
        // 判斷桶中第一項(數(shù)組元素)相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一個結(jié)點
        if ((e = first.next) != null) {
            // 是否是紅黑樹，是的話調(diào)用getTreeNode方法
            if (first instanceof TreeNode)
                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;
}

注意：

1. HashMap的hash算法(hash()方法)。

2. (n - 1) & hash等價于對 length 取余。

添加

public V put(K key, V value) {
    // 調(diào)用hash(key)方法來計算hash 
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; 
    Node<K,V> p; 
    int n, i;
    // 容量初始化：當(dāng)table為空，則調(diào)用resize()方法來初始化容器
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //確定元素存放在哪個桶中，桶為空，新生成結(jié)點放入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 比較桶中第一個元素(數(shù)組中的結(jié)點)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果鍵的值以及節(jié)點 hash 等于鏈表中的第一個鍵值對節(jié)點時，則將 e 指向該鍵值對
            e = p;
        // 如果桶中的引用類型為 TreeNode，則調(diào)用紅黑樹的插入方法
        else if (p instanceof TreeNode)
            // 放入樹中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //對鏈表進(jìn)行遍歷，并統(tǒng)計鏈表長度
            for (int binCount = 0; ; ++binCount) {
                // 到達(dá)鏈表的尾部
                if ((e = p.next) == null) {
                    //在尾部插入新結(jié)點
                    p.next = newNode(hash, key, value, null);
                    // 如果結(jié)點數(shù)量達(dá)到閾值，轉(zhuǎn)化為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 判斷鏈表中結(jié)點的key值與插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //判斷要插入的鍵值對是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否僅在 oldValue 為 null 的情況下更新鍵值對的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 鍵值對數(shù)量超過閾值時，則進(jìn)行擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

事實上，new HashMap();完成后，如果沒有put操作，是不會分配存儲空間的。

1. 當(dāng)桶數(shù)組 table 為空時，通過擴(kuò)容的方式初始化 table

2. 查找要插入的鍵值對是否已經(jīng)存在，存在的話根據(jù)條件判斷是否用新值替換舊值

3. 如果不存在，則將鍵值對鏈入鏈表中，并根據(jù)鏈表長度決定是否將鏈表轉(zhuǎn)為紅黑樹

4. 判斷鍵值對數(shù)量是否大于閾值，大于的話則進(jìn)行擴(kuò)容操作

擴(kuò)容機(jī)制

在 HashMap 中，桶數(shù)組的長度均是2的冪，閾值大小為桶數(shù)組長度與負(fù)載因子的乘積。當(dāng) HashMap 中的鍵值對數(shù)量超過閾值時，進(jìn)行擴(kuò)容。

HashMap 按當(dāng)前桶數(shù)組長度的2倍進(jìn)行擴(kuò)容，閾值也變?yōu)樵瓉淼?倍（如果計算過程中，閾值溢出歸零，則按閾值公式重新計算）。擴(kuò)容之后，要重新計算鍵值對的位置，并把它們移動到合適的位置上去。

final Node<K,V>[] resize() {
    // 拿到數(shù)組桶
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果數(shù)組桶的容量大與0
    if (oldCap > 0) {
        // 如果比最大值還大，則賦值為最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果擴(kuò)容后小于最大值 而且 舊數(shù)組桶大于初始容量16， 閾值左移1(擴(kuò)大2倍)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果數(shù)組桶容量<=0 且 舊閾值 >0
    else if (oldThr > 0) // initial capacity was placed in threshold
        // 新容量=舊閾值
        newCap = oldThr;
    // 如果數(shù)組桶容量<=0 且 舊閾值 <=0
    else {               // zero initial threshold signifies using defaults
        // 新容量=默認(rèn)容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新閾值= 負(fù)載因子*默認(rèn)容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新閾值為0
    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"})
        // 創(chuàng)建新數(shù)組
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 覆蓋數(shù)組桶    
    table = newTab;
    // 如果舊數(shù)組桶不是空，則遍歷桶數(shù)組，并將鍵值對映射到新的桶數(shù)組中
    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)
                    // 重新映射時，需要對紅黑樹進(jìn)行拆分
                    ((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;
                    // 遍歷鏈表，并將鏈表節(jié)點按原順序進(jìn)行分組
                    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;
}

整體步驟：

1. 計算新桶數(shù)組的容量 newCap 和新閾值 newThr

2. 根據(jù)計算出的 newCap 創(chuàng)建新的桶數(shù)組，桶數(shù)組 table 也是在這里進(jìn)行初始化的

3. 將鍵值對節(jié)點重新映射到新的桶數(shù)組里。如果節(jié)點是 TreeNode 類型，則需要拆分紅黑樹。如果是普通節(jié)點，則節(jié)點按原順序進(jìn)行分組。

總結(jié)起來，一共有三種擴(kuò)容方式：

1. 使用默認(rèn)構(gòu)造方法初始化HashMap。從前文可以知道HashMap在一開始初始化的時候會返回一個空的table，并且thershold為0。因此第一次擴(kuò)容的容量為默認(rèn)值DEFAULT_INITIAL_CAPACITY也就是16。同時threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。

2. 指定初始容量的構(gòu)造方法初始化HashMap。那么從下面源碼可以看到初始容量會等于threshold，接著threshold = 當(dāng)前的容量（threshold） * DEFAULT_LOAD_FACTOR。

3. HashMap不是第一次擴(kuò)容。如果HashMap已經(jīng)擴(kuò)容過的話，那么每次table的容量以及threshold量為原有的兩倍。

細(xì)心點的人會很好奇，為什么要判斷l(xiāng)oadFactor為0呢？

loadFactor小數(shù)位為 0，整數(shù)位可被2整除且大于等于8時，在某次計算中就可能會導(dǎo)致 newThr 溢出歸零。

疑問和進(jìn)階

1. JDK1.7是基于數(shù)組+單鏈表實現(xiàn)（為什么不用雙鏈表）

首先，用鏈表是為了解決hash沖突。

單鏈表能實現(xiàn)為什么要用雙鏈表呢?(雙鏈表需要更大的存儲空間)

2. 為什么要用紅黑樹，而不用平衡二叉樹？

插入效率比平衡二叉樹高，查詢效率比普通二叉樹高。所以選擇性能相對折中的紅黑樹。

3. 重寫對象的Equals方法時，要重寫hashCode方法，為什么？跟HashMap有什么關(guān)系？

equals與hashcode間的關(guān)系:

1. 如果兩個對象相同（即用equals比較返回true），那么它們的hashCode值一定要相同；

2. 如果兩個對象的hashCode相同，它們并不一定相同(即用equals比較返回false)

因為在 HashMap 的鏈表結(jié)構(gòu)中遍歷判斷的時候，特定情況下重寫的 equals 方法比較對象是否相等的業(yè)務(wù)邏輯比較復(fù)雜，循環(huán)下來更是影響查找效率。所以這里把 hashcode 的判斷放在前面，只要 hashcode 不相等就玩兒完，不用再去調(diào)用復(fù)雜的 equals 了。很多程度地提升 HashMap 的使用效率。

所以重寫 hashcode 方法是為了讓我們能夠正常使用 HashMap 等集合類，因為 HashMap 判斷對象是否相等既要比較 hashcode 又要使用 equals 比較。而這樣的實現(xiàn)是為了提高 HashMap 的效率。

附上源碼圖：

4. HashMap為什么不直接使用對象的原始hash值呢?

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

我們發(fā)現(xiàn)，HashMap的哈希值是通過上面的方式獲取，而不是通過key.hashCode()方法獲取。

原因：

通過移位和異或運算，可以讓 hash 變得更復(fù)雜，進(jìn)而影響 hash 的分布性。

5. 既然紅黑樹那么好，為啥hashmap不直接采用紅黑樹，而是當(dāng)大于8個的時候才轉(zhuǎn)換紅黑樹？

因為紅黑樹需要進(jìn)行左旋，右旋操作， 而單鏈表不需要。

以下都是單鏈表與紅黑樹結(jié)構(gòu)對比。

如果元素小于8個，查詢成本高，新增成本低。

如果元素大于8個，查詢成本低，新增成本高。

至于為什么選數(shù)字8，是大佬折中衡量的結(jié)果-.-，就像loadFactor默認(rèn)值0.75一樣。

對Java技術(shù)，架構(gòu)技術(shù)感興趣的同學(xué)，歡迎加群，一起學(xué)習(xí)，相互討論。可以獲取免費的學(xué)習(xí)資料，群號：614478470

標(biāo)題名稱：面試必會之HashMap源碼分析
標(biāo)題來源：http://aaarwkj.com/article32/pegopc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號、手機(jī)網(wǎng)站建設(shè)、營銷型網(wǎng)站建設(shè)、品牌網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、定制開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)