Map集合之HashMap的使用及說明

更新時間：2022年10月12日 15:04:37 作者：桐花思雨

這篇文章主要介紹了Map集合之HashMap的使用及說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

HashMap 概述

HashMap 是通過 put(key,value) 存儲，get(key)來獲取。當傳入 key 時，HashMap 會根據(jù) key 的 hashCode() 方法計算出 hash 值，根據(jù) hash 值將 value 保存在 bucket(桶)里。當計算出的 hash 值相同時，稱之為 hash 沖突。HashMap 的做法是用鏈表和紅黑樹存儲相同 hash 值的 value

jdk 1.8 之前與之后的 HashMap

在 jdk1.8 之前的 HashMap 是由數(shù)組 + 鏈表來實現(xiàn)的，數(shù)組是 HashMap 的主體。鏈表主要是為了解決 hash 沖突的
在 jdk1.8 之后的 HashMap 是由數(shù)組 + 鏈表 + 紅黑樹來實現(xiàn)的，在解決 hash 沖突時有了較大的變化。當鏈表長度大于閾值 8 時，并且數(shù)組的長度大于 64 時，此時此索引位置上的所有數(shù)據(jù)改為使用紅黑樹存儲

在這里插入圖片描述

HashMap 的數(shù)組，鏈表，紅黑樹之間的轉(zhuǎn)換

當創(chuàng)建 HashMap 集合對象的時候，在 jdk1.8 之前，是在它的構(gòu)造方法中創(chuàng)建了一個默認長度是 16 的 Entry[] table 的數(shù)組來存儲鍵值對數(shù)據(jù)的。而從 jdk1.8開始，是在第一次調(diào)用 put 方法時創(chuàng)建了一個默認長度是 16 的 Node[] table 的數(shù)組來存儲鍵值對數(shù)據(jù)的
數(shù)組創(chuàng)建完成后，當添加一個元素(key,value)時，首先計算元素 key 的 hash 值，以此確定插入數(shù)組中的位置。但是可能存在同一 hash 值的元素已經(jīng)被放在數(shù)組同一位置了，這時就添加到同一 hash 值的元素的后面，他們在數(shù)組的同一位置，這就形成了單鏈表，同一各鏈表上的 Hash 值是相同的。當鏈表長度大于閾值 8 時，并且數(shù)組的長度大于 64 時，此時此索引位置上的所有數(shù)據(jù)改為使用紅黑樹存儲，這樣大大提高了查找的效率
在轉(zhuǎn)換為紅黑樹存儲數(shù)據(jù)后，如果此時再次刪除數(shù)據(jù)，當紅黑樹的節(jié)點數(shù)小于 6 時，那么此時的紅黑樹將轉(zhuǎn)換為單鏈表結(jié)構(gòu)來存儲數(shù)據(jù)

HashMap 擴容機制

默認情況下，數(shù)組大小為 16，那么當 HashMap 中元素個數(shù)超過 16 * 0.75 = 12（這個值就是代碼中的 threshold 值，也叫做臨界值）的時候，就把數(shù)組的大小擴展為 2*16 = 32，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置

0.75 這個值稱為負載因子，那么為什么負載因子為 0.75 呢? 這是通過大量實驗統(tǒng)計得出來的，如果過小，比如 0.5，那么當存放的元素超過一半時就進行擴容，會造成資源的浪費；如果過大，比如 1，那么當元素滿的時候才進行擴容，會使 get,put 操作的碰撞幾率增加

HashMap 源碼

HashMap 的基本屬性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列號
    private static final long serialVersionUID = 362498820763181265L;    
    // 默認的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30; 
    // 默認的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 當桶(bucket)上的結(jié)點數(shù)大于這個值時會轉(zhuǎn)成紅黑樹;+對應(yīng)的table的最小大小為64，即MIN_TREEIFY_CAPACITY ；這兩個條件都滿足，會鏈表會轉(zhuǎn)紅黑樹
    static final int TREEIFY_THRESHOLD = 8; 
    // 當桶(bucket)上的結(jié)點數(shù)小于這個值時樹轉(zhuǎn)鏈表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對應(yīng)的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存儲元素的數(shù)組，總是2的冪次倍
    transient Node<k,v>[] table; 
    // 存放具體元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的個數(shù)，注意這個不等于數(shù)組的長度。
    transient int size;
    // 每次擴容和更改map結(jié)構(gòu)的計數(shù)器
    transient int modCount;   
    // 臨界值 當實際大小(容量*填充因子)超過臨界值時，會進行擴容
    int threshold;
    // 填充因子
    final float loadFactor;
}

