接觸過 Python 的小伙伴應(yīng)該對【字典】這一數(shù)據(jù)類型都了解吧

雖然 Python 沒有顯式名稱為“哈希表”的內(nèi)置數(shù)據(jù)結(jié)構(gòu)，但是字典是哈希表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

在 Python 中，字典的鍵（key）被哈希，哈希值決定了鍵對應(yīng)的值（value）在字典底層數(shù)據(jù)存儲中的位置

那么今天我們就來看看哈希表的原理以及如何實(shí)現(xiàn)一個(gè)簡易版的 Python 哈希表

ps：文中提到的 Python 指的是 CPyhton 實(shí)現(xiàn)

何為哈希表？

哈希表（hash table）通常是基于“鍵-值對”存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)

哈希表的鍵（key）通過哈希函數(shù)轉(zhuǎn)換為哈希值（hash value），這個(gè)哈希值決定了數(shù)據(jù)在數(shù)組中的位置。這種設(shè)計(jì)使得數(shù)據(jù)檢索變得非?？?/p>

舉個(gè)例子，下面有一組鍵值對數(shù)據(jù)，其中歌手姓名是 key，歌名是 value

+------------------------------+
|   Key        |   Value       |
+------------------------------+
| Kanye        | Come to life  |
| XXXtentacion | Moonlight     |
| J.cole       | All My Life   |
| Lil wanye    | Mona Lisa     |
| Juice WRLD   | Come & Go     |
+------------------------------+

如果我們想要將這些鍵值對存儲在哈希表中，首先需要將鍵的值轉(zhuǎn)換成哈希表的數(shù)組的索引，這時(shí)候就需要用到哈希函數(shù)了

哈希函數(shù)是哈希表實(shí)現(xiàn)的主要關(guān)鍵，它能夠處理鍵然后返回存放數(shù)據(jù)的哈希表中對應(yīng)的索引

一個(gè)好的哈希函數(shù)能夠在數(shù)組中均勻地分布鍵，盡量避免哈希沖突（兩個(gè)鍵返回了相同的索引）

哈希函數(shù)是如何處理鍵的，這里我們創(chuàng)建一個(gè)簡易的哈希函數(shù)來模擬一下（實(shí)際上哈希函數(shù)要比這復(fù)雜得多）

def simple_hash(key, size):
    return ord(key[0]) % size

這個(gè)簡易版哈希函數(shù)將歌手名（即 key）首字母的 ASCII 值與哈希表大小取余，得出來的值就是歌名（value）在哈希表中的索引

那這個(gè)簡易版哈希函數(shù)有什么問題呢？聰明的你一眼就看出來了：容易出現(xiàn)碰撞。因?yàn)椴煌逆I的首字母有可能是一樣的，就意味著返回的索引也是一樣的

例如我們假設(shè)哈希表的大小為 10 ，我們以上面的歌手名作為鍵然后執(zhí)行 simple_hash(key, 10) 得到索引

可以看到，由于Juice WRLD 和 J.cole 的首字母都一樣，哈希函數(shù)返回了相同的索引，這里就發(fā)生了哈希碰撞

雖然幾乎不可能完全避免任何大量數(shù)據(jù)的碰撞，但一個(gè)好的哈希函數(shù)加上一個(gè)適當(dāng)大小的哈希表將減少碰撞的機(jī)會

當(dāng)出現(xiàn)哈希碰撞時(shí)，可以使用不同的方法（例如開放尋址法）來解決碰撞

應(yīng)該設(shè)計(jì)健壯的哈希函數(shù)來盡量避免哈希碰撞

我們再來看其他的鍵，Kanye 通過 simple_hash() 函數(shù)返回 index 5，這意味著我們可以在索引 5 （哈希表的第六個(gè)元素）上找到 其鍵 Kanye 和值Come to life

哈希表優(yōu)點(diǎn)

在哈希表中，是根據(jù)哈希值（即索引）來尋找數(shù)據(jù)，所以可以快速定位到數(shù)據(jù)在哈希表中的位置，使得檢索、插入和刪除操作具有常數(shù)時(shí)間復(fù)雜度 O(1) 的性能

與其他數(shù)據(jù)結(jié)構(gòu)相比，哈希表因其效率而脫穎而出

不但如此，哈希表可以存儲不同類型的鍵值對，還可以動態(tài)調(diào)整自身大小

Python 中的哈希表實(shí)現(xiàn)

在 Python 中有一個(gè)內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，它實(shí)現(xiàn)了哈希表的功能，稱為字典

Python 字典（dictionary，dict）是一種無序的、可變的集合（collections），它的元素以 “鍵值對（key-value）”的形式存儲

字典中的 key 是唯一且不可變的，這意味著它們一旦設(shè)置就無法更改

my_dict = {"Kanye": "Come to life", "XXXtentacion": "Moonlight", "J.cole": "All My Life"}

在底層，Python 的字典以哈希表的形式運(yùn)行，當(dāng)我們創(chuàng)建字典并添加鍵值對時(shí)，Python 會將哈希函數(shù)作用于鍵，從而生成哈希值，接著哈希值決定對應(yīng)的值將存儲在內(nèi)存的哪個(gè)位置中

