使⽤python实现哈希表、字典、集合操作
哈希表
哈希表（Hash Table, ⼜称为散列表），是⼀种线性表的存储结构。哈希表由⼀个直接寻址表和⼀个哈希函数组成。哈希函数h(k)将元素关键字k作为⾃变量，返回元素的存储下标。
简单哈希函数：
除法哈希：h(k) = k mod m乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1
假设有⼀个长度为7的数组，哈希函数h(k) = k mod 7，元素集合{14, 22, 3, 5}的存储⽅式如下图：
哈希冲突
由于哈希表的⼤⼩是有限的，⽽要存储的值的总数量是⽆限的，因此对于任何哈希函数，都会出现两个不同的元素映射到同⼀个位置上的情况，这种情况叫做哈希冲突。
⽐如：h(k) = k mod 7, h(0) = h(7) = h(14) = ...
解决哈希冲突--开放寻址法
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值
线性探查：如果位置i被占⽤，则探查i+1, i+2,...⼆次探查：如果位置i被占⽤，则探查i+12, i-12, i+22, i-22,...⼆度哈希：有n个哈希函数，当使⽤第⼀个哈希函数h1发⽣冲突时，则尝试使⽤h2, h3,...
解决哈希冲突--拉链法
拉链法：哈希表每⼀个位置都连接⼀个链表，当冲突发⽣时，冲突的元素将被加到该位置链表的最后。
哈希表的实现
class Array(object):
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * 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 表数组的槽(slot 这⾥指的就是数组的⼀个位置)
hash table 就是⼀个数组，每个数组的元素（也叫slot槽）是⼀个对象，对象包含两个属性 key 和 value。
注意，⼀个槽有三种状态，看你能否想明⽩。相⽐链接法解决冲突，探查法删除⼀个 key 的操作稍微复杂。
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) # 保持 2*i 次⽅
self.length = 0
@property
def _load_factor(self):
# load_factor 超过 0.8 重新分配
return self.length / float(len(self._table))
def __len__(self):
return self.length
# 进⾏哈希
def _hash(self, key):
return abs(hash(key)) % len(self._table)
# 查key
def _find_key(self, key):
"""
解释⼀个 slot 为 UNUSED 和 EMPTY 的区别
因为使⽤的是⼆次探查的⽅式，假如有两个元素 A，B 冲突了，
⾸先A hash 得到是 slot 下标5，A 放到了第5个槽，之后插⼊ B 因为冲突了，所以继续根据⼆次探查⽅式放到了 slot下标8。然后删除 A，槽 5 被置为 EMPTY。然后我去查 B，
第⼀次 hash 得到的是槽5，但是这个时候我还是需要第⼆次计算 hash 才能到 B。
但是如果槽是 UNUSED 我就不⽤继续了，我认为 B 就是不存在的元素。这个就是 UNUSED 和 EMPTY 的区别。
"""
origin_index = index = self._hash(key) # origin_index 判断是否⼜⾛到了起点，如果查⼀圈了都不到则⽆此元素
_len = len(self._table)
while self._table[index] is not HashTable.UNUSED:
if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY，继续寻下⼀个槽
index = (index * 5 + 1) % _len
if index == origin_index:
break
continue
if self._table[index].key == key: # 到了key
return index
else:
index = (index * 5 + 1) % _len # 没有到继续下⼀个位置
if index == origin_index:
break
return None
# 能插⼊的槽
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 _slot_can_insert(self, index):
return self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED # in operator，实现之后可以使⽤ in 操作符判断
def __contains__(self, key):
index = self._find_key(key)
return index is not None
# 添加元素
def add(self, key, value):
if key in self: # update
index = self._find_key(key)
self._table[index].value = 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.UNUSED)
self.length = 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)
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.EMPTY, HashTable.UNUSED):
yield slot.key
哈希表的使⽤
h = HashTable()
h.add('a', 0)
h.add('b', 1)
h.add('c', 2)
print(len(h)) # 3
('a')) # 0
('b')) # 1
('hehe')) # None
('a')) # None
print(sorted(list(h))) # ['b', 'c']
字典
字典是另⼀种可变容器模型，且可存储任意类型对象。
字典的每个键值key=>value对⽤冒号：分割，每个键值对之间⽤逗号，分割，整个字典包括在花括号{}中 ，格式如下所⽰：d = {key1 : value1, key2 : value2 }
基于哈希表实现字典
class Array(object):
def __init__(self, size=32, init=None):
self._size = size
self._items = [init] * 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 表数组的槽(slot 这⾥指的就是数组的⼀个位置)
hash table 就是⼀个数组，每个数组的元素（也叫slot槽）是⼀个对象，对象包含两个属性 key 和 value。
注意，⼀个槽有三种状态，看你能否想明⽩。相⽐链接法解决冲突，探查法删除⼀个 key 的操作稍微复杂。
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) # 保持 2*i 次⽅
self.length = 0
@property
def _load_factor(self):
# load_factor 超过 0.8 重新分配
return self.length / float(len(self._table))
def __len__(self):
return self.length
# 进⾏哈希
def _hash(self, key):
return abs(hash(key)) % len(self._table)
# 查key
def _find_key(self, key):
"""
解释⼀个 slot 为 UNUSED 和 EMPTY 的区别
因为使⽤的是⼆次探查的⽅式，假如有两个元素 A，B 冲突了，
⾸先A hash 得到是 slot 下标5，A 放到了第5个槽，之后插⼊ B 因为冲突了，所以继续根据⼆次探查⽅式放到了 slot下标8。然后删除 A，槽 5 被置为 EMPTY。然后我去查 B，
第⼀次 hash 得到的是槽5，但是这个时候我还是需要第⼆次计算 hash 才能到 B。
但是如果槽是 UNUSED 我就不⽤继续了，我认为 B 就是不存在的元素。这个就是 UNUSED 和 EMPTY 的区别。
"""
origin_index = index = self._hash(key) # origin_index 判断是否⼜⾛到了起点，如果查⼀圈了都不到则⽆此元素
_len = len(self._table)
while self._table[index] is not HashTable.UNUSED:
if self._table[index] is HashTable.EMPTY: # 注意如果是 EMPTY，继续寻下⼀个槽
index = (index * 5 + 1) % _len
if index == origin_index:
break
continue
if self._table[index].key == key: # 到了key
return index
else:
index = (index * 5 + 1) % _len # 没有到继续下⼀个位置
if index == origin_index:
break
return None
# 能插⼊的槽
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
python获取数组长度return index
# 槽是否能插⼊
def _slot_can_insert(self, index):
return self._table[index] is HashTable.EMPTY or self._table[index] is HashTable.UNUSED
# in operator，实现之后可以使⽤ in 操作符判断
def __contains__(self, key):
index = self._find_key(key)
return index is not None
# 添加元素
def add(self, key, value):
if key in self: # update
index = self._find_key(key)
self._table[index].value = 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
# 槽不够时，重哈希
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论