點(diǎn)擊上方藍(lán)色小字，關(guān)注“碼農(nóng)小黑屋”

重磅干貨，第一時(shí)間送達(dá)

今天這篇文章給大家講講hashmap，這個(gè)號(hào)稱是所有Java工程師都會(huì)的數(shù)據(jù)結(jié)構(gòu)。為什么說(shuō)是所有Java工程師都會(huì)呢，因?yàn)楹芎?jiǎn)單，他們不會(huì)這個(gè)找不到工作。幾乎所有面試都會(huì)問，基本上已經(jīng)成了標(biāo)配了。

在今天的這篇文章當(dāng)中我們會(huì)揭開很多謎團(tuán)。比如，為什么hashmap的get和put操作的復(fù)雜度是，甚至比紅黑樹還要快？hashmap和hash算法究竟是什么關(guān)系？hashmap有哪些參數(shù)，這些參數(shù)分別是做什么用的？hashmap是線程安全的嗎？我們?cè)趺磥?lái)維護(hù)hashmap的平衡呢？

讓我們帶著疑問來(lái)看看hashmap的基本結(jié)構(gòu)。

基本結(jié)構(gòu)

hashmap這個(gè)數(shù)據(jù)結(jié)構(gòu)其實(shí)并不難，它的結(jié)構(gòu)非常非常清楚，我用一句話就可以說(shuō)明，其實(shí)就是鄰接表。雖然這兩者的用途迥然不同，但是它們的結(jié)構(gòu)是完全一樣的。說(shuō)白了就是一個(gè)定長(zhǎng)的數(shù)組，這個(gè)數(shù)組的每一個(gè)元素都是一個(gè)鏈表的頭結(jié)點(diǎn)。我們把這個(gè)結(jié)構(gòu)畫出來(lái)，大家一看就明白了。

headers是一個(gè)定長(zhǎng)的數(shù)組，數(shù)組當(dāng)中的每一個(gè)元素都是一個(gè)鏈表的頭結(jié)點(diǎn)。也就是說(shuō)根據(jù)這個(gè)頭結(jié)點(diǎn)，我們可以遍歷這個(gè)鏈表。數(shù)組是定長(zhǎng)的，但是鏈表是變長(zhǎng)的，所以如果我們發(fā)生元素的增刪改查，本質(zhì)上都是通過鏈表來(lái)實(shí)現(xiàn)的。

這個(gè)就是hashmap的基本結(jié)構(gòu)，如果在面試當(dāng)中問到，你可以直接回答：它本質(zhì)上就是一個(gè)元素是鏈表的數(shù)組。

hash的作用

現(xiàn)在我們搞明白了hashmap的基本結(jié)構(gòu)，現(xiàn)在進(jìn)入下一個(gè)問題，這么一個(gè)結(jié)構(gòu)和hash之間有什么關(guān)系呢？

其實(shí)也不難猜，我們來(lái)思考一個(gè)場(chǎng)景。假設(shè)我們已經(jīng)擁有了一個(gè)hashmap，現(xiàn)在新來(lái)了一份數(shù)據(jù)需要存儲(chǔ)。上圖當(dāng)中數(shù)組的長(zhǎng)度是6，也就是說(shuō)有6個(gè)鏈表可供選擇，那么我們應(yīng)該把這個(gè)新來(lái)的元素放在哪個(gè)鏈表當(dāng)中呢？

你可能會(huì)說(shuō)當(dāng)然是放在最短的那個(gè)，這樣鏈表的長(zhǎng)度才能平衡。這樣的確不錯(cuò)，但是有一個(gè)問題，這樣雖然存儲(chǔ)方便了，但是讀取的時(shí)候卻有很大的問題。因?yàn)槲覀兇鎯?chǔ)的時(shí)候知道是存在最短的鏈表里了，但是當(dāng)我們讀取的時(shí)候，我們是不知道當(dāng)初哪個(gè)鏈表最短了，很有可能整個(gè)結(jié)構(gòu)已經(jīng)面目全非了。所以我們不能根據(jù)這種動(dòng)態(tài)的量來(lái)決定節(jié)點(diǎn)的放置位置，必須要根據(jù)靜態(tài)的量來(lái)決定。