所以當(dāng)你想要檢索值時(shí)，Python 就會對鍵進(jìn)行哈希，從而快速引導(dǎo) Python 找到值的存儲位置，而無需考慮字典的大小

my_dict = {}
my_dict["Kanye"] = "Come to life" # 哈希函數(shù)決定了 Come to life" 在內(nèi)存中的位置
print(my_dict["Alice"]) # "Come to life" 

可以看到，我們通過方括號[key]來訪問鍵對應(yīng)的值，如果鍵不存在，則會報(bào)錯(cuò)

print(my_dict["Kanye"])  # "Come to life" 
# Raises KeyError: "Drake"
print(my_dict["Drake"])

為了避免該報(bào)錯(cuò)，我們可以使用字典內(nèi)置的 get() 方法，如果鍵不存在則返回默認(rèn)值

print(my_dict.get('Drake', "Unknown")) # Unknown

在 python 中實(shí)現(xiàn)哈希表

首先我們定義一個(gè) HashTable 類，表示一個(gè)哈希表數(shù)據(jù)結(jié)構(gòu)

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None]*size
    def _hash(self, key):
        return ord(key[0]) % self.size

在構(gòu)造函數(shù) __init__() 中：

• size 表示哈希表的大小
• table是一個(gè)長度為 size 的數(shù)組，被用作哈希表的存儲結(jié)構(gòu)。初始化時(shí)，數(shù)組的所有元素都被設(shè)為 None，表示哈希表初始時(shí)不含任何數(shù)據(jù)

在內(nèi)部函數(shù) _hash() 中，用于計(jì)算給定 key 的哈希值。它采用給定鍵 key 的第一個(gè)字符的 ASCII 值，并使用取余運(yùn)算 % 將其映射到哈希表的索引范圍內(nèi)，以便確定鍵在哈希表中的存儲位置。

然后我們接著在 HashTable 類中添加對鍵值對的增刪查方法

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None]*size
    def _hash(self, key):
        return ord(key[0]) % self.size
    def set(self, key, value):
        hash_index = self._hash(key)
        self.table[hash_index] = (key, value)
    def get(self, key):
        hash_index = self._hash(key)
        if self.table[hash_index] is not None:
            return self.table[hash_index][1]
        raise KeyError(f'Key {key} not found')
    def remove(self, key):
        hash_index = self._hash(key)
        if self.table[hash_index] is not None:
            self.table[hash_index] = None
        else:
            raise KeyError(f'Key {key} not found')

其中，set() 方法將鍵值對添加到表中，而 get() 該方法則通過其鍵檢索值。該 remove() 方法從哈希表中刪除鍵值對

現(xiàn)在，我們可以創(chuàng)建一個(gè)哈希表并使用它來存儲和檢索數(shù)據(jù)：

# 創(chuàng)建哈希表
hash_table = HashTable(10)
# 添加鍵值對
hash_table.set('Kanye', 'Come to life')
hash_table.set('XXXtentacion', 'Moonlight')
# 獲取值
print(hash_table.get('XXXtentacion'))  # Outputs: 'Moonlight'
# 刪除鍵值對
hash_table.remove('XXXtentacion')
# 報(bào)錯(cuò)： KeyError: 'Key XXXtentacion not found'
print(hash_table.get('XXXtentacion'))

前面我們提到過，哈希碰撞是使用哈希表時(shí)不可避免的一部分，既然 Python 字典是哈希表的實(shí)現(xiàn)，所以也需要相應(yīng)的方法來處理哈希碰撞

在 Python 的哈希表實(shí)現(xiàn)中，為了避免哈希沖突，通常會使用開放尋址法的變體之一，稱為“線性探測”（Linear Probing）

當(dāng)在字典中發(fā)生哈希沖突時(shí)，Python 會使用線性探測，即從哈希沖突的位置開始，依次往后查找下一個(gè)可用的插槽（空槽），直到找到一個(gè)空的插槽來存儲要插入的鍵值對。

這種方法簡單直接，可以減少哈希沖突的次數(shù)。但是，它可能會導(dǎo)致“聚集”（Clustering）問題，即一旦哈希表中形成了一片連續(xù)的已被占用的位置，新元素可能會被迫放入這片區(qū)域，導(dǎo)致哈希表性能下降

為了緩解聚集問題，假若當(dāng)哈希表中存放的鍵值對超過哈希表長度的三分之二時(shí)（即裝載率超過66%時(shí)），哈希表會自動擴(kuò)容

最后總結(jié)一下：

• 在哈希表中，是根據(jù)哈希值（即索引）來尋找數(shù)據(jù)，所以可以快速定位到數(shù)據(jù)在哈希表中的位置
• Python 的字典以哈希表的形式運(yùn)行，當(dāng)我們創(chuàng)建字典并添加鍵值對時(shí)，Python 會將哈希函數(shù)作用于鍵，從而生成哈希值，接著哈希值決定對應(yīng)的值將存儲在內(nèi)存的哪個(gè)位置中
• Python 通常會使用線性探測法來解決哈希沖突問題

到此這篇關(guān)于Python 哈希表的實(shí)現(xiàn)——字典的文章就介紹到這了,更多相關(guān)Python 哈希表字典內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論