HashMap 中涉及到的數(shù)據(jù)結(jié)構(gòu)

鏈表節(jié)點（單鏈表）

Node 是 HashMap 的一個內(nèi)部類，實現(xiàn)了 Map.Entry 接口，本質(zhì)上是一個單鏈表的數(shù)據(jù)結(jié)構(gòu)。鏈表中的每個節(jié)點就是一個 Node 對象

static class Node<k,v> implements Map.Entry<k,v> {
    final int hash;
    final K key;
    V value;
    Node<k,v> next; // 下一個節(jié)點
    
    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;
    }
    // 判斷兩個node是否相等,若key和value都相等，返回true?？梢耘c自身比較為true
    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;
    }
}

紅黑樹節(jié)點

紅黑樹比鏈表多了四個變量，parent 父節(jié)點、left 左節(jié)點、right 右節(jié)點、prev上一個同級節(jié)點

static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
? ? TreeNode<k,v> parent; ?// 父節(jié)點
? ? TreeNode<k,v> left; // 左子樹
? ? TreeNode<k,v> right;// 右子樹
? ? TreeNode<k,v> prev; // 刪除時需要取消下一個鏈接
? ? boolean red; ? ?// 顏色屬性
? ? TreeNode(int hash, K key, V val, Node<k,v> next) {
? ? ? ? super(hash, key, val, next);
? ? }
?
? ? // 返回當前節(jié)點的根節(jié)點
? ? final TreeNode<k,v> root() {
? ? ? ? for (TreeNode<k,v> r = this, p;;) {
? ? ? ? ? ? if ((p = r.parent) == null)
? ? ? ? ? ? ? ? return r;
? ? ? ? ? ? r = p;
? ? ? ? }
? ? }
? ??
? ? // ......省略
}

位桶

存儲（位桶）的數(shù)組

transient Node<K,V>[] table;

HashMap 類中有一個非常重要的字段，就是 Node[] table，即哈希桶數(shù)組，明顯它是一個 Node 的數(shù)組

HashMap 的 put() 方法

數(shù)組判斷

判斷 tab[] 數(shù)組是否為 null 或長度為 0，如果是 null 或長度為 0；則通過 resize() 方法初始化數(shù)組，并獲取長度
如果單鏈表 Node<K,V> p == tab[i = (n - 1) & hash]) == null，就直接 put 進單鏈表中，說明此時并沒有發(fā)生 hash 沖突
如果該數(shù)組索引位置之前放入過數(shù)據(jù)，在通過 key 的 hash 值，(k = p.key) == key || (key != null && key.equals(k)) 判斷該 put 的數(shù)據(jù)是否與數(shù)組索引位置數(shù)據(jù)相同；如果相同，使用 e = p 來則初始化數(shù)組 Node<K,V> e

紅黑樹判斷

如果不相同，則判斷是否是紅黑樹，如果是紅黑樹就直接插入樹中

鏈表判斷

如果不是紅黑樹，就遍歷鏈表每個節(jié)點，并判斷鏈表末尾節(jié)點是否為 null；如果為 null，則在該單鏈表末尾節(jié)點插入數(shù)據(jù)，并判斷是否 binCount > 8 -1，為 true 的話會調(diào)用 treeifyBin(tab, hash) 方法，該方法在后面詳解
然后，判斷該 put 的數(shù)據(jù)是否與單鏈表的某個節(jié)點數(shù)據(jù)相同，如果相同則跳出循環(huán)，執(zhí)行下一步

