原文鏈接
作為演示代碼，做了以下的簡化處理：
- 鍵類型僅支持
int - 哈希沖突處理使用鏈存儲
- 不設(shè)置裝載因子的處理
- 不對輸入進行校驗
- 默認數(shù)據(jù)大小可以完全放在內(nèi)存中
class Item(object):
def __init__(self, key, value):
self.key = key
self.value = value
class HashTable(object):
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]
def _hash_function(self, key):
return key % self.size
def set(self, key, value):
hash_index = self._hash_function(key)
for item in self.table[hash_index]:
if item.key == key:
item.value = value
return
self.table[hash_index].append(Item(key, value))
def get(self, key):
hash_index = self._hash_function(key)
for item in self.table[hash_index]:
if item.key == key:
return item.value
raise KeyError('Key not found')
def remove(self, key):
hash_index = self._hash_function(key)
for index, item in enumerate(self.table[hash_index]):
if item.key == key:
del self.table[hash_index][index]
return
raise KeyError('Key not found')
簡單說明一下，這里使用list的數(shù)據(jù)結(jié)構(gòu)存放數(shù)據(jù)掀潮，哈希函數(shù)是最簡單的key值對存儲大小取余（這也是為什么key值僅支持int類型的原因）。
需要注意的幾點是寻歧，哈希函數(shù)可以選用更為通用的函數(shù)耘戚，這樣就能夠支持更多的鍵數(shù)據(jù)類型；這里對于哈希沖突的解決采用了鏈式存儲本涕，在極端條件下（即所有哈希值都映射到同一個位置）业汰，set和get方法的時間復(fù)雜度將從O(1)退化到O(n)；隨著數(shù)據(jù)量的增加菩颖，哈希沖突發(fā)生的概率越來越大样漆，所以應(yīng)當(dāng)引入裝載因子進行動態(tài)擴容。
