原文链接
作为演示代码，做了以下的简化处理：
- 键类型仅支持
int - 哈希冲突处理使用链存储
- 不设置装载因子的处理
- 不对输入进行校验
- 默认数据大小可以完全放在内存中
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的数据结构存放数据，哈希函数是最简单的key值对存储大小取余（这也是为什么key值仅支持int类型的原因）。
需要注意的几点是，哈希函数可以选用更为通用的函数，这样就能够支持更多的键数据类型；这里对于哈希冲突的解决采用了链式存储，在极端条件下（即所有哈希值都映射到同一个位置），set和get方法的时间复杂度将从O(1)退化到O(n)；随着数据量的增加，哈希冲突发生的概率越来越大，所以应当引入装载因子进行动态扩容。
