1. 前言

哈希表或稱為散列表，是一種常見的、使用頻率非常高的數(shù)據(jù)存儲(chǔ)方案。

哈希表屬于抽象數(shù)據(jù)結(jié)構(gòu)，需要開發(fā)者按哈希表數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)要求進(jìn)行API定制，對(duì)于大部分高級(jí)語(yǔ)言而言，都會(huì)提供已經(jīng)實(shí)現(xiàn)好的、可直接使用的API，如JAVA中有MAP集合、C++中的MAP容器，Python中的字典……

使用者可以使用API中的方法完成對(duì)哈希表的增、刪、改、查……一系列操作。

如何學(xué)習(xí)哈希表？

可以從2個(gè)角度開始：

• 使用者角度：只需要知道哈希表是基于鍵、值對(duì)存儲(chǔ)的解決方案，另需要熟悉不同計(jì)算機(jī)語(yǔ)言提供的基于哈希表數(shù)據(jù)結(jié)構(gòu)的 API實(shí)現(xiàn)，學(xué)會(huì)使用 API中的方法。
• 開發(fā)者的角度：則需要知道哈希表底層實(shí)現(xiàn)原理，以及實(shí)現(xiàn)過(guò)程中需要解決的各種問題。本文將站在開發(fā)者的角度，帶著大家一起探究哈希的世界。

2. 哈希表

什么是哈希表？

哈希表是基于鍵、值對(duì)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，底層一般采用的是列表(數(shù)組)。

大家都知道，基于列表（數(shù)組）的查詢速度非?？?，時(shí)間復(fù)雜度是O（1），常量級(jí)別的。

列表的底層存儲(chǔ)結(jié)構(gòu)是連續(xù)的內(nèi)存區(qū)域，只要給定數(shù)據(jù)在列表（數(shù)組）中的位置，就能直接查詢到數(shù)據(jù)。理論上是這么回事，但在實(shí)際操作過(guò)程，查詢數(shù)據(jù)的時(shí)間復(fù)雜度卻不一定是常量級(jí)別的。

如存儲(chǔ)下面的學(xué)生信息，學(xué)生信息包括學(xué)生的姓名和學(xué)號(hào)。在存儲(chǔ)學(xué)生數(shù)據(jù)時(shí)，如果把學(xué)號(hào)為0的學(xué)生存儲(chǔ)在列表0位置，學(xué)號(hào)為1的學(xué)生存儲(chǔ)在列表1位置……

這里把學(xué)生的學(xué)號(hào)和列表的索引號(hào)進(jìn)行關(guān)聯(lián)，查詢某一個(gè)學(xué)生時(shí)，知道了學(xué)生的學(xué)號(hào)也就知道了學(xué)生數(shù)據(jù)存儲(chǔ)在列表中的位置，可以認(rèn)為查詢的時(shí)間復(fù)雜度為O(1)。

之所以可以達(dá)到常量級(jí)，是因?yàn)檫@里有信息關(guān)聯(lián)（學(xué)生學(xué)號(hào)關(guān)聯(lián)到數(shù)據(jù)的存儲(chǔ)位置）。

還有一點(diǎn)，學(xué)生的學(xué)號(hào)是公開信息也是常用信息，很容易獲取。

但是，不是存儲(chǔ)任何數(shù)據(jù)時(shí)，都可以找到與列表位置相關(guān)聯(lián)的信息。比如存儲(chǔ)所有的英文單詞，不可能為每一個(gè)英文單詞編號(hào)，即使編號(hào)了，編號(hào)在這里也僅僅是流水號(hào)，沒有數(shù)據(jù)含義的數(shù)據(jù)對(duì)于使用者來(lái)講是不友好，誰(shuí)也無(wú)法記住哪個(gè)英文單詞對(duì)應(yīng)哪個(gè)編號(hào)。

所以使用列表存儲(chǔ)英文單詞后需要詢時(shí)，因沒有單詞的存儲(chǔ)位置。還是需要使用如線性、二分……之類的查詢算法，這時(shí)的時(shí)間復(fù)雜度由使用的查詢算法的時(shí)間復(fù)雜度決定。

如果對(duì)上述存儲(chǔ)在列表的學(xué)生信息進(jìn)行了插入、刪除……等操作，改變了數(shù)據(jù)原來(lái)的位置后，因破壞了學(xué)號(hào)與位置關(guān)聯(lián)信息，再查詢時(shí)也只能使用其它查詢算法，不可能達(dá)到常量級(jí)。

