當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

2020.10.28----HashMap

發布時間：2023/12/15 编程问答 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 2020.10.28----HashMap 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

基本概念

//默認容量 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//左移4位 //加載因子 0.75f static final float DEFAULT_LOAD_FACTOR = 0.75f;

加載因子0.75的意思是這個表超過75%容量的時候，就會擴容。0.75是一個經過大量實驗測算得出的比較好的值，不要問為什么不是0.6或者0.8什么的…
HashMap的底層jdk1.8后是“數組+鏈表+紅黑樹”，之前是“數組+鏈表。說白了就是默認長度為16的數組，每個元素存儲的是一個鏈表或者是紅黑樹的頭結點。
哈希碰撞指的是key不同，但是計算的hash值相同或者在數組中的索引值相同了。HashMap來解決這個問題就是用了鏈表。當碰撞很多時，HashMap就退化成了一個鏈表，查詢時間0(n)。在jdk1.8開始呢增加了紅黑樹（查詢時間O（logn））這種數據結構，在碰撞結點較少時，就采用鏈表，當碰撞結點較多時，就轉為紅黑樹。
HashMap是線程不安全的。HashTable是線程安全的，因為添加了synchronized關鍵字來確保線程同步。

源碼分析

構造方法

public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity); }//會根據傳入的cap值計算一個數組大小，這個方法得到的一定是一個2的幾次方的值 //也就是說數組的長度一定是2的N次方，這么設計主要是為了較少哈希碰撞的產生 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; }

hash值的計算

//計算hash值：將hashCode與hashCode的高16位異或運算 //為什么要用高16位來運行，其實也是為了減少哈希碰撞 static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }//計算在數組中的索引 (n - 1) & hash

put操作

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) {Node<K,V>[] tab; Node<K,V> p; int n, i;//數組為空則初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//計算索引，取該索引保存的節點賦值給pif ((p = tab[i = (n - 1) & hash]) == null)//該位置沒有節點則新建節點放在該位置tab[i] = newNode(hash, key, value, null);else {//該位置已經有節點了Node<K,V> e; K k;//如果hash值和key都相同if (p.hash == hash &&((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 {//頭結點如果是鏈表for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//校驗節點數是否超過8個，如果超過則調用treeifyBin方法將鏈表節點轉為紅黑樹節點if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//找到hash值并且key相同的節點if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//覆蓋if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//擴容if (++size > threshold)resize();afterNodeInsertion(evict);return null; }

get

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;if ((e = first.next) != null) {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; }

擴容

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//舊表長度int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {//舊表不為空if (oldCap >= MAXIMUM_CAPACITY) {//舊表超過最大容量，將閾值改為Integer最大值，結束threshold = Integer.MAX_VALUE;return oldTab;}//得到新表長度為舊表*2//如果新表長度在最大最小容量之間，則新閾值為舊閾值*2else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//舊表長度為0，但是閾值大于0else if (oldThr > 0) newCap = oldThr;else {//舊表長度為0，但是閾值為0newCap = DEFAULT_INITIAL_CAPACITY;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"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;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)//該索引位置只有1個節點，則直接放入新表newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)//如果是紅黑樹節點，則進行紅黑樹的重hash分布((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { //是鏈表//這里定義兩個鏈表節點Node<K,V> loHead = null, loTail = null;//新舊表索引位置一樣Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;//新舊表位置不一樣do {next = e.next;//如果擴容后索引位置與舊表一致if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//該節點在新表的位置發生了變化：舊表的索引位置＋oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.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; }

那么我們肯定想知道HashMap是什么時候擴容的？

1.數組空的時候后會擴容 2.當HashMap中元素總個數（不是數組元素個數）達到閾值時就會擴容。 if (++size > threshold)resize(); afterNodeInsertion(evict); return null;3.鏈表轉紅黑樹的時候，如果數組長度小于64，則會擴容 final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;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 {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);} }

那么為什么要擴容？

1. HashMap中元素個數實在太多了，已經很頻繁的發生hash沖突，不得不進行擴容來減少這個沖突，來增強效率。 2. 可能元素都集中在某幾個位置造成了分布不均勻，數組空間浪費，效率低。

補充ConcurrentHashMap