這個(gè)靜態(tài)的量就是hash值，我們都知道hash算法的本質(zhì)上是進(jìn)行一個(gè)映射運(yùn)算，將一個(gè)任意結(jié)構(gòu)的值映射到一個(gè)整數(shù)上。我們的理想情況是不同的值映射的結(jié)果不同，相同的值映射的結(jié)果相同。也就是說(shuō)一個(gè)變量和一個(gè)整數(shù)是一一對(duì)應(yīng)的。但是由于我們的整數(shù)數(shù)量是有限的，而變量的取值是無(wú)窮的，那么一定會(huì)有一些變量雖然它們并不相等但是它們映射之后的結(jié)果是一樣的。這種情況叫做hash碰撞。

在hashmap當(dāng)中我們并不需要理會(huì)hash碰撞，因?yàn)槲覀儾⒉蛔非蟛煌膋ey能夠映射到不同的值。因?yàn)槲覀冎皇且眠@個(gè)hash值來(lái)決定這個(gè)節(jié)點(diǎn)應(yīng)該存放在哪一條鏈表當(dāng)中。只要hash函數(shù)確定了，只要值不變，計(jì)算得到的hash值也不會(huì)變。所以我們查詢的時(shí)候也可以遵循這個(gè)邏輯，找到key對(duì)應(yīng)的hash值以及對(duì)應(yīng)的鏈表。

在Python當(dāng)中由于系統(tǒng)提供了hash函數(shù)，所以整個(gè)過程變得更加方便。我們只需要兩行代碼就可以找到key對(duì)應(yīng)的鏈表。

hash_key?=?hash(key)?%?len(self.headers)
linked_list?=?self.headers[hash_key]

get、put實(shí)現(xiàn)

明白了hash函數(shù)的作用了之后，hashmap的問題就算是解決了大半。因?yàn)槭Ｏ碌木褪且粋€(gè)在鏈表當(dāng)中增刪改查的問題了，比如我們要通過key查找value的時(shí)候。當(dāng)我們通過hash函數(shù)確定了是哪一個(gè)鏈表之后，剩下的就是遍歷這個(gè)鏈表找到這個(gè)值。

這個(gè)函數(shù)我們可以實(shí)現(xiàn)在LinkedList這個(gè)類當(dāng)中，非常簡(jiǎn)單，就是一個(gè)簡(jiǎn)單的遍歷：

def?get_by_key(self,?key):
????cur?=?self.head.succ
????while?cur?!=?self.tail:
????????if?cur.key?==?key:
????????????return?cur
????????cur?=?cur.succ
????return?None

鏈表的節(jié)點(diǎn)查詢邏輯有了之后，hashmap的查詢邏輯也就有了。因?yàn)楸举|(zhì)上只做了兩件事，一件事根據(jù)hash函數(shù)的值找到對(duì)應(yīng)的鏈表，第二件事就是遍歷這個(gè)鏈表，找到這個(gè)節(jié)點(diǎn)。

我們也很容易實(shí)現(xiàn)：

def?get(self,?key):
????hash_key?=?self.get_hash_key(key)
????linked_list?=?self.headers[hash_key]
????node?=?linked_list.get_by_key(key)
????return?node

get方法實(shí)現(xiàn)了之后，寫出put方法也一樣水到渠成，因?yàn)閜ut方法邏輯和get相反。我們把查找換成添加或者是修改即可：

def?put(self,?key,?val):
????node?=?self.get(key)
????#?如果能找到，那么只需要更新即可
????if?node?is?not?None:
????????node.val?=?val
????else:
????????#?否則我們?cè)阪湵懋?dāng)中添加一個(gè)節(jié)點(diǎn)
????????node?=?Node(key,?val)
????????linked_list.append(node)

復(fù)雜度的保障

get和put都實(shí)現(xiàn)了，整個(gè)hashmap是不是就實(shí)現(xiàn)完了？很顯然沒有，因?yàn)檫€有一件很重要的事情我們沒有做，就是保證hashmap的復(fù)雜度。

我們簡(jiǎn)單分析一下就會(huì)發(fā)現(xiàn)，這樣實(shí)現(xiàn)的hashmap有一個(gè)重大的問題。就是由于hashmap一開始的鏈表的數(shù)組是定長(zhǎng)的，不管這個(gè)數(shù)組多長(zhǎng)，只要我們存儲(chǔ)的元素足夠多，那么每一個(gè)鏈表當(dāng)中分配到的元素也就會(huì)非常多。我們都知道鏈表的遍歷速度是，這樣我們還怎么保證查詢的速度是常數(shù)級(jí)呢？

除此之外還有另外一個(gè)問題，就是hash值傾斜的問題。比如明明我們的鏈表有100個(gè)，但是我們的數(shù)據(jù)剛好hash值大部分對(duì)100取模之后都是0。于是大量的數(shù)據(jù)就會(huì)被存儲(chǔ)在0這個(gè)桶當(dāng)中，導(dǎo)致其他桶沒什么數(shù)據(jù)，就這一個(gè)桶爆滿。對(duì)于這種情況我們又怎么避免呢？