是否存在一種方案，能最大化地優(yōu)化數(shù)據(jù)的存儲(chǔ)和查詢？

通過(guò)上述的分析，可以得出一個(gè)結(jié)論，要提高查詢的速度，得想辦法把數(shù)據(jù)與位置進(jìn)行關(guān)聯(lián)。而哈希表的核心思想便是如此。

2.1 哈希函數(shù)

哈希表引入了關(guān)鍵字概念，關(guān)鍵字可以認(rèn)為是數(shù)據(jù)的別名。如上表，可以給每一個(gè)學(xué)生起一個(gè)別名，這個(gè)就是關(guān)鍵字。

Tip： 這里的關(guān)鍵字是姓名的拼音縮寫，關(guān)鍵字和數(shù)據(jù)的關(guān)聯(lián)性較強(qiáng)，方便記憶和查詢。

有了關(guān)鍵字后，再把關(guān)鍵字映射成列表中的一個(gè)有效位置，映射方法就是哈希表中最重要的概念哈希函數(shù)。

關(guān)鍵字是一個(gè)橋梁，即關(guān)聯(lián)到真正數(shù)據(jù)又關(guān)聯(lián)到哈希表中的位置。

關(guān)鍵字也可以是需要保存的數(shù)據(jù)本身。

哈希函數(shù)的功能：提供把關(guān)鍵字映射到列表中的位置算法，是哈希表存儲(chǔ)數(shù)據(jù)的核心所在。如下圖，演示數(shù)據(jù)、哈希函數(shù)、哈希表之間的關(guān)系，可以說(shuō)哈希函數(shù)是數(shù)據(jù)進(jìn)入哈希表的入口。

數(shù)據(jù)最終會(huì)存儲(chǔ)在列表中的哪一個(gè)位置，完全由哈希算法決定。

當(dāng)需要查詢學(xué)生數(shù)據(jù)時(shí)，同樣需要調(diào)用哈希函數(shù)對(duì)關(guān)鍵字進(jìn)行換算，計(jì)算出數(shù)據(jù)在列表中的位置后就能很容易查詢到數(shù)據(jù)。

如果忽視哈希函數(shù)的時(shí)間復(fù)雜度，基于哈希表的數(shù)據(jù)存儲(chǔ)和查詢時(shí)間復(fù)雜度是 O(1)。

如此說(shuō)來(lái)哈希函數(shù)算法設(shè)計(jì)的優(yōu)劣是影響哈希表性能的關(guān)鍵所在。

2.2 哈希算法

哈希算法決定了數(shù)據(jù)的最終存儲(chǔ)位置，不同的哈希算法設(shè)計(jì)方案，也關(guān)乎哈希表的整體性能，所以，哈希算法就變得的尤為重要。

下文將介紹并縱橫比較幾種常見的 哈希算法的設(shè)計(jì)方案。

Tip：無(wú)論使用何種哈希算法，都有一個(gè)根本，哈希后的結(jié)果一定是一個(gè)數(shù)字，表示列表（哈希表）中的一個(gè)有效位置。也稱為哈希值。

使用哈希表存儲(chǔ)數(shù)據(jù)時(shí)，關(guān)鍵字可以是數(shù)字類型也可以是非數(shù)字類型，其實(shí)，關(guān)鍵字可以是任何一種類型。這里先討論當(dāng)關(guān)鍵字為非數(shù)字類型時(shí)設(shè)計(jì)哈希算法的基本思路。

如前所述，已經(jīng)為每一個(gè)學(xué)生提供了一個(gè)以姓名的拼音縮寫的關(guān)鍵字。

現(xiàn)在如何把關(guān)鍵字映射到列表的一個(gè)有效位置？

這里可以簡(jiǎn)單地把拼音看成英文中的字母，先分別計(jì)算每一個(gè)字母在字母表中的位置，然后相加，得到的一個(gè)數(shù)字。

使用上面的哈希思想對(duì)每一個(gè)學(xué)生的關(guān)鍵字進(jìn)行哈希：

• zjl的哈希值為 26+10+12=48。
• llj的哈希值為 12+12+10=34。
• cl 的哈希值為 3+12=15。
• zxy的哈希值為 26+25+24=75。

前文說(shuō)過(guò)哈希值是表示數(shù)據(jù)在列表中的存儲(chǔ)位置，現(xiàn)在假設(shè)一種理想化狀態(tài)，學(xué)生的姓名都是3個(gè)漢字，意味著關(guān)鍵字也是3個(gè)字母，采用上面的的哈希算法，最大的哈希值應(yīng)該是zzz=26+26+26=78，意味著至少應(yīng)該提供一個(gè)長(zhǎng)度為78的列表 。