public V put(K key, V value) {
?? ?return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
? ? ? ? ? ? ? ? ? ?boolean evict) {
? ? // tab表示 Node<K,V>類型的數(shù)組，p表示某一個具體的單鏈表 Node<K,V> 節(jié)點
? ? Node<K,V>[] tab; Node<K,V> p; int n, i;
? ? // 判斷 table[] 是否為空，如果是空的就創(chuàng)建一個 table[]，并獲取他的長度n
? ? if ((tab = table) == null || (n = tab.length) == 0)
? ? ?? ?n = (tab = resize()).length;?? ?
? ? // tab[i = (n - 1) & hash] 表示數(shù)組中的某一個具體位置的數(shù)據(jù)
? ? // 如果單鏈表 Node<K,V> p == tab[i = (n - 1) & hash]) == null，
? ? // 就直接 put 進單鏈表中，說明此時并沒有發(fā)生 Hash 沖突
? ? if ((p = tab[i = (n - 1) & hash]) == null)
? ? ?? ?tab[i] = newNode(hash, key, value, null);
? ? else {
?? ??? ?// 說明索引位置已經(jīng)放入過數(shù)據(jù)了，已經(jīng)在單鏈表處產(chǎn)生了Hash沖突
? ? ? ? Node<K,V> e; K k;
?? ??? ?// 判斷 put 的數(shù)據(jù)和之前的數(shù)據(jù)是否重復
? ? ? ? if (p.hash == hash &&
? ? ? ? ? ? // 進行 key 的 hash 值和 key 的 equals() 和 == 比較，如果都相等，則初始化節(jié)點 Node<K,V> e
? ? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k)))) ? ?? ??? ??? ?
? ? ? ? ? ? e = p;
?? ??? ?// 判斷是否是紅黑樹，如果是紅黑樹就直接插入樹中
? ? ? ? else if (p instanceof TreeNode)
? ? ? ? ?? ?e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
? ? ? ? else {
?? ??? ??? ?// 如果不是紅黑樹，就遍歷每個節(jié)點，判斷單鏈表長度是否大于等于 7，
?? ??? ??? ?// 如果單鏈表長度大于等于 7，數(shù)組的長度小于 64 時，會優(yōu)先選擇擴容
?? ??? ??? ?// 如果單鏈表長度大于等于 7，數(shù)組的長度大于 64 時，才會選擇單鏈表--->紅黑樹
? ? ? ? ? ? for (int binCount = 0; ; ++binCount) {
? ? ? ? ? ? ?? ?if ((e = p.next) == null) {
? ? ? ? ? ? ?? ??? ?// 采用尾插法，在單鏈表中插入數(shù)據(jù)
? ? ? ? ? ? ? ? ?? ?p.next = newNode(hash, key, value, null);
? ? ? ? ? ? ? ? ?? ?// 如果 binCount >= 8 - 1
? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD - 1)?
? ? ? ? ? ? ? ? ? ? ?? ?treeifyBin(tab, hash);
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? }
?? ??? ??? ??? ?// 判斷索引每個元素的key是否可要插入的key相同，如果相同就直接覆蓋
? ? ? ? ? ? ? ? if (e.hash == hash &&
?? ??? ??? ??? ??? ?((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ?p = e;
?? ??? ??? ?}
?? ??? ?}
? ? ? ? if (e != null) {?
? ? ? ? ?? ?// 此時說明 key 的 hash 值和 key 的 equals() 和 == 比較結(jié)果都相等
? ? ? ? ?? ?// 說明數(shù)組或者單鏈表中有完全相同的 key
?? ??? ??? ?// 只需要將 value 覆蓋，并將 oldValue 返回即可
? ? ? ? ?? ?V oldValue = e.value;
? ? ? ? ? ? if (!onlyIfAbsent || oldValue == null)
? ? ? ? ? ? ?? ?e.value = value;
? ? ? ? ? ? ? ? afterNodeAccess(e);
? ? ? ? ? ? ? ?? ?return oldValue;
? ? ? ? }
?? ?}
?? ?// 說明沒有key相同，因此要插入一個key-value，并記錄內(nèi)部結(jié)構(gòu)變化次數(shù)
? ? ++modCount;
? ? // 判斷是否擴容
? ? if (++size > threshold)
? ? ?? ?resize();
? ? afterNodeInsertion(evict);
? ? return null;
}

HashMap 的 get() 方法

首先定位鍵值對所在桶的位置，之后再對鏈表或紅黑樹進行查找

判斷表或 key 是否是 null，如果是直接返回 null key 對應(yīng)的 value
判斷索引處第一個 key 與傳入 key 是否相等，如果相等直接返回
如果不相等，判斷鏈表是否是紅黑二叉樹，如果是，直接從樹中取值
如果不是樹，就遍歷鏈表查找