其實(shí)不論是數(shù)據(jù)過多也好，還是分布不均勻也罷，其實(shí)說(shuō)的都是同一種情況。就是至少一個(gè)桶當(dāng)中存儲(chǔ)的數(shù)據(jù)過多，導(dǎo)致效率降低。針對(duì)這種情況，hashmap當(dāng)中設(shè)計(jì)了一種檢查機(jī)制，一旦某一個(gè)桶當(dāng)中的元素超過某個(gè)閾值，那么就會(huì)觸發(fā)reset。也就是把hashmap當(dāng)中的鏈表數(shù)量增加一倍，并且把數(shù)據(jù)全部打亂重建。這個(gè)閾值是通過一個(gè)叫做load_factor的參數(shù)設(shè)置的，當(dāng)某一個(gè)桶當(dāng)中的元素大于load_factor * capacity的時(shí)候，就會(huì)觸發(fā)reset機(jī)制。

我們把reset的邏輯加進(jìn)去，那么put函數(shù)就變成了這樣：

def?put(self,?key,?val):
????hash_key?=?self.get_hash_key(key)
????linked_list?=?self.headers[hash_key]
????#?如果超過閾值
????if?linked_list.size?>=?self.load_factor?*?self.capacity:
????????#?進(jìn)行所有數(shù)據(jù)reset
????????self.reset()
????????#?對(duì)當(dāng)前要加入的元素重新hash分桶
????????hash_key?=?self.get_hash_key(key)
????????linked_list?=?self.headers[hash_key]
????????node?=?linked_list.get_by_key(key)
????????if?node?is?not?None:
????????????node.val?=?val
????????else:
????????????node?=?Node(key,?val)
????????????linked_list.append(node)

reset的邏輯也很簡(jiǎn)單，我們把數(shù)組的長(zhǎng)度擴(kuò)大一倍，然后把原本的數(shù)據(jù)一一讀取出來(lái)，重新hash分配到新的桶當(dāng)中即可。

def?reset(self):
????#?數(shù)組擴(kuò)大一倍
????headers?=?[LinkedList()?for?_?in?range(self.capacity?*?2)]
????cap?=?self.capacity
????#?capacity也擴(kuò)大一倍
????self.capacity?=?self.capacity?*?2
????for?i?in?range(cap):
????????linked_list?=?self.headers[i]
????????nodes?=?linked_list.get_list()
????????#?將原本的node一個(gè)一個(gè)填入新的鏈表當(dāng)中
????????for?u?in?nodes:
????????????hash_key?=?self.get_hash_key(u.key)
????????????head?=?headers[hash_key]
????????????head.append(u)
????self.headers?=?headers

其實(shí)這里的閾值就是我們的最大查詢時(shí)間，我們可以把它近似看成是一個(gè)比較大的常量，那么put和get的效率就有保障了。因?yàn)椴迦肓舜罅繑?shù)據(jù)或者是剛好遇到了hash不平均的情況我們就算是都解決了。

細(xì)節(jié)和升華

如果你讀過JDK當(dāng)中hashmap的源碼，你會(huì)發(fā)現(xiàn)hashmap的capacity也就是鏈表的數(shù)量是2的冪。這是為什么呢？

其實(shí)也很簡(jiǎn)單，因?yàn)榘凑瘴覀儎偛诺倪壿?#xff0c;當(dāng)我們通過hash函數(shù)計(jì)算出了hash值之后，還需要將這個(gè)值對(duì)capacity進(jìn)行取模。也就是hash(key) % capacity，這一點(diǎn)在剛才的代碼當(dāng)中也有體現(xiàn)。

這里有一個(gè)小問題就是取模運(yùn)算非常非常慢，在系統(tǒng)層面級(jí)比加減乘慢了數(shù)十倍。為了優(yōu)化和提升這個(gè)部分的性能，所以我們使用2的冪，這樣我們就可以用hash(key) & (capacity - 1)來(lái)代替hash(key) % capacity，因?yàn)楫?dāng)capacity是2的冪時(shí)，這兩者計(jì)算是等價(jià)的。我們都知道位運(yùn)算的計(jì)算速度是計(jì)算機(jī)當(dāng)中所有運(yùn)算最快的，這樣我們可以提升不少的計(jì)算效率。