如果，現(xiàn)在僅僅只保存4名學(xué)生，雖然只有4名學(xué)生，因無(wú)法保證學(xué)生的關(guān)鍵字不出現(xiàn)zzz，所以列表長(zhǎng)度還是需要78。如下圖所示。

采用這種哈希算法會(huì)導(dǎo)致列表的空間浪費(fèi)嚴(yán)重，最直觀想法是對(duì)哈希值再做約束，如除以4再取余數(shù)，把哈希值限制在4之內(nèi)，4個(gè)數(shù)據(jù)對(duì)應(yīng)4個(gè)哈希值。我們稱這種取余數(shù)方案為取余數(shù)算法。

取余數(shù)法中，被除數(shù)一般選擇小于哈希表長(zhǎng)度的素?cái)?shù)。本文介紹其它哈希算法時(shí)，也會(huì)使用取余數(shù)法對(duì)哈希值進(jìn)行適當(dāng)范圍的收縮。

重新對(duì) 4 名學(xué)生的關(guān)鍵字進(jìn)行哈希。

• zjl的哈希值為 26+10+12=48，48 除以 4 取余數(shù)，結(jié)果是0。
• llj的哈希值為 12+12+10=34，34 除以 4 取余數(shù)，結(jié)果是2。
• cl 的哈希值為 3+12=15，15 除以 4 取余數(shù)，結(jié)果是3。
• zzz的哈希值為 26+26+26=78，78 除以 4 取余數(shù)，結(jié)果是2。

演示圖上出現(xiàn)了一個(gè)很奇怪的現(xiàn)象，沒有看到李連杰的存儲(chǔ)信息。

4個(gè)存儲(chǔ)位置存儲(chǔ)4學(xué)生，應(yīng)該是剛剛好，但是，只存儲(chǔ)了3名學(xué)生。且還有1個(gè)位置是空閑的。現(xiàn)在編碼驗(yàn)證一下，看是不是人為因素引起的。

'''
哈希函數(shù)
'''
def hash_code(key):
    # 設(shè)置字母 A 的在字母表中的位置是 1
    pos = 0
    for i in key:
        i = i.lower()
        res = ord(i) - ord('a') + 1
        pos += res
    return pos % 4

測(cè)試代碼：

# 哈希表
hash_table = [None] * 4
# 計(jì)算關(guān)鍵字的哈希值
idx = hash_code('zjl')
# 根據(jù)關(guān)鍵字換算出來(lái)的位置存儲(chǔ)數(shù)據(jù)
hash_table[idx] = '周杰倫'
idx = hash_code('llj')
hash_table[idx] = '李連杰'
idx = hash_code('cl')
hash_table[idx] = '成龍'
idx = hash_code('zzz')
hash_table[idx] = '張志忠'
print('哈希表中的數(shù)據(jù)：', hash_table)
'''
輸出結(jié)果：
哈希表中的數(shù)據(jù)： ['周杰倫', None, '張志忠', '成龍']
'''

執(zhí)行代碼，輸出結(jié)果，依然還是沒有看到李連杰的信息。

原因何在？

這是因?yàn)槔钸B杰和張志忠的哈希值都是2 ，導(dǎo)致在存儲(chǔ)時(shí)，后面存儲(chǔ)的數(shù)據(jù)會(huì)覆蓋前面存儲(chǔ)的數(shù)據(jù)，這就是哈希中的典型問題，哈希沖突問題。

所謂哈希沖突，指不同的關(guān)鍵字在進(jìn)行哈希算法后得到相同的哈希值，這意味著，不同關(guān)鍵字所對(duì)應(yīng)的數(shù)據(jù)會(huì)存儲(chǔ)在同一個(gè)位置，這肯定會(huì)發(fā)生數(shù)據(jù)丟失，所以需要提供算法，解決沖突問題。

Tip： 研究哈希表，歸根結(jié)底，是研究如何計(jì)算哈希值以及如何解決哈希值沖突的問題。

針對(duì)上面的問題，有一種想當(dāng)然的沖突解決方案，擴(kuò)展列表的存儲(chǔ)長(zhǎng)度，如把列表擴(kuò)展到長(zhǎng)度為8。

直觀思維是：擴(kuò)展列表長(zhǎng)度，哈希值的范圍會(huì)增加，沖突的可能性會(huì)降低。