public V get(Object key) {
?? ?Node<K,V> e;
? ? 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;
?? ?// 1.如果表不是空的，并且要查找索引處有值，就判斷位于第一個的key是否是要查找的key
?? ?if ((tab = table) != null && (n = tab.length) > 0 &&
?? ??? ?(first = tab[(n - 1) & hash]) != null) {
?? ??? ?// 1.1.檢查要查找的是否是第一個節(jié)點
?? ??? ?if (first.hash == hash && // always check first node
?? ??? ??? ?((k = first.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? return first;
?? ??? ??? ?// 1.2.沿著第一個節(jié)點繼續(xù)查找
? ? ? ? ? ? if ((e = first.next) != null) {
? ? ? ? ? ? ?? ?// 1.2.1.如果是紅黑樹，那么調(diào)用紅黑樹的方法查找
? ? ? ? ? ? ? ? if (first instanceof TreeNode)
? ? ? ? ? ? ? ? ? ? return ((TreeNode<K,V>)first).getTreeNode(hash, key);
?? ??? ??? ??? ?// 1.2.2.如果是鏈表，那么采用鏈表的方式查找
? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? ? ? ? ? ? ? return e;
?? ??? ??? ?} while ((e = e.next) != null);
?? ??? ?}
?? ?}
?? ?return null;
}

HashMap 的 remove 方法

HashMap 的刪除操作并不復雜，僅需三個步驟即可完成

定位桶位置
遍歷鏈表或紅黑樹并找到鍵值相等的節(jié)點
刪除節(jié)點

public V remove(Object key) {
? ? Node<K,V> e;
? ? return (e = removeNode(hash(key), key, null, false, true)) == null ?
? ? ? ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
? ? ? ? ? ? ? ? ? ? ? ? ? ?boolean matchValue, boolean movable) {
? ??? ?// ------------------1. 查找到要刪除的節(jié)點------------------ ? ? ? ? ? ? ? ? ? ? ??
? ? // tab當前數(shù)組，n當前數(shù)組容量，p根據(jù)hash從數(shù)組上找到的節(jié)點，index p節(jié)點在數(shù)組上的位置 ? ? ? ? ? ? ? ? ? ? ?
? ? Node<K,V>[] tab; Node<K,V> p; int n, index;
? ? // 當數(shù)組存在且數(shù)組容量大于0，且p節(jié)點存在
? ? if ((tab = table) != null && (n = tab.length) > 0 &&
? ? ? ? (p = tab[index = (n - 1) & hash]) != null) {
? ? ? ? Node<K,V> node = null, e; K k; V v;
? ? ? ? // 當 p 的 hash 等于參數(shù) hash，且 p 的 key 等于參數(shù) key
? ? ? ? // p節(jié)點就是當前要刪除的節(jié)點，將node指向p
? ? ? ? if (p.hash == hash &&
? ? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k))))
? ? ? ? ? ? node = p;
? ? ? ? // 當p節(jié)點不是要刪除的節(jié)點時，說明p節(jié)點上有紅黑樹或者鏈表
? ? ? ? else if ((e = p.next) != null) {
? ? ? ? ?? ?// p如果是紅黑樹,通過getTreeNode()查找節(jié)點
? ? ? ? ? ? if (p instanceof TreeNode)
? ? ? ? ? ? ? ? node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
? ? ? ? ? ? // p是鏈表，循環(huán)鏈表查詢節(jié)點
? ? ? ? ? ? else {
? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ? ? ((k = e.key) == key ||
? ? ? ? ? ? ? ? ? ? ? ? ?(key != null && key.equals(k)))) {
? ? ? ? ? ? ? ? ? ? ? ? node = e;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? p = e;
? ? ? ? ? ? ? ? } while ((e = e.next) != null);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // ------------------2. 刪除查找到的節(jié)點------------------
? ? ? ? // 如果查找到的node存在且machValue為false或v等于value
? ? ? ? if (node != null && (!matchValue || (v = node.value) == value ||
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(value != null && value.equals(v)))) {
? ? ? ? ? ? // 如果node是TreeNode則使用removeTreeNode刪除節(jié)點
? ? ? ? ? ? if (node instanceof TreeNode)
? ? ? ? ? ? ? ? ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
? ? ? ? ? ? // 如果node等于p，說明移除鏈表頭，將node的后節(jié)點放到數(shù)組上 ?
? ? ? ? ? ? else if (node == p)
? ? ? ? ? ? ? ? tab[index] = node.next;
? ? ? ? ? ? // 說明移除的不是鏈表頭，根據(jù)上方的循環(huán)可得，node是p的后節(jié)點，將p的后節(jié)點指向node的后節(jié)點
? ? ? ? ? ? else
? ? ? ? ? ? ? ? p.next = node.next;
? ? ? ? ? ? // 增加修改次數(shù)，減少當前數(shù)組長度
? ? ? ? ? ? ++modCount;
? ? ? ? ? ? --size;
? ? ? ? ? ? afterNodeRemoval(node);
? ? ? ? ? ? return node;
? ? ? ? }
? ? }
? ? return null;
}

