更新時間:2022-08-24 來源:黑馬程序員 瀏覽量:
一、前言:
面試過的人都知道,HashMap是Java程序員在面試中最最最經(jīng)常被問到的一個點,可以說,不了解HashMap都不好意思說自己是做Java開發(fā)的?;旧夏闳ッ嬖囀夜?,有七八家都會問到你HashMap。那么今天,就帶著大家從源碼的角度去分析一下,HashMap具體是怎么實現(xiàn)的。
二、HashMap的構造方法
1.HashMap構造方法
我們先來看HashMap的四個構造方法
```java //initialCapacity給定的初始化容量,loadFactor擴容因子 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); } public HashMap(int initialCapacity) { //內(nèi)部調(diào)用了上邊的構造方法 this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() {//空參構造 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) {//構造傳入一個map,將map中的值放到hashmap中 this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } ```
2.構造方法里的putMapEntries方法
剛才構造方法中提到了putMapEntries這個方法,接下來就讓我們一起看一下
//該函數(shù)用于將一個map賦值給新的HashMap final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //定義變量接收舊hashmap的size int s = m.size(); //判斷s的容量是否大于0 if (s > 0) { //判斷當前數(shù)組有沒有初始化 if (table == null) { // pre-size ////求出以 舊hashmap數(shù)組容量為閾值 的數(shù)組容量賦值給ft float ft = ((float)s / loadFactor) + 1.0F; //判斷是不是大于最大容量,如果是,賦值為最大容量,否則將ft賦值給t int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //判斷t是否大于threshold(數(shù)組擴容閾值) if (t > threshold) //通過tablesizefor方法求出大于等于t的最小2的次冪值賦值給threshold(數(shù)組擴容閾值) threshold = tableSizeFor(t); } //如果數(shù)組長度大于擴容閾值,進行resize擴容操作 else if (s > threshold) resize(); //循環(huán)遍歷取出舊hashmap的值放入當前hashmap for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } /* if (table == null)分支,是判斷當前數(shù)組是否初始化,因為在jdk1.8之后,只有當你第一次放值時,才會幫你創(chuàng)建16位的數(shù)組。 float ft = ((float)s / loadFactor) + 1.0F經(jīng)過除運算再加上1.0F是為了向上取整 if (t > threshold)注意一個細節(jié),做判斷的的時候,數(shù)組還沒有初始化,這里的threshold的值還是給定的數(shù)組長度的值,也就是capacity的值 else if (s > threshold)說明傳入的map集合大于當前的擴容閾值,需要進行resize擴容操作 */ ```
tableSizeFor方法
剛才putMapEntries方法中,調(diào)用了tableSizeFor方法,接下來我們看一下這個tableSizeFor方法。
作用:創(chuàng)建hashMap對象時調(diào)用有參構造,傳入初始容量,需要保證hashMap的初始長度為2的n次冪。
tableSizeFor方法用來計算大于等于并離傳入值最近的2的n次冪的數(shù)值,比如傳入15,算出結果為16,傳入17,算出結果為32。
通過二進制的位移,第一次右移一位,第二次右移兩位,第三次右移四位。。。通過五次位移,將范圍內(nèi)所有的位數(shù)都變?yōu)?,高位補0,最后得出來的結果再加上1,最后算出來的結果一定是2的n次冪。
//這個方法的作用是找到大于等于給定容量的最小2的次冪值 //>>>表示無符號右移,也叫邏輯右移,即若該數(shù)為正,則高位補0,而若該數(shù)為負數(shù),則右移后高位同樣補0 7--》8 16--》16 static final int tableSizeFor(int cap) { //先將數(shù)組長度減1,之所以在開始移位前先將容量-1,是為了避免給定容量已經(jīng)是8,16這樣2的冪時,不減一 直接移位會導致得到的結果比預期大。比如預期16得到應該是16,直接移位的話會得到32。 int n = cap - 1; //右移一位,在進行或運算,這個時候最高位和次高位就已經(jīng)都是1,此時是2個1 n |= n >>> 1; //右移兩位,在進行或運算,這個時候由上次運算得出的兩個1,變成了四個1 n |= n >>> 2; //右移四位 n |= n >>> 4; //右移八位 n |= n >>> 8; //右移十六位,這個時候所有的位數(shù)都變?yōu)榱? n |= n >>> 16; //n+1操作,是為了進1,這個時候算出來的數(shù)值就一點是 2的n次冪 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } ```
移位的思想
2的整數(shù)冪用二進制表示都是最高有效位為1,其余全是0。
對任意十進制數(shù)轉換為2的整數(shù)冪,結果是這個數(shù)本身的最高有效位的前一位變成1,最高有效位以及其后的位都變?yōu)?。
核心思想是,先將最高有效位以及其后的位都變?yōu)?,最后再+1,就進位到前一位變成1,其后所有的滿2變0。所以關鍵是如何將最高有效位后面都變?yōu)?。
先移位,再或運算。
> 右移一位,再或運算,就有兩位變?yōu)?;
>
> 右移兩位,再或運算,就有四位變?yōu)?,,,
>
> 最后右移16位再或運算,保證32位的int類型整數(shù)最高有效位之后的位都能變?yōu)?。
三、HashMap的底層原理
先來看幾個重要的參數(shù):
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認數(shù)組初始容量 static final int MAXIMUM_CAPACITY = 1 << 30;//數(shù)組最大容量 static final float DEFAULT_LOAD_FACTOR = 0.75f;//默認加載因子 static final int TREEIFY_THRESHOLD = 8;//樹化的閾值 static final int UNTREEIFY_THRESHOLD = 6;//由樹退化到鏈表的閾值 static final int MIN_TREEIFY_CAPACITY = 64;//樹化最小數(shù)組容量 //node節(jié)點,繼承了Map.entry,在Entry原有的K,V的基礎上追加了hash和next字段 //分別表示key的hash值和下一個節(jié)點 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; } //重寫了計算hash的方法 //將 Hash 值的高 16 位右移并與原 Hash 值取異或運算(^),混合高 16 位和低 16 位的值 //得到一個更加散列的低 16 位的 Hash 值。 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } ```
HashMap在JDK1.8之前的實現(xiàn)方式數(shù)組+鏈表,
但是在JDK1.8后對HashMap進行了底層優(yōu)化,改為了由 **數(shù)組+鏈表或者數(shù)值+紅黑樹**實現(xiàn),主要的目的是提高查找效率
1. Jdk8數(shù)組+鏈表或者數(shù)組+紅黑樹實現(xiàn),當鏈表中的元素大于等于8 個并且數(shù)組長度大于等于64以后, 會將鏈表轉換為紅黑樹,當紅黑樹節(jié)點 小于 等于6 時又會退化為鏈表。
2. 當new HashMap()時,底層沒有創(chuàng)建數(shù)組,首次調(diào)用put()方法示時,會調(diào)用resize方法,底層創(chuàng)建長度為16的數(shù)組,jdk8底層的數(shù)組是:Node[],而非Entry[],用數(shù)組容量大小乘以加載因子得到一個值,一旦數(shù)組中存儲的元素個數(shù)超過該值就會調(diào)用resize方法將數(shù)組擴容到原來的兩倍,在做擴容的時候會生成一個新的數(shù)組,原來的所有數(shù)據(jù)需要重新計算哈希碼值重新分配到新的數(shù)組,所以擴容的操作非常消耗性能。
默認的負載因子大小為0.75,數(shù)組大小為16。也就是說,默認情況下,那么當HashMap中元素個數(shù)超過16*0.75=12的時候,就把數(shù)組的大小擴展為2*16=32,即擴大一倍。
3. 在我們Java中任何對象都有hashcode,hash算法就是通過hashcode與自己進行向右位移16的異或運算。這樣做是為了使高位的16位hash也能參與運算,使運算出來的hash值足夠隨機,足夠分散,還有產(chǎn)生的數(shù)組下標足夠隨機。
map.put(k,v)實現(xiàn)原理:
(1)首先將k,v封裝到Node對象當中(節(jié)點)。
(2)先調(diào)用k的hashCode()方法得出哈希值,并通過哈希算法轉換成數(shù)組的下標。
(3)下標位置上如果沒有任何元素,就把Node添加到這個位置上。如果說下標對應的位置上有鏈表。此時,就會拿著k和鏈表上每個節(jié)點的k進行equal。如果所有的equals方法返回都是false,那么這個新的節(jié)點將被添加到鏈表的末尾。如其中有一個equals返回了true,那么這個節(jié)點的value將會被覆蓋。
HashMap中的put()方法
```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } ```
putVal()方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //判斷數(shù)組是否未初始化 if ((tab = table) == null || (n = tab.length) == 0) //如果未初始化,調(diào)用resize方法 進行初始化 n = (tab = resize()).length; //通過 & 運算求出該數(shù)據(jù)(key)的數(shù)組下標并判斷該下標位置是否有數(shù)據(jù) if ((p = tab[i = (n - 1) & hash]) == null) //如果沒有,直接將數(shù)據(jù)放在該下標位置 tab[i] = newNode(hash, key, value, null); //該數(shù)組下標有數(shù)據(jù)的情況 else { Node<K,V> e; K k; //判斷該位置數(shù)據(jù)的key和新來的數(shù)據(jù)是否一樣 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果一樣,證明為修改操作,該節(jié)點的數(shù)據(jù)賦值給e,后邊會用到 e = p; //判斷是不是紅黑樹 else if (p instanceof TreeNode) //如果是紅黑樹的話,進行紅黑樹的操作 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //新數(shù)據(jù)和當前數(shù)組既不相同,也不是紅黑樹節(jié)點,證明是鏈表 else { //遍歷鏈表 for (int binCount = 0; ; ++binCount) { //判斷next節(jié)點,如果為空的話,證明遍歷到鏈表尾部了 if ((e = p.next) == null) { //把新值放入鏈表尾部 p.next = newNode(hash, key, value, null); //因為新插入了一條數(shù)據(jù),所以判斷鏈表長度是不是大于等于8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果是,進行轉換紅黑樹操作 treeifyBin(tab, hash); break; } //判斷鏈表當中有數(shù)據(jù)相同的值,如果一樣,證明為修改操作 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //把下一個節(jié)點賦值為當前節(jié)點 p = e; } } //判斷e是否為空(e值為修改操作存放原數(shù)據(jù)的變量) if (e != null) { // existing mapping for key //不為空的話證明是修改操作,取出老值 V oldValue = e.value; //一定會執(zhí)行 onlyIfAbsent傳進來的是false if (!onlyIfAbsent || oldValue == null) //將新值賦值當前節(jié)點 e.value = value; afterNodeAccess(e); //返回老值 return oldValue; } } //計數(shù)器,計算當前節(jié)點的修改次數(shù) ++modCount; //當前數(shù)組中的數(shù)據(jù)數(shù)量如果大于擴容閾值 if (++size > threshold) //進行擴容操作 resize(); //空方法 afterNodeInsertion(evict); //添加操作時 返回空值 return null; } ```
map中resize方法
//擴容、初始化數(shù)組 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //如果當前數(shù)組為null的時候,把oldCap老數(shù)組容量設置為0 int oldCap = (oldTab == null) ? 0 : oldTab.length; //老的擴容閾值 int oldThr = threshold; int newCap, newThr = 0; //判斷數(shù)組容量是否大于0,大于0說明數(shù)組已經(jīng)初始化 if (oldCap > 0) { //判斷當前數(shù)組長度是否大于最大數(shù)組長度 if (oldCap >= MAXIMUM_CAPACITY) { //如果是,將擴容閾值直接設置為int類型的最大數(shù)值并直接返回 threshold = Integer.MAX_VALUE; return oldTab; } //如果在最大長度范圍內(nèi),則需要擴容 OldCap << 1等價于oldCap*2 //運算過后判斷是不是最大值并且oldCap需要大于16 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold 等價于oldThr*2 } //如果oldCap<0,但是已經(jīng)初始化了,像把元素刪除完之后的情況,那么它的臨界值肯定還存在, 如果是首次初始化,它的臨界值則為0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //數(shù)組未初始化的情況,將閾值和擴容因子都設置為默認值 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //初始化容量小于16的時候,擴容閾值是沒有賦值的 if (newThr == 0) { //創(chuàng)建閾值 float ft = (float)newCap * loadFactor; //判斷新容量和新閾值是否大于最大容量 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //計算出來的閾值賦值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //根據(jù)上邊計算得出的容量 創(chuàng)建新的數(shù)組 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //賦值 table = newTab; //擴容操作,判斷不為空證明不是初始化數(shù)組 if (oldTab != null) { //遍歷數(shù)組 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //判斷當前下標為j的數(shù)組如果不為空的話賦值個e,進行下一步操作 if ((e = oldTab[j]) != null) { //將數(shù)組位置置空 oldTab[j] = null; //判斷是否有下個節(jié)點 if (e.next == null) //如果沒有,就重新計算在新數(shù)組中的下標并放進去 newTab[e.hash & (newCap - 1)] = e; //有下個節(jié)點的情況,并且判斷是否已經(jīng)樹化 else if (e instanceof TreeNode) //進行紅黑樹的操作 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //有下個節(jié)點的情況,并且沒有樹化(鏈表形式) else { //比如老數(shù)組容量是16,那下標就為0-15 //擴容操作*2,容量就變?yōu)?2,下標為0-31 //低位:0-15,高位16-31 //定義了四個變量 // 低位頭 低位尾 Node<K,V> loHead = null, loTail = null; // 高位頭 高位尾 Node<K,V> hiHead = null, hiTail = null; //下個節(jié)點 Node<K,V> next; //循環(huán)遍歷 do { //取出next節(jié)點 next = e.next; //通過 與操作 計算得出結果為0 if ((e.hash & oldCap) == 0) { //如果低位尾為null,證明當前數(shù)組位置為空,沒有任何數(shù)據(jù) if (loTail == null) //將e值放入低位頭 loHead = e; //低位尾不為null,證明已經(jīng)有數(shù)據(jù)了 else //將數(shù)據(jù)放入next節(jié)點 loTail.next = e; //記錄低位尾數(shù)據(jù) loTail = e; } //通過 與操作 計算得出結果不為0 else { //如果高位尾為null,證明當前數(shù)組位置為空,沒有任何數(shù)據(jù) if (hiTail == null) //將e值放入高位頭 hiHead = e; //高位尾不為null,證明已經(jīng)有數(shù)據(jù)了 else //將數(shù)據(jù)放入next節(jié)點 hiTail.next = e; //記錄高位尾數(shù)據(jù) hiTail = e; } //如果e不為空,證明沒有到鏈表尾部,繼續(xù)執(zhí)行循環(huán) } while ((e = next) != null); //低位尾如果記錄的有數(shù)據(jù),是鏈表 if (loTail != null) { //將下一個元素置空 loTail.next = null; //將低位頭放入新數(shù)組的原下標位置 newTab[j] = loHead; } //高位尾如果記錄的有數(shù)據(jù),是鏈表 if (hiTail != null) { //將下一個元素置空 hiTail.next = null; //將高位頭放入新數(shù)組的(原下標+原數(shù)組容量)位置 newTab[j + oldCap] = hiHead; } } } } } //返回新的數(shù)組對象 return newTab; } ```
map.get(k)實現(xiàn)原理
(1)、先調(diào)用k的hashCode()方法得出哈希值,并通過哈希算法轉換成數(shù)組的下標。
(2)、在通過數(shù)組下標快速定位到某個位置上。重點理解如果這個位置上什么都沒有,則返回null。如果這個位置上有單向鏈表,那么它就會拿著參數(shù)K和單向鏈表上的每一個節(jié)點的K進行equals,如果所有equals方法都返回false,則get方法返回null。如果其中一個節(jié)點的K和參數(shù)K進行equals返回true,那么此時該節(jié)點的value就是我們要找的value了,get方法最終返回這個要找的value。
HashMap中的get()方法
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } ```
getNode()方法
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //判斷數(shù)組不為null并且長度大于0,并且通過hash算出來的數(shù)組下標的位置不為空,證明有數(shù)據(jù) if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //判斷數(shù)組的位置的key的hash和內(nèi)容是否等同與要查詢的數(shù)據(jù) 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) { //判斷是否為為紅黑樹 if (first instanceof TreeNode) //進行紅黑樹查詢操作 return ((TreeNode<K,V>)first).getTreeNode(hash, key); //鏈表查詢操作 do { //循環(huán)鏈表,逐一判斷 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //發(fā)現(xiàn)key的話就返回 return e; } while ((e = e.next) != null); } } //沒有查詢到返回null return null; }
四、HashMap常見面試題分析
為何HashMap的數(shù)組長度一定是2的次冪?
首先,HashMap的初始化的數(shù)組長度一定是2的n次的,每次擴容仍是原來的2倍的話,就不會破壞這個規(guī)律,每次擴容后,原數(shù)據(jù)都會進行數(shù)據(jù)遷移,根據(jù)二進制的計算,擴容后數(shù)據(jù)要么在原來位置,要么在【原來位置+擴容長度】,這樣就不需要重新hash,效率上更高。
HashMap中,如果想存入數(shù)據(jù),首先它需要根據(jù)key的哈希值去定位落入哪個桶中
HashMap的做法,我總結的是,三步:>>>無符號右移、^異或、&與
具體是:拿著key的哈希值,先“>>>”無符號右移16位,然后“^”異或上key的哈希值,得到一個值,再拿著這個值去“&”上數(shù)組長度減一
最后得出一個數(shù)(如果數(shù)組長度是15的話,那這個數(shù)就是一個0-15之間的一個數(shù)),這個數(shù)就是得出的數(shù)組腳標位置,也就是存入的桶的位置。
由上邊可以知道,定位桶的位置最后需要做一個 “&” 與運算,&完了得出一個數(shù),就是桶的位置
知道了這些以后,再來說為什么HashMap的長度之所以一定是2的次冪?
至少有以下**兩個原因**:
1、HashMap的長度是2的次冪的話,可以讓**數(shù)據(jù)更散列更均勻的分布**,更充分的利用數(shù)組的空間
怎么理解呢?下面舉例子說一下如果不是2的次冪的數(shù)的話假設數(shù)組長度是一個奇數(shù),那參與最后的&運算的肯定就是偶數(shù),那偶數(shù)的話,它二進制的最后一個低位肯定是0,0做完&運算得到的肯定也是0,那意味著&完后得到的數(shù)的最低位一定是0最低位一定是0的話,那說明一定是一個偶數(shù),換句話說就是:&完得到的數(shù)一定是一個偶數(shù),所以&完獲取到的腳標永遠是偶數(shù)位,那意味著奇數(shù)位的腳標永遠都沒值,**有一半的空間是浪費的**奇數(shù)說完了,來說一下偶數(shù),假設數(shù)組長度是一個偶數(shù),比如6,那參與&運算的就是55的二進制 00000000 00000000 00000000 00000101發(fā)現(xiàn)任何一個數(shù)&上5,倒數(shù)第二低位永遠是0,那就意味著&完以后,最起碼肯定得不出2或者3(這點剛開始不好理解,但是好好想一下就能明白)意味著第二和第三腳標位肯定不會有值。
雖然偶數(shù)的話,不會像奇數(shù)那么夸張會有一半的腳標位得不到,但是也總會有一些腳標位得不到的。**所以不是2的次冪的話,不管是奇數(shù)還是偶數(shù),就肯定注定了某些腳標位永遠是沒有值的,而某些腳標位永遠是沒有值的,就意味著浪費空間,會讓數(shù)據(jù)散列的不充分,這對HashMap來說絕對是個災難!**
2、HashMap的長度一定是2的次冪,還有另外一個原因,那就是在擴容遷移的時候不需要再重新通過哈希定位新的位置了。擴容后,元素新的位置,要么在原腳標位,要么在原腳標位+擴容長度這么一個位置。
比如擴容前長度是8,擴容后長度是16 第一種情況: 擴容前: 00000000 00000000 00000000 00000101 &00000000 00000000 00000000 00000111 8-1=7 ------------------------------------- 101 ===== 5 原來腳標位是5 擴容后: 00000000 00000000 00000000 00000101 &00000000 00000000 00000000 00001111 16-1=15 ------------------------------------- 101 ===== 5 擴容后腳標位是5(原腳標位) 第二種情況: 擴容前: 00000000 00000000 00000000 00001101 &00000000 00000000 00000000 00000111 8-1=7 ------------------------------------- 101 ===== 5 原來腳標位是5 擴容后: 00000000 00000000 00000000 00001101 &00000000 00000000 00000000 00001111 16-1=15 ------------------------------------- 1101 ===== 13 擴容后腳標位是13(原腳標位+擴容長度) ```
擴容后到底是在原來位置還是在原腳標位+擴容長度的位置,主要是看新擴容最左邊一個1對應的上方數(shù)字是0還是1如果是0則擴容后在原來位置,如果是1則擴容后在原腳標位+擴容長度的位置HashMap源碼里擴容也是這么做的。
總結來說,就是hash&(n-1)這個計算有關。如果不為n不為2的n次方的話,那轉換為二進制情況下,n-1就會有某一位為0,那與hash做了&運算后,該位置永遠為0,那么計算出來的數(shù)組位置就永遠會有某個下標的數(shù)組位置是空的,也就是這個位置永遠不會有值。
JDK1.8中HashMap的性能優(yōu)化
JDK1.8在1.7的基礎上對一些操作進行了優(yōu)化。
| 不同 | JDK1.7 | JDK1.8 |
| ------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |
| 存儲結構 | 數(shù)組+鏈表 | 數(shù)組+鏈表+紅黑樹 |
| 初始化方式 | 單獨函數(shù)inflateTable() | 集成至擴容方法resize() |
| hash值計算方式 | 擾動處理=9次擾動=4次位運算+5次異或運算 | 擾動處理=2次擾動=1次位運算+1次異或運算 |
| 存放數(shù)據(jù)規(guī)則 | 無沖突時,存放數(shù)組;沖突時存放鏈表 | 無沖突時,存放數(shù)組;沖突&鏈表長度<8:c存放單鏈表;沖突&鏈表長度 >8:樹化并存放紅黑樹 |
| 插入數(shù)據(jù)方式 | 頭插法(將原位置的數(shù)據(jù)移動到后一位,再插入數(shù)據(jù)到該位置) | 尾插法 (直接插入鏈表尾部/紅黑樹) |
| 擴容后存儲位置的計算方式 | 全部按照原來的方法進行運算(hashCode()->>擾動函數(shù)->>(h&length-1)) | 按照擴容后的規(guī)則計算(即擴容后位置=原位置或原位置+舊容量) |
注意:JDK1.8里轉換為紅黑樹的時候,數(shù)組長度必須大于64,如果數(shù)組長度小于64,鏈表長度達到8的話,會進行resize擴容操作。
五、總結
看到這里,我們已經(jīng)HashMap的源碼和實現(xiàn)有了清晰的理解,并且對它的構造方法再到它的一個put數(shù)據(jù)和get數(shù)據(jù)的一個源碼解析,還有一些它里邊比較精妙和重要的一些方法也都探索清楚了,希望這些知識點可以在大家以后的面試中也能夠幫助到大家,斬獲一個心儀的offer。