哈希表
在学习Python的时候有时候会想，为什么dict和set的查找速度这么快，感觉就像是事先知道要找的元素的位置一样？在学完哈希表之后，这个问题也就够被很好的解释了。
定义
哈希表是一种根据关键码（key）去寻找值（value）的数据映射结构，该结构通过把关键码映射的位置（index）去寻找存放值的地方。 举个例子，也就是像小时候我们经常查的字典一样，比如我们要查找一个字 “一”（value），我们先得到它的拼音“yi”（key），然后就可以在字典的查找目录看到这个字在哪一页（index），最后就得到这个字的详细信息。
实现方法
我们知道，数组的查找速度之所以是O(1)是因为数组里面的元素都有一个下标，所以参考数组的下标，给每个元素一种[逻辑下标]。我们把得到的逻辑下标称为“槽”。
逻辑下标的计算方法采用的是取模运算: h(key) = key % M
哈希冲突
当给出的值取到的“逻辑下标”相同时，哈希冲突便产生了。这里引用一下别人的图
解决办法
遇到这种情况该如何解决呢？我们首先能够想到的是既然冲突了，那能不能够把这些冲突的放进一个链表里面呢？或者重新找过其他地方呢？
- 让数组中 冲突的槽 变成一个链式结构，但是这个方法有个缺点，当链表太长的时候，就会造成时间退化，查找时间会从O(1)退化为O(n)，因此这种方法比较少用。
- 寻找下一个槽，这里给出的是比较常用的二次探查（以二次方作为偏移量）
装载因子（load factor）
load factor = 元素个数 / 哈希表大小， 当装载因子超过0.8时，就要开辟新的空间并重新进行散列了。
重哈希（Rehashing）
重新开辟空间并散列的操作过程就叫做重哈希
代码示例
下面给出实现哈希表的代码
# 哈希表是用数组完成的
class Array(object):
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * 32 # 得到一个空的数组
# 返回value
def __getiter__(self, index):
return self._items[index]
# 重置value
def __setitem__(self, index, value):
self._items[index] = value
def __len__(self):
return self._size
def clear(self, value=None):
for i in range(len(self._items)):
self._items[i] = value
def __iter__(self):
for item in self._items:
yield item
# 定义槽，传入key和value
class Slot(object):
def __init__(self, key, value):
self.key = key
self.value = value
# 定义哈希表
class HashTable(object):
# 首先定义两个全局变量
UNUSED = None
EMPTY = Slot(None, None)
def __init__(self):
self._table = Array(8, init=HashTable.UNUSED)
self.length = 0 # 已使用槽的数量
def __load_factor(self):
"""定义装载因子"""
return self.length / float(len(self._table))
def __len__(self):
return self.length
def __hash__(self):
"""定义哈希函数"""
return abs(hash(key)) % len(self._table)
def _find_key(self, key):
"""根据给出的key，获得index"""
index = self.__hash__(key)
_len = len(self._table)
while self._table[index] is not HashTable.UNUSED: # 这个槽已经被使用过且为空，则重新查找
if self._table[index] is HashTable.EMPTY:
index = (index * 5 + 1) % _len
continue
elif self._table[index].key == key:
return index
else:
index = (index * 5 + 1) % _len
return None
def _slot_can_insert(self, index):
"""判断找到的槽是否可用"""
return (self._table[index] is HashTable.UNUSED or self._table[index] is HashTable.EMPTY)
def _find_slot_for_insert(self, key):
"""查找可以用的槽"""
index = self.__hash__(key)
_len = len(self._table)
while not self._slot_can_insert(index):
index = (index * 5 + 1) % _len
return
index
def __contains__(self, key):
index = self._find_key(key)
return index is not None
def add(self, value, key):
"""往哈希表里添加数据"""
if key in self:
index = self._find_key(key)
self._table[index] = value
return False
else:
index = self._find_slot_for_insert(key)
self._table[index] = Slot(key, value)
self.length += 1
if self.__load_factor() > 0.8:
self.rehash()
return True
def _rehash(self):
"""重哈希"""
old_table = self._table
newsize = len(self._table) * 2
self._table = Array(newsize, HashTable.EMPTY)
self.length = 0
for slot in old_table:
if slot is not HashTable.UNUSED or slot is not HashTable.EMPTY:
index = self._find_slot_for_insert(slot.key)
self._table[index] = slot
self.length += 1
def get(self, key, default=None):
"""取值"""
index = self._find_key(key)
if index is None:
return default
else:
return self._table[index].value
def remove(self, key):
index = self._find_key(key)
if index is None:
return KeyError()
value = self._table[index]
self.length -= 1
self._table[index] = HashTable.EMPTY
return value
def __iter__(self):
for slot in self._table:
if slot not in (HashTable.UNUSED, HashTable.EMPTY):
yield slot
复制代码哈希表是很高效的数据结构，对于新手来讲也比较难理解，我手写了一遍代码，然后再用电脑敲了一遍才基本了解。新手写的，请见谅