jdk1.8之后，ConcurrentHashMap的底層也是數組+鏈表+紅黑樹。我們知道HashMap是線程不安全的，而HashTable只是簡單的在方法上加鎖實現線程安全，效率低下，所以在線程安全的環境下我們通常會使用ConcurrentHashMap。這里我們主要想看下為什么ConcurrentHashMap是線程安全的。

先看下初始化數組的操作

CAS是樂觀鎖技術，當多個線程嘗試使用CAS同時更新同一個變量時，只有其中一個線程能更新變量的值，，失敗的線程并不會被掛起，而是被告知這次競爭中失敗，并可以再次嘗試。 private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;//如果數組為空，就一直循環試圖去初始化while ((tab = table) == null || tab.length == 0) {if ((sc = sizeCtl) < 0)//sizeCtl小于0說明有其他線程正在初始化Thread.yield();//將當前線程掛起，讓出CPU時間//sizeCtl不小于0，說明沒有其他線程在初始化數組//將sizeCtl修改為-1，表示該線程正在初始化數組else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {//再次判斷數組是否被初始化if ((tab = table) == null || tab.length == 0) {//因為sc為0，所以n就是DEFAULT_CAPACITY也就是16int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//初始化數組，長度為16@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;sc = n - (n >>> 2);}} finally {sizeCtl = sc;}break;}}return tab; }

計算hash值