'''
哈希函數(shù)
'''
def hash_code(key):
    # 設(shè)置字母 A 的在字母表中的位置是 1
    pos = 0
    for i in key:
        i = i.lower()
        res = ord(i) - ord('a') + 1
        pos += res
    return pos % 8

# 哈希表
hash_table = [None] * 8

# 保存所有學(xué)生
idx = hash_code('zjl')
hash_table[idx] = '周杰倫'
idx = hash_code('llj')
hash_table[idx] = '李連杰'
idx = hash_code('cl')
hash_table[idx] = '成龍'
idx = hash_code('zzz')
hash_table[idx] = '張志忠'
print('哈希表中的數(shù)據(jù)：', hash_table)
'''
輸出結(jié)果：
哈希表中的數(shù)據(jù)： ['周杰倫', None, '李連杰', None, None, None, '張志忠', '成龍']
'''

貌似解決了沖突問題，其實(shí)不然，當(dāng)試著設(shè)置列表的長(zhǎng)度為6、7、8、9、10時(shí)，只有當(dāng)長(zhǎng)度為8時(shí)沒有發(fā)生沖突，這還是在要存儲(chǔ)的數(shù)據(jù)是已知情況下的嘗試。

如果數(shù)據(jù)是動(dòng)態(tài)變化的，顯然這種擴(kuò)展長(zhǎng)度的方案絕對(duì)不是本質(zhì)解決沖突的方案。即不能解決沖突，且產(chǎn)生大量空間浪費(fèi)。

如何解決哈希沖突，會(huì)在后文詳細(xì)介紹，這里還是回到哈希算法上。

綜上所述，我們對(duì)哈希算法的理想要求是：

• 為每一個(gè)關(guān)鍵字生成一個(gè)唯一的哈希值，保證每一個(gè)數(shù)據(jù)都有只屬于自己的存儲(chǔ)位置。
• 哈希算法的性能時(shí)間復(fù)雜度要低。

現(xiàn)實(shí)情況是，同時(shí)滿足這2個(gè)條件的哈希算法幾乎是不可能有的，面對(duì)數(shù)據(jù)量較多時(shí)，哈希沖突是常態(tài)。所以，只能是盡可能滿足。

因沖突的存在，即使為 100 個(gè)數(shù)據(jù)提供 100 個(gè)有效存儲(chǔ)空間，還是會(huì)有空間閑置。這里把實(shí)際使用空間和列表提供的有效空間相除，得到的結(jié)果，稱之為哈希表的占有率（載荷因子）。

如上述，當(dāng)列表長(zhǎng)度為 4時(shí)， 占有率為 3/4=0.75，當(dāng)列表長(zhǎng)度為 8 時(shí)，占有率為 4/8=0.5，一般要求占率控制 在0.6~0.9之間。

2.3 常見哈希算法

前面在介紹什么是哈希算法時(shí)，提到了取余數(shù)法，除此之外，還有幾種常見的哈希算法。

2.3.1 折疊法

折疊法：將關(guān)鍵字分割成位數(shù)相同的幾個(gè)部分（最后一部分的位數(shù)可以不同）然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希值。

折疊法又分移位疊加和間界疊加。

• 移位疊加：將分割后的每一部分的最低位對(duì)齊，然后相加。
• 間界疊加：從一端沿分割線來(lái)回折疊，然后對(duì)齊相加。

因有相加求和計(jì)算，折疊法適合數(shù)字類型或能轉(zhuǎn)換成數(shù)字類型的關(guān)鍵字。假設(shè)現(xiàn)在有很多商品訂單信息，為了簡(jiǎn)化問題，訂單只包括訂單編號(hào)和訂單金額。

現(xiàn)在使用用哈希表存儲(chǔ)訂單數(shù)據(jù)，且以訂單編號(hào)為關(guān)鍵字，訂單金額為值。

移位疊法換算關(guān)鍵字的思路：

第一步：把訂單編號(hào)20201011按每3位一組分割，分割后的結(jié)果：202、010、11。

按2位一組還是3位一組進(jìn)行分割，可以根據(jù)實(shí)際情況決定。

第二步： 把分割后的數(shù)字相加202+010+11，得到結(jié)果：223。再使用取余數(shù)法，如果哈希表的長(zhǎng)度為10，則除以10后的余數(shù)為3。

這里除以10僅是為了簡(jiǎn)化問題細(xì)節(jié)，具體操作時(shí)，很少選擇列表的長(zhǎng)度。

第三步：對(duì)其它的關(guān)鍵字采用相同的處理方案。

