Python实现哈希表
Python实现哈希表
哈希表:
有一个数组的长度为M,key是要保存的键,h是一个哈希函数 通过%取模使得下标不会超过数组长度 h(key) = key % M M = 9 h(256) = 256 % M = 4 h(313) = 313 % M = 7 h(45) = 45 % M = 0 h(421) = 421 % M = 7 h(137) = 137 % M = 2 冲突
哈希冲突:
不同的key经过h函数计算后得到的下标一样,称为哈希冲突
1.链接法(chaining) 数组中对应的槽变成一个链式结构
2.线性探查(linear probing): 当一个槽被占用,找下一个可用的槽。
h(k,i)=(h′(k)+i)%m,i=0,1,...,m?1h(k,i)=(h′(k)+i)%m,i=0,1,...,m?1
3.二次探查(quadratic probing): 当一个槽被占用,以二次方作为偏移量。
h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,...,m?1h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,...,m?1
4.双重散列(double hashing): 重新计算 hash 结果。
h(k,i)=(h1(k)+ih2(k))%mh(k,i)=(h1(k)+ih2(k))%m
inserted_index_set = set() M = 9 def h(key, M=9): return key % M to_insert = [256, 313, 45, 421, 317] for number in to_insert: index = h(number) first_index = index i = 1 while index in inserted_index_set: # 如果计算发现已经占用,继续计算得到下一个可用槽的位置 print(‘\th({number}) = {number} % M = {index} collision‘.format(number=number, index=index)) index = (first_index + i*i) % M # 根据二次方探查的公式重新计算下一个需要插入的位置 i += 1 else: print(‘h({number}) = {number} % M = {index}‘.format(number=number, index=index)) inserted_index_set.add(index)
装载因子:已经使用的槽数/哈希表大小
5/9 = 0.56
当装载因子超过 0.8 时,就要开辟空间重新进行散列,俗称重哈希
class Array(object): def __init__(self, size=32, init=None): self._size = size self._items = [init] * self._size def __getitem__(self, index): return self._items[index] 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 class Slot(object): """定义一个 hash 表 数组的槽 注意,一个槽有三种状态,看你能否想明白 1.从未使用 HashMap.UNUSED。此槽没有被使用和冲突过,查找时只要找到 UNUSED 就不用再继续探查了 2.使用过但是 remove 了,此时是 HashMap.EMPTY,该探查点后边的元素扔可能是有key 3.槽正在使用 Slot 节点 """ def __init__(self, key, value): self.key, self.value = key, value class HashTable(object): # 表示从未被使用过 UNUSED = None # 使用过,但是被删除了 EMPTY = Slot(None, None) def __init__(self): self._table = Array(8, init=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): return abs(hash(key)) % len(self._table) def _find_key(self, key): # 得到第一个值的位置 index = self._hash(key) _len = len(self._table) # 当这个槽不是未使用过的,才接着往下找;如果是未使用过的,这个key肯定不存在 while self._table[index] is not HashTable.UNUSED: # 槽使用过,但是被删除了 if self._table[index] is HashTable.EMPTY: # cpython解决哈希冲突的一种方式 index = (index*5 + 1) % _len continue elif self._table[index] == key: return index else: index = (index * 5 + 1) % _len return None # 检测槽是否能被插入 def _slot_can_insert(self, index): return (self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED) # 找到能被插入的槽的index def _find_slot_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) return index is not None def add(self, key, value): if key in self: index = self._find_key(key) # 更新值 self._table[index].value = value return False else: index = self._find_slot_insert(key) self._table[index] = Slot(key, value) self.length += 1 if self._load_factor > 0.8: return self._rehash() return True def _rehash(self): oldtable = self._table newsize = len(self._table) * 2 # 新的table self._table = Array(newsize, HashTable.UNUSED) self.length = 0 for slot in oldtable: if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY: index = self._find_slot_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: raise KeyError value = self._table[index].value 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.value
相关推荐
kaixinfelix 2020-10-04
chenfei0 2020-07-30
liqinglin0 2020-07-05
范范 2020-07-04
清溪算法君老号 2020-06-25
MLXY 2020-06-18
深思千年 2020-06-10
码墨 2020-05-29
alicelmx 2020-05-26
ipqtjmqj 2020-05-19
waitwolf 2020-05-12
rongxionga 2020-05-06
yangjingdong00 2020-05-04
kaixinfelix 2020-05-01
fsl 2020-04-29
lickylin 2020-04-25
凌风郎少 2020-04-23
无能力者只知抱怨 2020-04-23