Categories
程式開發

了解HashMap數據結構,超詳細!


寫在前面

小伙伴兒們,大家好!今天來學習HashMap相關內容,作為面試必問的知識點,來深入了解一波!

思維導圖:

了解HashMap數據結構,超詳細! 1

學習框架圖

1,HashMap集合簡介

HashMap基於哈希表的Map接口實現,是以key-value存儲形式存在,即主要用來存放鍵值對。 HashMap的實現不是同步的,這意味著它不是線程安全的。它的key、value都可以為null。此外,HashMap中的映射不是有序的。

JDK1.8之前的HashMap由數組+鍊錶組成的,數組是HashMap的主體,鍊錶則是主要為了節解決哈希碰撞(兩個對象調用的hashCode方法計算的哈希碼值一致導致計算的數組索引值相同)而存在的(“拉鍊法”解決衝突)。

JDK1.8之後在解決哈希衝突時有了較大的變化,當鍊錶長度大於閾值(或者紅黑樹的邊界值,默認為8)並且當前數組的長度大於64時,此時此索引位置上的所有數據改為使用紅黑樹存儲。

數組裡面都是key-value的實例,在JDK1.8之前叫做Entry,在JDK1.8之後叫做Node。

了解HashMap數據結構,超詳細! 2

key-value實例

由於它的key、value都為null,所以在插入的時候會根據key的hash去計算一個index索引的值。計算索引的方法如下:

/**
* 根据key求index的过程
* 1,先用key求出hash值
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//2,再用公式index = (n - 1) & hash(n是数组长度)
int hash=hash(key);
index=(n-1)&hash;

這裡的Hash算法本質上就是三步:取key的hashCode值、高位運算、取模運算。

這樣的話比如說put(“A”,王炸),插入了key為”A”的元素,這時候通過上述公式計算出插入的位置index,若index為3則結果如下(即hash(“A” )=3):

了解HashMap數據結構,超詳細! 3

那麼,HashMap中的鍊錶又是乾什麼用的呢?

大家都知道數組的長度是有限的,在有限的長度裡面使用哈希函數計算index的值時,很有可能插入的k值不同,但所產生的hash是相同的(也叫做哈希碰撞),這也就是哈希函數存在一定的概率性。就像上面的K值為A的元素,如果再次插入一個K值為a的元素,很有可能所產生的index值也為3,也就是即hash(“a”)=3;那這就形成了鍊錶,這種解決哈希碰撞的方法也叫做拉鍊法。

了解HashMap數據結構,超詳細! 4

當這個鍊錶長度大於閾值8並且數組長度大於64則進行將鍊錶變為紅黑樹。

補充:

將鍊錶轉換成紅黑樹前會判斷,如果閾值大於8,但是數組長度小64,此時並不會將鍊錶變為紅黑樹。而是選擇進行數組擴容。

這樣做的目的是因為數組比較小,盡量避開紅黑樹結構,這種情況下變為紅黑樹結構,反而會降低效率,因為紅黑樹需要進行左旋,右旋,變色這些操作來保持平衡。同事數組長度小於64時,搜索時間相對快一些。所以綜上所述為了提高性能和減少搜索時間,底層在閾值大於8並且數組長度大於64時,鍊錶才轉換為紅黑樹。具體可以參考treeifyBin方法。

當然雖然增了紅黑樹作為底層數據結構,結構變得複雜了,但是閾值大於8並且數組長度大於64時,鍊錶轉換為紅黑樹時,效率也變得更高效。

特點:

存取無序的鍵和值位置都可以是null,但是鍵位置只能是一個null鍵位置是唯一的,底層的數據結構控制鍵的jdk1.8前數據結構是:鍊錶+ 數組jdk1.8之後是:鍊錶+ 數組+ 紅黑樹閾值(邊界值) > 8 並且數組長度大於64,才將鍊錶轉換為紅黑樹,變為紅黑樹的目的是為了高效的查詢。

2,HsahMap底層數據結構

2.1,HashMap存儲數據的過程

了解HashMap數據結構,超詳細! 5

每一個Node結點都包含鍵值對的key,value還有計算出來的hash值,還保存著下一個 Node 的引用next(如果沒有下一個Node,next = null),來看看Node的源碼:

static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
...
}

HashMap存儲數據需要用到put()方法,關於這些方法的詳解,我們下節再說,這裡簡要說一下;

public static void main(String[] args) {
HashMap hmap=new HashMap();
hmap.put("斑",55);
hmap.put("镜",63);
hmap.put("带土",25);
hmap.put("鼬",9);
hmap.put("佐助",43);
hmap.put("斑",88);
System.out.println(hmap);
}

當創建HashMap集合對象的時候,在jdk1.8之前,構造方法中會創建很多長度是16的Entry[] table用來存儲鍵值對數據的。在jdk1.8之後不是在HashMap的構造方法底層創建數組了,是在第一次調用put方法時創建的數組,Node[] table用來存儲鍵值對數據的。

比方說我們向哈希表中存儲”斑”-55的數據,根據K值(“斑”)調用String類中重寫之後的hashCode()方法計算出值(數量級很大),然後結合數組長度採用取餘((n-1)&hash)操作或者其他操作方法來計算出向Node數組中存儲數據的空間的索引值。如果計算出來的索引空間沒有數據,則直接將”斑”-55數據存儲到數組中。跟上面的”A-王炸”數據差不多。

我們回到上方的數組圖,如果此時再插入”A-蘑菇”元素,那麼首先根據Key值(“A”)調用hashCode()方法結合數組長度計算出索引肯定也是3,此時比較後存儲的”A-蘑菇”和已經存在的數據”A-王炸”的hash值是否相等,如果hash相等,此時發生hash碰撞。

那麼底層會調用”A”所屬類String中的equals方法比較兩個key內容是否相等,若相等,則後添加的數據直接覆蓋已經存在的Value,也就是”蘑菇”直接覆蓋”王炸”;若不相等,繼續向下和其他數據的key進行比較,如果都不相等,則規劃出一個節點存儲數據。

了解HashMap數據結構,超詳細! 6

兩個結點key值比較,是否覆蓋

2.2,哈希碰撞相關的問題

哈希表底層採用何種算法計算hash值?還有哪些算法可以計算出hash值?

底層是採用key的hashCode方法的值結合數組長度進行無符號右移(>>>)、按位異或(^)、按位與(&)計算出索引的

還可以採用:平方取中法,取餘數,偽隨機數法。這三種效率都比較低。而無符號右移16位異或運算效率是最高的。

當兩個對象的hashCode相等時會怎麼樣?

會產生哈希碰撞,若key值內容相同則替換舊的value.否則連接到鍊錶後面,鍊錶長度超過閾值8就轉換為紅黑樹存儲。

何時發生哈希碰撞和什麼是哈希碰撞,如何解決哈希碰撞?

只要兩個元素的key計算的哈希值相同就會發生哈希碰撞。 jdk8前使用鍊錶解決哈希碰撞。 jdk8之後使用鍊錶+紅黑樹解決哈希碰撞。

如果兩個鍵的hashcode相同,如何存儲鍵值對?

hashcode相同,通過equals比較內容是否相同。相同:則新的value覆蓋之前的value 不相同:則將新的鍵值對添加到哈希表中

2.3,紅黑樹結構

當位於一個鍊錶中的元素較多,即hash值相等但是內容不相等的元素較多時,通過key值依次查找的效率較低。而jdk1.8中,哈希表存儲采用數組+鍊錶+紅黑樹實現,當鍊錶長度(閥值)超過8 時且當前數組的長度> 64時,將鍊錶轉換為紅黑樹,這樣大大減少了查找時間。 jdk8在哈希表中引入紅黑樹的原因只是為了查找效率更高。

了解HashMap數據結構,超詳細! 7

紅黑樹結構

JDK 1.8 以前HashMap 的實現是數組+鍊錶,即使哈希函數取得再好,也很難達到元素百分百均勻分佈。當HashMap 中有大量的元素都存放到同一個桶中時,這個桶下有一條長長的鍊錶,這個時候HashMap 就相當於一個單鍊錶,假如單鍊錶有n 個元素,遍歷的時間複雜度就是O(n),完全失去了它的優勢。針對這種情況,JDK 1.8 中引入了紅黑樹(查找時間複雜度為O(logn))來優化這個問題。當鍊錶長度很小的時候,即使遍歷,速度也非常快,但是當鍊錶長度不斷變長,肯定會對查詢性能有一定的影響,所以才需要轉成樹。

2.4,存儲流程圖

HashMap存放數據是用的put方法,put 方法內部調用的是putVal() 方法,所以對put 方法的分析也是對putVal 方法的分析,整個過程比較複雜,流程圖如下:

了解HashMap數據結構,超詳細! 8

來看看put()源碼:

public V put(K key, V value) {
//对key的hashCode()做hash,调用的是putVal方法
return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
/*
1,tab为空则开始创建,
2,(tab = table) == null 表示将空的table赋值给tab,然后判断tab是否等于null,第一次肯定是null
3,(n = tab.length) == 0 表示没有为table分配内存
4,tab为空,执行代码 n = (tab = resize()).length; 进行扩容。并将初始化好的数组长度赋值给n.
5,执行完n = (tab = resize()).length,数组tab每个空间都是null
*/

