hashmap怎麼取值_面試不再慌，看完這篇保證讓你寫HashMap跟玩一樣

今天這篇文章給大家講講hashmap，這個号稱是所有Java工程師都會的資料結構。為什麼說是所有Java工程師都會呢，因為很簡單，他們不會這個找不到工作。幾乎所有面試都會問，基本上已經成了标配了。

在今天的這篇文章當中我們會揭開很多謎團。比如，為什麼hashmap的get和put操作的複雜度是

O(1)，甚至比紅黑樹還要快？hashmap和hash算法究竟是什麼關系？hashmap有哪些參數，這些參數分别是做什麼用的？hashmap是線程安全的嗎？我們怎麼來維護hashmap的平衡呢？

讓我們帶着疑問來看看hashmap的基本結構。

基本結構

hashmap這個資料結構其實并不難，它的結構非常非常清楚，我用一句話就可以說明，其實就是鄰接表。雖然這兩者的用途迥然不同，但是它們的結構是完全一樣的。說白了就是一個定長的數組，這個數組的每一個元素都是一個連結清單的頭結點。我們把這個結構畫出來，大家一看就明白了。

headers是一個定長的數組，數組當中的每一個元素都是一個連結清單的頭結點。也就是說根據這個頭結點，我們可以周遊這個連結清單。數組是定長的，但是連結清單是變長的，是以如果我們發生元素的增删改查，本質上都是通過連結清單來實作的。

這個就是hashmap的基本結構，如果在面試當中問到，你可以直接回答：它本質上就是一個元素是連結清單的數組。

hash的作用

現在我們搞明白了hashmap的基本結構，現在進入下一個問題，這麼一個結構和hash之間有什麼關系呢？

其實也不難猜，我們來思考一個場景。假設我們已經擁有了一個hashmap，現在新來了一份資料需要存儲。上圖當中數組的長度是6，也就是說有6個連結清單可供選擇，那麼我們應該把這個新來的元素放在哪個連結清單當中呢？

你可能會說當然是放在最短的那個，這樣連結清單的長度才能平衡。這樣的确不錯，但是有一個問題，這樣雖然存儲友善了，但是讀取的時候卻有很大的問題。因為我們存儲的時候知道是存在最短的連結清單裡了，但是當我們讀取的時候，我們是不知道當初哪個連結清單最短了，很有可能整個結構已經面目全非了。是以我們不能根據這種動态的量來決定節點的放置位置，必須要根據靜态的量來決定。

這個靜态的量就是hash值，我們都知道hash算法的本質上是進行一個映射運算，将一個任意結構的值映射到一個整數上。我們的理想情況是不同的值映射的結果不同，相同的值映射的結果相同。也就是說一個變量和一個整數是一一對應的。但是由于我們的整數數量是有限的，而變量的取值是無窮的，那麼一定會有一些變量雖然它們并不相等但是它們映射之後的結果是一樣的。這種情況叫做hash碰撞。

在hashmap當中我們并不需要理會hash碰撞，因為我們并不追求不同的key能夠映射到不同的值。因為我們隻是要用這個hash值來決定這個節點應該存放在哪一條連結清單當中。隻要hash函數确定了，隻要值不變，計算得到的hash值也不會變。是以我們查詢的時候也可以遵循這個邏輯，找到key對應的hash值以及對應的連結清單。

在Python當中由于系統提供了hash函數，是以整個過程變得更加友善。我們隻需要兩行代碼就可以找到key對應的連結清單。

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

get、put實作

明白了hash函數的作用了之後，hashmap的問題就算是解決了大半。因為剩下的就是一個在連結清單當中增删改查的問題了，比如我們要通過key查找value的時候。當我們通過hash函數确定了是哪一個連結清單之後，剩下的就是周遊這個連結清單找到這個值。

這個函數我們可以實作在LinkedList這個類當中，非常簡單，就是一個簡單的周遊：

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
           

連結清單的節點查詢邏輯有了之後，hashmap的查詢邏輯也就有了。因為本質上隻做了兩件事，一件事根據hash函數的值找到對應的連結清單，第二件事就是周遊這個連結清單，找到這個節點。

我們也很容易實作：

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方法實作了之後，寫出put方法也一樣水到渠成，因為put方法邏輯和get相反。我們把查找換成添加或者是修改即可：

def put(self, key, val):    node = self.get(key)    # 如果能找到，那麼隻需要更新即可    if node is not None:        node.val = val    else:        # 否則我們在連結清單當中添加一個節點        node = Node(key, val)        linked_list.append(node)
           