static final int spread(int h) {//將hashCode的高16位和低16位異或運算//再和0x7fffffff相與運算是為了得到正數return (h ^ (h >>> 16)) & HASH_BITS; }//計算索引 (n - 1) & hash)

put操作

final V putVal(K key, V value, boolean onlyIfAbsent) {//不允許key或者value為nullif (key == null || value == null) throw new NullPointerException();//計算hash值 int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)tab = initTable();//初始化數組else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果該位置沒有節點if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break; }//如果正在擴容else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {V oldVal = null;synchronized (f) {if (tabAt(tab, i) == f) {if (fh >= 0) {//表示是鏈表binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}Node<K,V> pred = e;//尾插法if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}//如果紅黑樹else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2;if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}else if (f instanceof ReservationNode)throw new IllegalStateException("Recursive update");}}if (binCount != 0) {//鏈表轉紅黑樹if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);return null; } put操作如何保證線程安全的呢？ 1.table變量加了volatile保證其引用的可見性，并不能確保其數組中的對象是否是最新的。 2.將 Node 鏈表的頭節點作為鎖 3.使用Unsafe的getObjectVolatile方法取值

移除

public V remove(Object key) {return replaceNode(key, null, null); }final V replaceNode(Object key, V value, Object cv) {int hash = spread(key.hashCode());for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;//數組為空或者沒有找到該key對應的元素if (tab == null || (n = tab.length) == 0 ||(f = tabAt(tab, i = (n - 1) & hash)) == null)break;//正在擴容else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {V oldVal = null;boolean validated = false;synchronized (f) {//對f加鎖if (tabAt(tab, i) == f) {if (fh >= 0) {//鏈表validated = true;for (Node<K,V> e = f, pred = null;;) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {V ev = e.val;if (cv == null || cv == ev ||(ev != null && cv.equals(ev))) {oldVal = ev;if (value != null)e.val = value;else if (pred != null)//如果移除的是非頭結點pred.next = e.next;else//如果是移除的就是頭結點setTabAt(tab, i, e.next);}break;}pred = e;if ((e = e.next) == null)break;}}else if (f instanceof TreeBin) {validated = true;TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> r, p;if ((r = t.root) != null &&(p = r.findTreeNode(hash, key, null)) != null) {V pv = p.val;if (cv == null || cv == pv ||(pv != null && cv.equals(pv))) {oldVal = pv;if (value != null)p.val = value;else if (t.removeTreeNode(p))setTabAt(tab, i, untreeify(t.first));}}}else if (f instanceof ReservationNode)throw new IllegalStateException("Recursive update");}}//調用addCount方法，將當前ConcurrentHashMap存儲的鍵值對數量-1if (validated) {if (oldVal != null) {if (value == null)addCount(-1L, -1);return oldVal;}break;}}}return null; }

5.get方法

public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;int h = spread(key.hashCode());if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}else if (eh < 0)return (p = e.find(h, key)) != null ? p.val : null;while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null; } get操作保證線程間的可見性即可

擴容

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;if (tab != null && (f instanceof ForwardingNode) &&(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {int rs = resizeStamp(tab.length);while (nextTab == nextTable && table == tab &&(sc = sizeCtl) < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || transferIndex <= 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {transfer(tab, nextTab);break;}}return nextTab;}return table; }private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)stride = MIN_TRANSFER_STRIDE; // subdivide range//如果nextTab為空則初始化為原tab的兩倍if (nextTab == null) { // initiatingtry {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];nextTab = nt;} catch (Throwable ex) { // try to cope with OOMEsizeCtl = Integer.MAX_VALUE;return;}nextTable = nextTab;transferIndex = n;}//假設為16*2=32int nextn = nextTab.length;//創建一個標記Node對象，hash值為-1ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);boolean advance = true;boolean finishing = false; // to ensure sweep before committing nextTabfor (int i = 0, bound = 0;;) {Node<K,V> f; int fh;while (advance) {int nextIndex, nextBound;if (--i >= bound || finishing)advance = false;else if ((nextIndex = transferIndex) <= 0) {i = -1;advance = false;}else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {bound = nextBound;i = nextIndex - 1;advance = false;}}if (i < 0 || i >= n || i + n >= nextn) {int sc;if (finishing) {nextTable = null;table = nextTab;sizeCtl = (n << 1) - (n >>> 1);return;}if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)return;finishing = advance = true;i = n; // recheck before commit}}//此時i=15，取出Node數組下標為15的那個Node，若為空則直接插入fwdelse if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);else if ((fh = f.hash) == MOVED)advance = true; // already processedelse {//要擴容處理的synchronized (f) {//對f加鎖if (tabAt(tab, i) == f) {Node<K,V> ln, hn;if (fh >= 0) {//此時fh與原來Node數組長度進行與運算int runBit = fh & n;Node<K,V> lastRun = f;for (Node<K,V> p = f.next; p != null; p = p.next) {int b = p.hash & n;if (b != runBit) {runBit = b;lastRun = p;}}//低位Nodeif (runBit == 0) {ln = lastRun;hn = null;}//高位Nodeelse {hn = lastRun;ln = null;}for (Node<K,V> p = f; p != lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;if ((ph & n) == 0)ln = new Node<K,V>(ph, pk, pv, ln);elsehn = new Node<K,V>(ph, pk, pv, hn);}//低位的話位置沒有變化setTabAt(nextTab, i, ln);//高位的話位置發生了變化 i+nsetTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd);advance = true;}else if (f instanceof TreeBin) {TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> lo = null, loTail = null;TreeNode<K,V> hi = null, hiTail = null;int lc = 0, hc = 0;for (Node<K,V> e = t.first; e != null; e = e.next) {int h = e.hash;TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);if ((h & n) == 0) {if ((p.prev = loTail) == null)lo = p;elseloTail.next = p;loTail = p;++lc;}else {if ((p.prev = hiTail) == null)hi = p;elsehiTail.next = p;hiTail = p;++hc;}}ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t;hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t;setTabAt(nextTab, i, ln);setTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd);advance = true;}}}}} } 1. 擴容時假如有個線程在get操作，而且操作的下標一樣呢？會調用ForwardingNode的find方法，會去新的數組中查找。 else if (eh < 0)return (p = e.find(h, key)) != null ? p.val : null;Node<K,V> find(int h, Object k) {// loop to avoid arbitrarily deep recursion on forwarding nodesouter: for (Node<K,V>[] tab = nextTable;;) {Node<K,V> e; int n;if (k == null || tab == null || (n = tab.length) == 0 ||(e = tabAt(tab, (n - 1) & h)) == null)return null;for (;;) {int eh; K ek;if ((eh = e.hash) == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;if (eh < 0) {if (e instanceof ForwardingNode) {tab = ((ForwardingNode<K,V>)e).nextTable;continue outer;}elsereturn e.find(h, k);}if ((e = e.next) == null)return null;}} }2.擴容的時候有個線程在put怎么辦？ else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);3.什么時候會擴容？ put時候如果該位置為ForwardingNode節點會一起擴容；鏈表轉紅黑樹時數組長度小于64的時候會擴容。

總結

以上是生活随笔為你收集整理的2020.10.28----HashMap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

hashmap