HashMap 的 treeifyBin() 方法

當桶中鏈表長度超過 TREEIFY_THRESHOLD（默認為 8）時，就會調(diào)用 treeifyBin() 方法進行樹化操作。

但此時并不一定會樹化，因為在 treeifyBin()方法中還會判斷 HashMap 的數(shù)組容量是否大于等于 64。

如果容量大于等于 64，那么進行樹化，否則優(yōu)先進行擴容

final void treeifyBin(Node<K,V>[] tab, int hash) {
?
? ? int n, index; Node<K,V> e;
? ? /*
? ? ?* 如果元素數(shù)組為空 或者 數(shù)組長度小于 樹結(jié)構(gòu)化的最小限制
? ? ?* MIN_TREEIFY_CAPACITY 默認值64，對于這個值可以理解為：如果元素數(shù)組長度小于這個值，沒有必要去進行結(jié)構(gòu)轉(zhuǎn)換
? ? ?* 當一個數(shù)組位置上集中了多個鍵值對，那是因為這些key的hash值和數(shù)組長度取模之后結(jié)果相同。（并不是因為這些key的hash值相同）
? ? ?* 因為hash值相同的概率不高，所以可以通過擴容的方式，來使得最終這些key的hash值在和新的數(shù)組長度取模之后，拆分到多個數(shù)組位置上。
? ? ?*/
? ? if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
? ? ? ? resize(); // 擴容
?
? ? // 如果元素數(shù)組長度已經(jīng)大于等于了 MIN_TREEIFY_CAPACITY，那么就有必要進行結(jié)構(gòu)轉(zhuǎn)換了
? ? // 根據(jù)hash值和數(shù)組長度進行取模運算后，得到鏈表的首節(jié)點
? ? else if ((e = tab[index = (n - 1) & hash]) != null) {?
? ? ? ? TreeNode<K,V> hd = null, tl = null; // 定義首、尾節(jié)點
? ? ? ? do {?
? ? ? ? ? ? TreeNode<K,V> p = replacementTreeNode(e, null); // 將該節(jié)點轉(zhuǎn)換為 樹節(jié)點
? ? ? ? ? ? if (tl == null) // 如果尾節(jié)點為空，說明還沒有根節(jié)點
? ? ? ? ? ? ? ? hd = p; // 首節(jié)點（根節(jié)點）指向 當前節(jié)點
? ? ? ? ? ? else { // 尾節(jié)點不為空，以下兩行是一個雙向鏈表結(jié)構(gòu)
? ? ? ? ? ? ? ? p.prev = tl; // 當前樹節(jié)點的 前一個節(jié)點指向 尾節(jié)點
? ? ? ? ? ? ? ? tl.next = p; // 尾節(jié)點的 后一個節(jié)點指向 當前節(jié)點
? ? ? ? ? ? }
? ? ? ? ? ? tl = p; // 把當前節(jié)點設(shè)為尾節(jié)點
? ? ? ? } while ((e = e.next) != null); // 繼續(xù)遍歷鏈表
?
? ? ? ? // 到目前為止 也只是把Node對象轉(zhuǎn)換成了TreeNode對象，把單向鏈表轉(zhuǎn)換成了雙向鏈表
?
? ? ? ? // 把轉(zhuǎn)換后的雙向鏈表，替換原來位置上的單向鏈表
? ? ? ? if ((tab[index] = hd) != null)
? ? ? ? ? ? hd.treeify(tab);//此處單獨解析
? ? }
}