if ((tab = table) == null || (n = tab.length) == 0)
//调用resize()方法进行扩容
n = (tab = resize()).length;
/*
1,i = (n - 1) & hash 表示计算数组的索引赋值给i,即确定元素存放在哪个桶中
2,p = tab[i = (n - 1) & hash]表示获取计算出的位置的数据赋值给节点p
3,(p = tab[i = (n - 1) & hash]) == null 判断节点位置是否等于null,
如果为null,则执行代码:tab[i] = newNode(hash, key, value, null);根据键值对创建新的节点放入该位置的桶中
小结:如果当前桶没有哈希碰撞冲突,则直接把键值对插入空间位置
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//节点位置为null,则直接进行插入操作
tab[i] = newNode(hash, key, value, null);
//节点位置不为null,表示这个位置已经有值了,于是需要进行比较hash值是否相等
else {
Node e; K k;
/*
比较桶中第一个元素(数组中的结点)的hash值和key是否相等
1,p.hash == hash 中的p.hash表示原来存在数据的hash值 hash表示后添加数据的hash值 比较两个hash值是否相等
2,(k = p.key) == key :p.key获取原来数据的key赋值给k key表示后添加数据的key 比较两个key的地址值是否相等
3,key != null && key.equals(k):能够执行到这里说明两个key的地址值不相等,那么先判断后添加的key是否等于null,如果不等于null再调用equals方法判断两个key的内容是否相等
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/*
说明:两个元素哈希值相等(哈希碰撞),并且key的值也相等
将旧的元素整体对象赋值给e,用e来记录
*/
e = p;
// hash值不相等或者key不相等;判断p是否为红黑树结点
else if (p instanceof TreeNode)
// 是红黑树,调用树的插入方法
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 说明是链表节点,这时进行插入操作
else {
/*
1,如果是链表的话需要遍历到最后节点然后插入
2,采用循环遍历的方式,判断链表中是否有重复的key
*/
for (int binCount = 0; ; ++binCount) {
/*
1)e = p.next 获取p的下一个元素赋值给e
2)(e = p.next) == null 判断p.next是否等于null,等于null,说明p没有下一个元 素,那么此时到达了链表的尾部,还没有找到重复的key,则说明HashMap没有包含该键
将该键值对插入链表中
*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//插入后发现链表长度大于8,转换成红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
//转换为红黑树
treeifyBin(tab, hash);
break;
}
//key值以及存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//若结点为null,则不进行插入操作
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//修改记录次数
++modCount;
// 判断实际大小是否大于threshold阈值,如果超过则扩容
if (++size > threshold)
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}

小結:

根據哈希表中元素個數確定是擴容還是樹形化如果是樹形化遍歷桶中的元素,創建相同個數的樹形節點,複製內容,建立起聯繫然後讓桶中的第一個元素指向新創建的樹根節點,替換桶的鍊錶內容為樹形化內容

3,HashMap的擴容機制

我們知道,數組的容量是有限的,多次插入數據的話,到達一定數量就會進行擴容;先來看兩個問題

什麼時候需要擴容?

當HashMap中的元素個數超過數組長度loadFactor(負載因子)時,就會進行數組擴容,loadFactor的默認值是0.75,這是一個折中的取值。也就是說,默認情況下,數組大小為16,那麼當HashMap中的元素個數超過16×0.75=12(這個值就是閾值)的時候,就把數組的大小擴展為2×16=32,即擴大一倍,然後重新計算每個元素在數組中的位置,而這是一個非常耗性能的操作,所以如果我們已經預知HashMap中元素的個數,那麼預知元素的個數能夠有效的提高HashMap的性能。

怎麼進行擴容的?

HashMap在進行擴容時使用resize() 方法,計算table 數組的新容量和Node 在新數組中的新位置,將舊數組中的值複製到新數組中,從而實現自動擴容。因為每次擴容都是翻倍,與原來計算的(n-1)&hash的結果相比,只是多了一個bit位,所以節點要么就在原來的位置,要么就被分配到”原位置+舊容量”這個位置。

因此,我們在擴充HashMap的時候,不需要重新計算hash,只需要看看原來hash值新增的那個bit是1還是0就可以了,是0的話索引沒變,是1的話索引變成“原索引+oldCap(原位置+舊容量)”。這裡不再詳細贅述,可以看看下圖為16擴充為32的resize示意圖:

了解HashMap數據結構,超詳細! 9

hashmap擴容

4,HashMap數組長度為什麼是2的次冪

我們先看看它的成員變量:

序列化版本號

private static final long serialVersionUID = 362498820763181265L;

集合的初始化容量initCapacity

//默认的初始容量是16 -- 1<<4相当于1*2的4次方---1*16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

初始化容量默認是16,容量過大,遍歷時會減慢速度,效率低;容量過小,那麼擴容的次數變多,非常耗費性能。

負載因子

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

初始默認值為0.75,若過大,會導致哈希衝突的可能性更大;若過小,擴容的次數也會提高。

為什麼必須是2的n次冪?

當向HashMap中添加一個元素的時候,需要根據key的hash值,去確定其在數組中的具體位置。 HashMap為了提高存取效率,要盡量較少碰撞,就是要盡量把數據分配均勻,每個鍊錶長度大致相同,這個實現就在把數據存到哪個鍊錶中的算法。

這個算法實際就是取模,hash%length,計算機中直接求餘效率不如位移運算。所以源碼中做了優化,使用 hash&(length-1),而實際上hash%length等於hash&(length-1)的前提是length是2的n次冪。

如果輸入值不是2的冪會怎麼樣?

如果數組長度不是2的n次冪,計算出的索引特別容易相同,及其容易發生hash碰撞,導致其餘數組空間很大程度上並沒有存儲數據,鍊錶或者紅黑樹過長,效率降低。

小結:

1,當根據key的hash確定其在數組的位置時,如果n為2的冪次方,可以保證數據的均勻插入,如果n不是2的冪次方,可能數組的一些位置永遠不會插入數據,浪費數組的空間,加大hash衝突。

2,一般可能會想通過% 求餘來確定位置,這樣也可以,只不過性能不如& 運算。而且當n是2的冪次方時:hash & (length - 1) == hash % length

3,因此,HashMap 容量為2次冪的原因,就是為了數據的的均勻分佈,減少hash衝突,畢竟hash衝突越大,代表數組中一個鏈的長度越大,這樣的話會降低hashmap的性能

微信搜索公眾號《程序員的時光》

好了,今天就先分享到這裡了,下期繼續給大家帶來HashMap面試內容!

更多乾貨、優質文章,歡迎關注我的原創技術公眾號~