編碼實(shí)現(xiàn)保存商品訂單信息：

'''
移位疊加哈希算法
'''
def hash_code(key, hash_table_size):
    # 轉(zhuǎn)換成字符串
    key_s = str(key)
    # 保存求和結(jié)果
    s = 0
    # 使用切片
    for i in range(0, len(key_s), 3):
        s += int(key_s[i:i + 3])
    return s % hash_table_size

# 商品信息
products = [[20201011, 400.00], [19981112, 300], [20221212, 200]]
# 哈希表長(zhǎng)度
hash_size = 10
# 哈希表
hash_table = [None] * hash_size
# 以哈希表方式進(jìn)行存儲(chǔ)
for p in products:
    key = hash_code(p[0], hash_size)
    hash_table[key] = p[1]
# 顯示哈希表中的數(shù)據(jù)
print("哈希表中的數(shù)據(jù)：",hash_table)
# 根據(jù)訂單號(hào)進(jìn)行查詢
hash_val = hash_code(19981112, hash_size)
val = hash_table[hash_val]
print("訂單號(hào)為{0}的金額為{1}".format(19981112, val))
'''
輸出結(jié)果
哈希表中的數(shù)據(jù)： [None, None, 300, 400.0, None, None, 200, None, None, None]
訂單號(hào)為19981112的金額為300
'''

間界疊加法：

間界疊加法，會(huì)間隔地把要相加的數(shù)字進(jìn)行反轉(zhuǎn)。

如訂單編號(hào)19981112 按3位一組分割，分割后的結(jié)果：199、811、12，間界疊加操作求和表達(dá)式為199+118+12=339，再把結(jié)果339%10=9。

編碼實(shí)現(xiàn)間界疊加算法：

'''
間界疊加哈希算法
'''
def hash_code(key, hash_table_size):
    # 轉(zhuǎn)換成字符串
    key_s = str(key)
    # 保存求和結(jié)果
    s = 0
    # 使用切片
    for i in range(0, len(key_s), 3):
        # 切片
        tmp_s = key_s[i:i + 3]
        # 反轉(zhuǎn)
        if i % 2 != 0:
            tmp_s = tmp_s[::-1]
        s += int(tmp_s)
    return s % hash_table_size

# 商品信息（數(shù)據(jù)樣例）
products = [[20201011, 400.00], [19981112, 300], [20221212, 200]]
# 哈希表長(zhǎng)度
hash_size = 10
# 哈希表
hash_table = [None] * hash_size
# 以哈希表方式進(jìn)行存儲(chǔ)
for p in products:
    key = hash_code(p[0], hash_size)
    hash_table[key] = p[1]
# 顯示哈希表中的數(shù)據(jù)
print("哈希表中的數(shù)據(jù)：", hash_table)
# 根據(jù)訂單號(hào)進(jìn)行查詢
hash_val = hash_code(19981112, hash_size)
val = hash_table[hash_val]
print("訂單號(hào)為{0}的金額為{1}".format(19981112, val))
'''
輸出結(jié)果：
哈希表中的數(shù)據(jù)： [None, None, None, 400.0, None, None, 200, None, None, 300]
訂單號(hào)為19981112的金額為300
'''

2.3.2 平方取中法

平方取中法：先是對(duì)關(guān)鍵字求平方，再在結(jié)果中取中間位置的數(shù)字。

求平方再取中算法，是一種較常見的哈希算法，從數(shù)學(xué)公式可知，求平方后得到的中間幾位數(shù)字與關(guān)鍵字的每一位都有關(guān)，取中法能讓最后計(jì)算出來(lái)的哈希值更均勻。

因要對(duì)關(guān)鍵字求平方，關(guān)鍵字只能是數(shù)字或能轉(zhuǎn)換成數(shù)字的類型，至于關(guān)鍵字本身的大小范圍限制，要根據(jù)使用的計(jì)算機(jī)語(yǔ)言靈活設(shè)置。

如下面的圖書數(shù)據(jù)，圖書包括圖書編號(hào)和圖書名稱。現(xiàn)在需要使用哈希表保存圖書信息，以圖書編號(hào)為關(guān)鍵字，圖書名稱為值。

使用平方取中法計(jì)算關(guān)鍵字的哈希值：

第一步：對(duì)圖書編號(hào)58求平方，結(jié)果為3364。

第二步：取3364的中間值36，然后再使用取余數(shù)方案。如果哈希表的長(zhǎng)度為10，則36%10=6。

