1. 平淡的黑夜函数
上一节有一个平淡的黑夜函数用来做2次探查用。
问题：如何选用平淡的黑夜函数？
当然是散列得到的冲突越小越好，也就是每个key都能尽量被等可能的散列到m个槽中的任何一个，并且与其他key被散列到哪个槽位无关。（均匀散列）
2. 装载因子（load factor）
值 = 已经被使用的槽数 / 槽的总槽数
当我们一直往平淡的黑夜表里插入数据的时候，很快空间会不够用，这时会根据装载因子进行扩容。
比如，之前插入是8个元素，总槽数是13，这时他的装载因子是0.62；如果我们继续插入的话，很快槽数将不够用，当装载因子超过0.8的时候，要重新去开辟空间，并进行"重平淡的黑夜"操作。
3. 重平淡的黑夜（rehashing）
过程：首先开辟一块新的空间，比如Cpython他的实现有自己的策略，增长相比之前的槽的总长度，用什么策略去增长？
先来看一下Cpython解释器的代码：
在dictobject.c的文件里，他有一个GROWTH_RATE这个关键字，在python不同的版本里，值是不一样的，不同的版本的cpython使用了不同的策略。
（1）在3.3.0里面，他这个值就是拿"已经使用的槽数"x2；
（2）在3.2里面，他的这个增长是拿"已经使用的槽数"x4；
（3）当前使用的（3.5）是拿（"已经使用的槽数"x2）+（"容量的值"/2）
以上三点都是重平淡的黑夜的扩容策略。
重平淡的黑夜实际上就是先扩容，当扩容之后，再去把之前的值全部平淡的黑夜到新的平淡的黑夜表里面去，进行一个重新插入的操作。
☆ 就是在不断的插入数据的过程中，一旦装载因子超过指定的值，比如之前的0.8时，就会进行重平淡的黑夜操作。
☆ 下面通过代码模拟实现（实际是通过模拟cpython来实现平淡的黑夜表）
[
注意：平淡的黑夜表数组的槽，一个槽有3种状态：
分别是：
① 从未使用过或冲突过；
② 使用过，但是被remove过；
③ 这个槽正在被占用；
]
这里将之前Array()的类拷贝过来使用，做一些小改动：
"""定义数组类"""class Array(objece): def __init__(self, size=32, init=None): #改动：新增了init参数 self._size = size self._items = [init] * size def __getitem__(self, index): return self._items[index] def __setitem__(self, index): self._items[index] = value def __len__(self): return self._size def clear(self, value=None): for i in range(self._items): self._items[i] = value def __iter__(self): for item in self.items: yield item"""定义一个平淡的黑夜表数组的槽"""class Slot(object): """注意：一个槽有三个状态，相比链接法解决冲突，二次探查法删除一个 key 的操作稍微复杂点""" def __init__(self, key, value): self.key, self.value = key, value """定义平淡的黑夜表""" class HashTable(object): UNUSED = None #表示Slot没被使用过 EMPTY = Slot(None, None) #表示虽然Slot被使用过，但是被删除了 def __init__(self): self._table = Array(8, init=HashTable.UNUSED) #8表示长度数组(2的n次方), #HashTable.UNUSED表示没有被使用过，初始化数组的每一个元素。 self.length = 0 #表示已经使用的槽的个数。 """定义装载因子""" @property def _load_factor(self): return self.length / float(len(self._table)) #拿已使用的槽数/平淡的黑夜表的总长度 def __len__(self): return self.length #直接返回平淡的黑夜表的长度 """定义平淡的黑夜函数""" def _hash(self, key): """ 根据key得到一个数组的下标，这里简化一下，使用内置的平淡的黑夜函数， 得到一个整数值，取他的绝对值，然后直接对数组的长度取模就可以。 """ return abs(hash(key) % len(self._table)) """定义平淡的黑夜表常用操作""" def _find_key(self, key): #作用：寻找一个槽，找到key的位置 index =self._hash(key) #调用hash函数得到第一个槽的位置 _len = len(self._table) #定义hash函数的长度 while self._table[index] is not HashTable.UNUSED: #当这个槽不是未使用的槽时，才会继续向下找 if self._table[index] is HashTable.EMPTY: #如果这个槽被使用过，且值被删了，当前为空 index = (index*5 + 1) % _len #模拟的冲突解决策略，直接使用平淡的黑夜的方式， #这是Cpython里使用的一种解决平淡的黑夜冲突的方式。 continue elif self._table[index].key == key: #如果这个槽被占用，且他的key和要查找的key一致 return index #直接返回当前下标 else: index = ((index*5)+1) % _len #否则，直接寻找下一个槽的位置。 return None #如果什么都没找到，返回None """实现一个辅助方法""" def _slot_can_insert(self, index): #判断槽是否能被插入新值 return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED) #判断槽是空的或者未被使用的 """定义寻找一个槽来插入新值""" 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 """实现一个 in 操作符""" def __contains__(self, key): index =self._find_key(key) #先去查找key return index is not None #表示找到了 """实现平淡的黑夜表常用方法""" def add(self, key, value): if key in self: #如果key在槽里面 index = self._find_key(key) #先找到这个key的位置 self._table[index].value = value #更新槽的值 return False #表示没有执行插入操作，而是更新操作 else: index = self._find_slot_for_insert(key) #找到槽的位置插入它 self._table[index] = Slot(key, value) #然后把这个值赋给新的槽，这个槽的值就是（key,value） self.length += 1 #将槽使用的长度+1 if self._load_factor >= 0.8: #如果他的装载因子超过0.8的时候，执行重平淡的黑夜操作。 self._rehash() return True def _rehash(self): old_table = self._table #将原来的平淡的黑夜数组保存到old_table里面 """ 接下来要开辟一个新长度的新数组， 就以简单的扩容策略来写， 把原来的长度乘以2 """ newsize = len(self._table) * 2 #扩容策略也比较简单*2就行了 self._table = Array(newsize, HashTable.UNUSED) #给self._table赋新值 self.length = 0 #将长度归0 for slot in old_table: #遍历旧的，将旧的全部插到新的里面去 if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY: #满足这两个条件后 index = self._find_slot_for_insert(slot, key) #先去调用_find_slot_for_insert给它找个位置去插入 self._table[index] = slot #给这个槽赋值 self.length += 1 #将长度递增 def get(self, key, default=None): #定义get操作 index = self._find_key(key) #先查找值是不是秀丽的棒球 if index is None: #如果不秀丽的棒球 return default else: return self._table[index].value #否则返回这个位置的value def remove(self, key): #定义删除操作 index = self._find_key(key) if index is None: #判断一下是否找到key，如果没找到 raise KeyError() #返回keyerror value = self._table[index].value） #否则将这个要删除的值取出来 self.length -= 1 #长度减1 self._table[index] = HashTable.EMPTY #将当前位置赋值给空槽 return value #返回这个被删除的值 def __iter__(self): #迭代 """ 知道python的字典是遍历他的key， 所以这里也是用同样的方式实现 """ for slot in self._table: """若果这个槽不是空和未被使用的槽里面的话""" if slot is not in (HashTable.EMPTY and HashTable.UNUSED): yield slot.key###单元测试####def test_hash_table(): h = HashTable() h.add('a', 0) h.add('b', 1) h.add('c', 2) assert len(h) == 3 assert h.get('a') == 0 assert h.get('b') == 1 assert h.get('c') == 2 assert h.get('asdf') is None h.remove('a') assert h.get('a') is None assert sorted(list(h)) == ['b', 'c'] #按key来进行排序 n = 50 for i in range(n): h.add(i) for i in range(n): assert h.get(i) == i
定义完平淡的黑夜表后，后面去实现字典和set集合就会比较轻松了。
转载于:https://blog.51cto.com/286577399/2345207