哈希表（Hash table，也叫散列表），是根據鍵（Key）而直接訪問數據在內存中的儲存位置（又叫做存儲桶，Buckets）的數據結構。也就是說，它通過計算一個關于鍵值的函數（哈希函數，Hash function，也叫散列函數），將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度，存放記錄的數組就叫做哈希表。最直觀的例子，我們的手機通訊錄中，如果王某某的電話號碼是12345678910，我們只需要記個王某某：12345678910，以后直接找王某某就可以找到他的電話號碼了。哈希表可以在O(1)時間內進行讀寫操作（插入與搜索），就是最大的優勢。（leetcode對應章節）

哈希表的關鍵思想是使用哈希函數將鍵映射到存儲桶。

1.當我們插入一個新的鍵時，哈希函數將決定該鍵應該分配到哪個桶中，并將該鍵存儲在相應的桶中；
2.當我們搜索一個鍵時，哈希表將使用相同的哈希函數來查找對應的桶，并只在特定的桶中進行搜索。

如果兩個不同的鍵經過哈希函數映射之后，得到的值相同，這叫做哈希沖突或者碰撞（collision），解決方法后面再講。

如何設計一個哈希表呢？最重要的肯定是哈希函數，完美的哈希函數是鍵與桶一 一對應，沒有任何沖突或者空間浪費的，然而實際基本不可能達到。哈希表又分為兩種：哈希集合和哈希映射，所以設計題就分為設計哈希集合和設計哈希映射。

705. 設計哈希集合

集合是用來存儲非重復值的數據結構，操作就三種：插入、查找（是否存在）、刪除。做設計題必須留意鍵key的取值范圍，此處為0到10的六次方，因此會有對于桶數（數組的長度）與桶大小（數組中一個格子的大小）的權衡。

最極端的，開辟一個超大數組（桶數為10的六次方、桶大小為1），方案如下：

class MyHashSet:def __init__(self):"""Initialize your data structure here."""self.HashSet = [False] * 1000001def add(self, key: int) -> None:self.HashSet[key] = Truedef remove(self, key: int) -> None:self.HashSet[key] = Falsedef contains(self, key: int) -> bool:"""Returns true if this set contains the specified element"""return self.HashSet[key]

初始化數組每一格都是False，插入就是對應格變為True，查找就是對應格的值（True or False），刪除就是對應格變為False。

如果希望平衡桶數與桶大小相同，可以得到以下方案：

class MyHashSet:def __init__(self):self.table = [[0] * 1000 for _ in range(1001)] # 注意是1001def hash(self, key):return key // 1000, key % 1000 # 獲取key在數組中的位置索引def add(self, key):hashkey, hashpos = self.hash(key) # 獲取key在數組中的位置索引self.table[hashkey][hashpos] = 1def remove(self, key):hashkey, hashpos = self.hash(key)self.table[hashkey][hashpos] = 0def contains(self, key):hashkey, hashpos = self.hash(key)return (self.table[hashkey] != []) and (self.table[hashkey][hashpos] == 1)

顯然，這里我們開辟了一個長度 length 為1000的數組，哈希函數為取整除，沖突的解決方法是讓一個格子不止存放一個 key，而是用數組把所有可能沖突的 key 都存放進來，只需要桶數（1000） * 桶大小（1001）的結果大于10的六次方即可。

hashkey是key經過哈希函數（取整除）映射后的值，可能會重復（沖突），用于確定key存放在哪個桶；

hashpos是key經過取余數后的值，可知不同的key得到相同的整除值后，它的余數一定是不同的，所以可以確定key存放在某一個桶中的哪個位置。

706. 設計哈希映射

映射是用來存儲 (key, value) 鍵值對的數據結構，設計思路與集合類似，如下：

class MyHashMap(object):def __init__(self):self.map = [[-1] * 1000 for _ in range(1001)] # 注意是1001def hash(self, key):return key // 1000, key % 1000 # 獲取key在數組中的位置索引def put(self, key, value):hashkey, hashpos = self.hash(key)self.map[hashkey][hashpos] = valuedef get(self, key):hashkey, hashpos = self.hash(key)return self.map[hashkey][hashpos]def remove(self, key):hashkey, hashpos = self.hash(key)self.map[hashkey][hashpos] = -1

這里我使用的哈希函數還是取整除，桶數還是1001，桶大小還是1000。

注意：之所以是 range(1001) 而不是 1000 的原因是10的六次方除以 1000 會得到 1000，而 range(1000) 最大是999，導致 1000 溢出。

下面是更好的方法！！

705. 設計哈希集合

class MyHashSet:def __init__(self):self.buckets = 1001self.table = [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef add(self, key: int) -> None:hash_key = self.hash(key)if key in self.table[hash_key]:returnself.table[hash_key].append(key)def remove(self, key: int) -> None:hash_key = self.hash(key)if key not in self.table[hash_key]:returnself.table[hash_key].remove(key)def contains(self, key: int) -> bool:hash_key = self.hash(key)return key in self.table[hash_key]

只需要設計哈希函數找到桶的位置即可，讓桶作為一個空的列表，里面的元素動態增加。

706. 設計哈希映射

class MyHashMap:def __init__(self):self.buckets = 1001self.table = [[] for _ in range(self.buckets)]def hash(self, key):return key % self.bucketsdef put(self, key: int, value: int) -> None:hash_key = self.hash(key)for item in self.table[hash_key]:if key == item[0]:item[1] = valuereturnself.table[hash_key].append([key, value])def get(self, key: int) -> int:hash_key = self.hash(key)for item in self.table[hash_key]:if key == item[0]:return item[1]return -1def remove(self, key: int) -> None:hash_key = self.hash(key)for i, item in enumerate(self.table[hash_key]):if key == item[0]:self.table[hash_key].pop(i)return

同理

總結

以上是生活随笔為你收集整理的哈希表（散列表）基础概念与经典题目（Leetcode题解-Python语言）之上——原理与设计的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。