如果 tab 數(shù)組為 null或 tab 的數(shù)組長度 < 64 時，調(diào)用 resize() 方法
否則，會將鏈表轉(zhuǎn)換為紅黑樹（是為了提高查詢性能，元素越多，鏈表的查詢性能越差）
說明了鏈表轉(zhuǎn)換為紅黑樹的條件：當鏈表長度大于閾值 8 時，并且數(shù)組的長度大于 64 時，此時此索引位置上的所有數(shù)據(jù)改為使用紅黑樹存儲

HashMap 如何解決 Hash 沖突

hash 沖突：在 put 多個元素時，通過 key 的 hashCode() 方法計算出的值是一樣的，是同一個存儲地址。當后面的元素要插入到這個地址時，發(fā)現(xiàn)已經(jīng)被占用了，這時候就產(chǎn)生了 hash 沖突。當發(fā)生 hash 沖突時，會進行如下操作

put 的 key == 已存在的 key 的判斷
put 的 key equals() 已存在的 key 的判斷（注意 HashMap 中并沒有重寫 equals() 方法，這里的 equals() 方法仍然是 Object 類的方法）
這里也體現(xiàn)了 == 與 equals() 方法的判斷區(qū)別

當上述條件判斷，只要有一個返回 false 時，也就是說需要put 的 key 與已存在的 key 是不相同的，則 HashMap 會使用單鏈表在已有數(shù)據(jù)的后面（單鏈表中）插入新數(shù)據(jù)，訪問的數(shù)組下標元素作為鏈表的頭部。這種解決 Hash 沖突的方法被稱為拉鏈法

在這里插入圖片描述

HashMap 存入和取出數(shù)據(jù)順序不一致

HashMap 遍歷時，取得數(shù)據(jù)的順序是完全隨機的，這樣會導致按照順序讀取的時候和存入的順序是不一樣的

public class MapTest {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("2020-10-1", "李軍");
        map.put("2020-10-3", "李華");
        map.put("2020-11-1", "李剛");
        map.put("2020-10-9", "李奎");
        for (String key : map.keySet()) {
            System.out.println(key + ":" + map.get(key));
        }
    }
}
結(jié)果：
2020-10-3 : 李華
2020-11-1 : 李剛
2020-10-1 : 李軍
2020-10-9 : 李奎

解決辦法

使用 LinkedHashMap
使用 TreeMap：它在內(nèi)部會對 Key 進行排序
通過有序的 Key 獲取相應(yīng)的數(shù)據(jù)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章:

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

Map集合之HashMap的使用及說明

目錄

HashMap 概述

jdk 1.8 之前與之后的 HashMap

HashMap 的數(shù)組，鏈表，紅黑樹之間的轉(zhuǎn)換

HashMap 擴容機制

HashMap 源碼

HashMap 的基本屬性

HashMap 中涉及到的數(shù)據(jù)結(jié)構(gòu)

HashMap 的 put() 方法

HashMap 的 get() 方法

HashMap 的 remove 方法

HashMap 的 treeifyBin() 方法

HashMap 如何解決 Hash 沖突

HashMap 存入和取出數(shù)據(jù)順序不一致

解決辦法

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线 免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

Map集合之HashMap的使用及說明

目錄

HashMap 概述

jdk 1.8 之前與之后的 HashMap

HashMap 的數(shù)組，鏈表，紅黑樹之間的轉(zhuǎn)換

HashMap 擴容機制

HashMap 源碼

HashMap 的基本屬性

HashMap 中涉及到的數(shù)據(jù)結(jié)構(gòu)

HashMap 的 put() 方法

HashMap 的 get() 方法

HashMap 的 remove 方法

HashMap 的 treeifyBin() 方法

HashMap 如何解決 Hash 沖突

HashMap 存入和取出數(shù)據(jù)順序不一致

解決辦法

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具

国产无遮挡裸体免费直播视频,久久精品国产蜜臀av,动漫在线视频一区二区,欧亚日韩一区二区三区,久艹在线免费视频,国产精品美女网站免费,正在播放 97超级视频在线观看,斗破苍穹年番在线观看免费,51最新乱码中文字幕

HashMap 的數(shù)組，鏈表，紅黑樹之間的轉(zhuǎn)換