第三步：對(duì)其它的關(guān)鍵字采用相同的計(jì)算方案。

編碼實(shí)現(xiàn)平方取中算法：

'''
哈希算法
平方取中
'''
def hash_code(key, hash_table_size):
    # 求平方
    res = key ** 2
    #  取中間值，這里取中間 2 位（簡(jiǎn)化問題）
    res = int(str(res)[1:3])
    # 取余數(shù)
    return res % hash_table_size

hash_table_size = 10
hash_table = [None]*hash_table_size
# 圖書信息
books = [[58, "python 從入門到精通"], [67, "C++ STL"], [78, "Java 內(nèi)存模型"]]
for b in books:
    hash_val = hash_code(b[0],hash_table_size)
    hash_table[hash_val]=b[1]

# 顯示哈希表中的數(shù)據(jù)
print("哈希表中的數(shù)據(jù)：", hash_table)
# 根據(jù)編號(hào)進(jìn)行查詢
hash_val = hash_code(67, hash_table_size)
val = hash_table[hash_val]
print("編號(hào)為{0}的書名為{1}".format(67, val))

上述求平方取中間值的算法僅針對(duì)于本文提供的圖書數(shù)據(jù)，如果需要算法具有通用性，則需要根據(jù)實(shí)際情況修改。

不要被 取中的中字所迷惑，不一定是絕對(duì)中間位置的數(shù)字。

2.3.3 直接地址法

直接地址法：提供一個(gè)與關(guān)鍵字相關(guān)聯(lián)的線性函數(shù)。如針對(duì)上述圖書數(shù)據(jù)，可以提供線性函數(shù)f(k)=2*key+10。

系數(shù)2和常數(shù)10的選擇會(huì)影響最終生成的哈希值的大小。可以根據(jù)哈希表的大小和操作的數(shù)據(jù)含義自行選擇。

key為圖書編號(hào)。當(dāng)關(guān)鍵字不相同時(shí)，使用線性函數(shù)得到的值也是唯一的，所以，不會(huì)產(chǎn)生哈希沖突，但是會(huì)要求哈希表的存儲(chǔ)長(zhǎng)度比實(shí)際數(shù)據(jù)要大。

這種算法在實(shí)際應(yīng)用中并不多見。

實(shí)際應(yīng)用時(shí)，具體選擇何種哈希算法，完全由開發(fā)者定奪，哈希算法的選擇沒有固定模式可循，雖然上面介紹了幾種算法，只是提供一種算法思路。

2.4 哈希沖突

哈希沖突是怎么引起的，前文已經(jīng)說(shuō)過(guò)。現(xiàn)在聊聊常見的幾種哈希沖突解決方案。

2.4.1 線性探測(cè)

當(dāng)發(fā)生哈希沖突后，會(huì)在沖突位置之后尋找一個(gè)可用的空位置。如下圖所示，使用取余數(shù)哈希算法，保存數(shù)據(jù)到哈希表中。

哈希表的長(zhǎng)度設(shè)置為 15，除數(shù)設(shè)置為 13。

解決沖突的流程：

• 78和26的哈希值都是 0。而因?yàn)?code>78在26的前面，78先占據(jù)哈希表的 0位置。
• 當(dāng)存儲(chǔ) 26時(shí)，只能以 0位置為起始位置，向后尋找空位置，因 1位置沒有被其它數(shù)據(jù)占據(jù)，最終保存在哈希表的1位置。
• 當(dāng)存儲(chǔ)數(shù)字 14時(shí)，通過(guò)哈希算法計(jì)算，其哈希值是1，本應(yīng)該要保存在哈希表中1的位置，因1位置已經(jīng)被26所占據(jù)，只能向后尋找空位置，最終落腳在2位置。

線性探測(cè)法讓發(fā)生哈希沖突的數(shù)據(jù)保存在其它數(shù)據(jù)的哈希位置，如果沖突的數(shù)據(jù)較多，則占據(jù)的本應(yīng)該屬于其它數(shù)據(jù)的哈希位置也較多，這種現(xiàn)象稱為哈希聚集。

查詢流程：

以查詢數(shù)據(jù)14為例。

• 計(jì)算 14的哈希值，得到值為 1 ，根據(jù)哈希值在哈希表中找到對(duì)應(yīng)位置。
• 查看對(duì)應(yīng)位置是否存在數(shù)據(jù)，如果不存在，宣告查詢失敗，如果存在，則需要提供數(shù)據(jù)比較方法。
• 因 1位置的數(shù)據(jù) 26并不等于14。于是，繼續(xù)向后搜索，并逐一比較。
• 最終可以得到結(jié)論14在哈希表的編號(hào)為2的位置。