複雜度的保障

get和put都實作了，整個hashmap是不是就實作完了？很顯然沒有，因為還有一件很重要的事情我們沒有做，就是保證hashmap的複雜度。

我們簡單分析一下就會發現，這樣實作的hashmap有一個重大的問題。就是由于hashmap一開始的連結清單的數組是定長的，不管這個數組多長，隻要我們存儲的元素足夠多，那麼每一個連結清單當中配置設定到的元素也就會非常多。我們都知道連結清單的周遊速度是O(n)，這樣我們還怎麼保證查詢的速度是常數級呢？

除此之外還有另外一個問題，就是hash值傾斜的問題。比如明明我們的連結清單有100個，但是我們的資料剛好hash值大部分對100取模之後都是0。于是大量的資料就會被存儲在0這個桶當中，導緻其他桶沒什麼資料，就這一個桶爆滿。對于這種情況我們又怎麼避免呢？

其實不論是資料過多也好，還是分布不均勻也罷，其實說的都是同一種情況。就是至少一個桶當中存儲的資料過多，導緻效率降低。針對這種情況，hashmap當中設計了一種檢查機制，一旦某一個桶當中的元素超過某個門檻值，那麼就會觸發reset。也就是把hashmap當中的連結清單數量增加一倍，并且把資料全部打亂重建。這個門檻值是通過一個叫做load_factor的參數設定的，當某一個桶當中的元素大于load_factor * capacity的時候，就會觸發reset機制。

我們把reset的邏輯加進去，那麼put函數就變成了這樣：

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:        # 進行所有資料reset        self.reset()        # 對目前要加入的元素重新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的邏輯也很簡單，我們把數組的長度擴大一倍，然後把原本的資料一一讀取出來，重新hash配置設定到新的桶當中即可。

def reset(self):    # 數組擴大一倍    headers = [LinkedList() for _ in range(self.capacity * 2)]    cap = self.capacity    # capacity也擴大一倍    self.capacity = self.capacity * 2    for i in range(cap):        linked_list = self.headers[i]        nodes = linked_list.get_list()        # 将原本的node一個一個填入新的連結清單當中        for u in nodes:            hash_key = self.get_hash_key(u.key)            head = headers[hash_key]            head.append(u)    self.headers = headers
           

其實這裡的門檻值就是我們的最大查詢時間，我們可以把它近似看成是一個比較大的常量，那麼put和get的效率就有保障了。因為插入了大量資料或者是剛好遇到了hash不平均的情況我們就算是都解決了。

細節和升華

如果你讀過JDK當中hashmap的源碼，你會發現hashmap的capacity也就是連結清單的數量是2的幂。這是為什麼呢？

其實也很簡單，因為按照我們剛才的邏輯，當我們通過hash函數計算出了hash值之後，還需要将這個值對capacity進行取模。也就是hash(key) % capacity，這一點在剛才的代碼當中也有展現。

這裡有一個小問題就是取模運算非常非常慢，在系統層面級比加減乘慢了數十倍。為了優化和提升這個部分的性能，是以我們使用2的幂，這樣我們就可以用hash(key) & (capacity - 1)來代替hash(key) % capacity，因為當capacity是2的幂時，這兩者計算是等價的。我們都知道位運算的計算速度是計算機當中所有運算最快的，這樣我們可以提升不少的計算效率。

最後聊一聊線程安全，hashmap是線程安全的嗎？答案很簡單，當然不是。因為裡面沒有任何加鎖或者是互斥的限制，A線程在修改一個節點，B線程也可以同時在讀取同樣的節點。那麼很容易出現問題，尤其是還有reset這種時間比較長的操作。如果剛好在reset期間來了其他的查詢，那麼結果一定是查詢不到，但很有可能這個資料是存在的。是以hashmap不是線程安全的，不可以在并發場景當中使用。

最後，我們附上hashmap完整的實作代碼：

import randomclass Node:    def __init__(self, key, val, prev=None, succ=None):        self.key = key        self.val = val        # 前驅        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節點添加在連結清單尾部        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):        # 删除節點        prev = node.prev        succ = node.succ        succ.prev, prev.succ = prev, succ        self.size -= 1    def get_list(self):        # 傳回一個包含所有節點的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 Noneclass 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
           

今天的文章就到這裡，衷心祝願大家每天都有所收獲。如果還喜歡今天的内容的話，請來一個三連支援吧~(點贊、關注、轉發)

- END -

本文始發于公衆号：TechFlow，求個關注