最后聊一聊線程安全，hashmap是線程安全的嗎？答案很簡(jiǎn)單，當(dāng)然不是。因?yàn)槔锩鏇]有任何加鎖或者是互斥的限制，A線程在修改一個(gè)節(jié)點(diǎn)，B線程也可以同時(shí)在讀取同樣的節(jié)點(diǎn)。那么很容易出現(xiàn)問題，尤其是還有reset這種時(shí)間比較長(zhǎng)的操作。如果剛好在reset期間來(lái)了其他的查詢，那么結(jié)果一定是查詢不到，但很有可能這個(gè)數(shù)據(jù)是存在的。所以hashmap不是線程安全的，不可以在并發(fā)場(chǎng)景當(dāng)中使用。

最后，我們附上hashmap完整的實(shí)現(xiàn)代碼：

import?random

class?Node:
????def?__init__(self,?key,?val,?prev=None,?succ=None):
????????self.key?=?key
????????self.val?=?val
????????#?前驅(qū)
????????self.prev?=?prev
????????#?后繼
????????self.succ?=?succ

????def?__repr__(self):
????????return?str(self.val)


class?LinkedList:
????def?__init__(self):
????????self.head?=?Node(None,?'header')
????????self.tail?=?Node(None,?'tail')
????????self.head.succ?=?self.tail
????????self.tail.prev?=?self.head
????????self.size?=?0

????def?append(self,?node):
????????#?將node節(jié)點(diǎn)添加在鏈表尾部
????????prev?=?self.tail.prev
????????node.prev?=?prev
????????node.succ?=?prev.succ
????????prev.succ?=?node
????????node.succ.prev?=?node
????????self.size?+=?1

????def?delete(self,?node):
????????#?刪除節(jié)點(diǎn)
????????prev?=?node.prev
????????succ?=?node.succ
????????succ.prev,?prev.succ?=?prev,?succ
????????self.size?-=?1

????def?get_list(self):
????????#?返回一個(gè)包含所有節(jié)點(diǎn)的list，方便上游遍歷
????????ret?=?[]
????????cur?=?self.head.succ
????????while?cur?!=?self.tail:
????????????ret.append(cur)
????????????cur?=?cur.succ
????????return?ret

????def?get_by_key(self,?key):
????????cur?=?self.head.succ
????????while?cur?!=?self.tail:
????????????if?cur.key?==?key:
????????????????return?cur
????????????cur?=?cur.succ
????????return?None



class?HashMap:
????def?__init__(self,?capacity=16,?load_factor=5):
????????self.capacity?=?capacity
????????self.load_factor?=?load_factor
????????self.headers?=?[LinkedList()?for?_?in?range(capacity)]

????def?get_hash_key(self,?key):
????????return?hash(key)?&?(self.capacity?-?1)

????def?put(self,?key,?val):
????????hash_key?=?self.get_hash_key(key)
????????linked_list?=?self.headers[hash_key]
????????if?linked_list.size?>=?self.load_factor?*?self.capacity:
????????????self.reset()
????????????hash_key?=?self.get_hash_key(key)
????????????linked_list?=?self.headers[hash_key]
????????node?=?linked_list.get_by_key(key)
????????if?node?is?not?None:
????????????node.val?=?val
????????else:
????????????node?=?Node(key,?val)
????????????linked_list.append(node)

????def?get(self,?key):
????????hash_key?=?self.get_hash_key(key)
????????linked_list?=?self.headers[hash_key]
????????node?=?linked_list.get_by_key(key)
????????return?node.val?if?node?is?not?None?else?None

????def?delete(self,?key):
????????node?=?self.get(key)
????????if?node?is?None:
????????????return?False
????????hash_key?=?self.get_hash_key(key)
????????linked_list?=?self.headers[hash_key]
????????linked_list.delete(node)
????????return?True

????def?reset(self):
????????headers?=?[LinkedList()?for?_?in?range(self.capacity?*?2)]
????????cap?=?self.capacity
????????self.capacity?=?self.capacity?*?2
????????for?i?in?range(cap):
????????????linked_list?=?self.headers[i]
????????????nodes?=?linked_list.get_list()
????????????for?u?in?nodes:
????????????????hash_key?=?self.get_hash_key(u.key)
????????????????head?=?headers[hash_key]
????????????????head.append(u)
????????self.headers?=?headers

喜歡本篇內(nèi)容請(qǐng)點(diǎn)個(gè)“在看”

總結(jié)

以上是生活随笔為你收集整理的查询已有链表的hashmap_原创 | 面试不再慌，看完这篇保证让你写HashMap跟玩一样...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。