所以，在查詢過(guò)程中，除了要提供哈希函數(shù)，還需要提供數(shù)據(jù)比較函數(shù)。

刪除流程：

以刪除數(shù)字26為例。

按上述的查詢流程找到數(shù)字26在哈希表中的位置1。

設(shè)置位置1為刪除狀態(tài)，一定要標(biāo)注此位置曾經(jīng)保存過(guò)數(shù)據(jù)，而不能設(shè)置為空狀態(tài)。為什么？

如果設(shè)置為空狀態(tài)，則在查詢數(shù)字14時(shí)，會(huì)產(chǎn)生錯(cuò)誤的返回結(jié)果，會(huì)認(rèn)為14不存在。為什么？自己想想。

編碼實(shí)現(xiàn)線性探測(cè)法：

添加數(shù)據(jù)：

'''
線性探測(cè)法解決哈希沖突
'''
def hash_code(key, hash_table, num):
    # 哈希表的長(zhǎng)度
    size = len(hash_table)
    # 取余數(shù)法計(jì)算哈希值
    hash_val = key % num
    # 檢查此位置是否已經(jīng)保存其它數(shù)據(jù)
    if hash_table[hash_val] is not None:
        # 則從hash_val 之后尋找空位置
        for i in range(hash_val + 1, size + hash_val):
            if i >= size:
                i = i % size
            if hash_table[i] is None:
                hash_val = i
                break
    return hash_val

# 哈希表
hash_table = [None] * 15
src_nums = [25, 78, 56, 32, 88, 26, 73, 81, 14]
for n in src_nums:
    hash_val = hash_code(n, hash_table, 13)
    hash_table[hash_val] = n

print("哈希表中的數(shù)據(jù)：", hash_table)
'''
輸出結(jié)果：
哈希表中的數(shù)據(jù)： [78, 26, 14, 81, 56, None, 32, None, 73, None, 88, None, 25, None, None]
'''

Tip：為了保證當(dāng)哈希值發(fā)生沖突后，如果從沖突位置查到哈希表的結(jié)束位置還是沒有找到空位置，則再?gòu)墓１淼钠鹗嘉恢茫簿褪?code>0位置再搜索到?jīng)_突位置。沖突位置是起點(diǎn)也是終點(diǎn)，構(gòu)建一個(gè)查找邏輯環(huán)，以保證一定能找到空位置。

for i in range(hash_val + 1, size + hash_val):
	 pass

基于線性探測(cè)的數(shù)據(jù)查詢過(guò)程和存儲(chǔ)過(guò)程大致相同：

def get(key, hash_table, num):
    # 哈希表的長(zhǎng)度
    size = len(hash_table)
    # 取余數(shù)法計(jì)算哈希值
    hash_val = key % num
    is_exist = False
    # 檢查此位置是否已經(jīng)保存其它數(shù)據(jù)
    if hash_table[hash_val] is None:
        # 不存在
        return None
    if hash_table[hash_val] != key:
        # 則從hash_val 之后尋找空位置
        for i in range(hash_val + 1, size + hash_val):
            if i >= size:
                i = i % size
            if hash_table[i] == key:
                hash_val = i
                is_exist = True
                break
    else:
        is_exist=True
    if is_exist:
        return hash_val

# 測(cè)試   
res = get(25, hash_table, 13)
print(res)

為了減少數(shù)據(jù)聚集，可以采用增量線性探測(cè)法，所謂增量指當(dāng)發(fā)生哈希沖突后，探測(cè)空位置時(shí)，使用步長(zhǎng)值大于1的方式跳躍式向前查找。目的是讓數(shù)據(jù)分布均勻，減小數(shù)據(jù)聚集。

除了采用增量探測(cè)之外，還可以使用再哈希的方案。也就是提供2個(gè)哈希函數(shù)，第1次哈希值發(fā)生沖突后，再調(diào)用第2個(gè)哈希函數(shù)再哈希，直到?jīng)_突不再產(chǎn)生。這種方案會(huì)增加計(jì)算時(shí)間。

2.4.2 鏈表法

上面所述的沖突解決方案的核心思想是，當(dāng)沖突發(fā)生后，在哈希表中再查找一個(gè)有效空位置。

這種方案的優(yōu)勢(shì)是不會(huì)產(chǎn)生額外的存儲(chǔ)空間，但易產(chǎn)生數(shù)據(jù)聚集，會(huì)讓數(shù)據(jù)的存儲(chǔ)不均衡，并且會(huì)違背初衷，通過(guò)關(guān)鍵字計(jì)算出來(lái)的哈希值并不能準(zhǔn)確描述數(shù)據(jù)正確位置。

鏈表法應(yīng)該是所有解決哈希沖突中較完美的方案。所謂鏈表法，指當(dāng)發(fā)生哈希沖突后，以沖突位置為首結(jié)點(diǎn)構(gòu)建一條鏈表，以鏈表方式保存所有發(fā)生沖突的數(shù)據(jù)。如下圖所示：

鏈表方案解決沖突，無(wú)論在存儲(chǔ)、查詢、刪除時(shí)都不會(huì)影響其它數(shù)據(jù)位置的獨(dú)立性和唯一性，且因鏈表的操作速度較快，對(duì)于哈希表的整體性能都有較好改善。

使用鏈表法時(shí)，哈希表中保存的是鏈表的首結(jié)點(diǎn)。首結(jié)點(diǎn)可以保存數(shù)據(jù)也可以不保存數(shù)據(jù)。

編碼實(shí)現(xiàn)鏈表法：鏈表實(shí)現(xiàn)需要定義 2 個(gè)類，1 個(gè)是結(jié)點(diǎn)類，1 個(gè)是哈希類。

'''
結(jié)點(diǎn)類
'''
class HashNode():
    def __init__(self, value):
        self.value = value
        self.next_node = None

'''
哈希類
'''
class HashTable():
    def __init__(self):
        # 哈希表,初始大小為 15，可以根據(jù)需要?jiǎng)討B(tài)修改
        self.table = [None] * 15
        # 實(shí)際數(shù)據(jù)大小
        self.size = 0

    '''
    存儲(chǔ)數(shù)據(jù)
    key:關(guān)鍵字
    value:值
    '''

    def put(self, key, value):
        hash_val = self.hash_code(key)
        # 新結(jié)點(diǎn)
        new_node = HashNode(value)
        if self.table[hash_val] is None:
            # 本代碼采用首結(jié)點(diǎn)保存數(shù)據(jù)方案
            self.table[hash_val] = new_node
            self.size+=1
        else:
            move = self.table[hash_val]
            while move.next_node is not None:
                move = move.next_node
            move.next_node = new_node
            self.size+=1

    '''
    查詢數(shù)據(jù)
    '''
    def get(self, key):
        hash_val = self.hash_code(key)
        if self.table[hash_val] is None:
            # 數(shù)據(jù)不存在
            return -1

        if self.table[hash_val].value == key:
            # 首結(jié)點(diǎn)就是要找的數(shù)據(jù)
            return self.table[hash_val].value

        # 移動(dòng)指針
        move = self.table[hash_val].next_node
        while move.value != key and move is not None:
            move = move.next_node
        if move is None:
            return -1
        else:
            return move.value

    def hash_code(self, key):
        # 這里僅為說(shuō)明問題，13 的選擇是固定的
        hash_val = key % 13
        return hash_val


# 原始數(shù)據(jù)
src_nums = [25, 78, 56, 32, 88, 26, 39, 82, 14]
# 哈希對(duì)象
hash_table = HashTable()
# 把數(shù)據(jù)添加到哈希表中
for n in src_nums:
    hash_table.put(n, n)
# 輸出哈希表中的首結(jié)點(diǎn)數(shù)據(jù)
for i in hash_table.table:
    if i is not None:
        print(i.value,end=" ")
print("\n-------------查詢-----------")
print(hash_table.get(26))
'''
輸出結(jié)果：
78 14 56 32 88 25 
-------------查詢-----------
26
'''

3.總結(jié)

哈希表是一種高級(jí)數(shù)據(jù)結(jié)構(gòu)，其存儲(chǔ)、查詢性能非常好，在不考慮哈希哈希算法和哈希沖突的時(shí)間復(fù)雜度情況下，哈希查找時(shí)間復(fù)雜度可以達(dá)到常量級(jí)，成為很多實(shí)際應(yīng)用場(chǎng)景下的首選。

研究哈希表，著重點(diǎn)就是搞清楚哈希算法以及如何解決哈希沖突。在算法的世界時(shí)，沒有固定的模式，開發(fā)者可以根據(jù)自己的需要自行設(shè)計(jì)哈希算法。

以上就是一文詳解Python中哈希表的使用的詳細(xì)內(nèi)容，更多關(guān)于Python哈希表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論