“形影不离”的散列表与链表
1. 特性
散列表和链表，经常会被放在一起使用。原因是散列表虽然支持高效的数据插入、删除、查找操作，但是散列后的数据都是无序存储的，无法支持按照某种顺序快速地遍历数据。散列表是动态的数据结构，如果每次按序访问都要拷贝到数组，排序然后在遍历，效率太低了。而支持动态创建的链表刚好能解决散列表的有序遍历问题。
2. 散列表的实现
在讲解散列表与链表的应用之前，我们先来解决上一篇文章遗漏的散列表的实现问题。散列表的原理并复杂，但是一个高效的哈希函数可能数学家精心研究的结果。这里我们不弄的太过复杂，我们介绍两种哈希表的实现，一种使用分离链表，另一种使用包含线性探测的开放寻址。
虽然这两种实现解决冲突的方法差异很大，但是也存在很多共性，因此我们基于 MapBase 扩展一个新的 HashMapBase 类。
2.1 HashMapBase
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
from abc import abstractmethod
from random import randrange
class HashMapBase(MapBase):
def __init__(self, cap=11, p=109345121):
self._table = cap * [None]
self._n = 0
# 压缩函数 MAD 的参数
# [(ai + b) mod p] mod N
# - N: 散列表内部数组的大小
# - p: 比 N 大的素数
# - a，b 是从区间 [0, p-1] 任意选择的整数，并且 a > 0
self._prime = p # p
self._scale = 1 + randrange(p - 1) # a
self._shift = randrange(p) # b
def _hash_function(self, k):
return (hash(k) * self._scale + self._shift) % self._prime % len(self._table)
def __len__(self):
return self._n
def __getitem__(self, k):
j = self._hash_function(k)
return self._bucket_setitem(j, k)
def __setitem__(self, key, value):
j = self._hash_function(key)
self._bucket_setitem(j, key, value)
if self._n > len(self._table) // 2:
self._resize(2 * len(self._table) - 1)
def __delitem__(self, key):
j = self._hash_function(key)
self._bucket_delitem(j, key)
self._n -= 1
def _resize(self, c):
old = list(self.items())
self._table = c * [None]
self._n = 0
for k, v in old:
self[k] = v
@abstractmethod
def _bucket_getitem(self, j, k):
pass
@abstractmethod
def _bucket_setitem(self, j, k, v):
pass
@abstractmethod
def _bucket_delitem(self, j, k):
pass
|
2.2 ChainHashMap
分离链表法的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class ChainHashMap(HashMapBase):
def _bucket_getitem(self, j, k):
bucket = self._table[j]
if bucket is None:
raise KeyError('Key error' + repr(k))
return bucket[k]
def _bucket_setitem(self, j, k, v):
if self._table[j] is None:
# 可以使用链表，红黑树，跳表优化,
# 示例使用的是 <11 映射> 实现的 UnsortedTableMap
self._table[j] = UnsortedTableMap()
oldsize = len(self._table[j])
self._table[j][k] = v
if len(self._table[j]) > oldsize:
self._n += 1
def _bucket_delitem(self, j, k):
bucket = self._table[j]
if bucket is None:
raise KeyError('Key error' + repr(k))
del bucket[k]
def __iter__(self):
for bucket in self._table:
if bucket is not None:
for key in bucket:
yield key
|
2.3 ProbeHashMap
线性探测的开放寻址法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
class ProbeHashMap(HashMapBase):
# 标记删除的哨兵
_AVAIL = object()
def _is_available(self, j):
return self._table[j] is None or self._table[j] is ProbeHashMap._AVAIL
def _find_slot(self, j, k):
# 位置探测
first_avail = None
while True:
if self._is_available(j):
if first_avail is None:
first_avail = j
# 查找失败，探测到的第一个空位置
if self._table[j] is None:
return False, first_avail
# 查找成功，元素 k 的位置
elif k == self._table[j]._key:
return True, j
j = (j + 1) % len(self._table)
def _bucket_getitem(self, j, k):
found, s = self._find_slot(j, k)
if not found:
raise KeyError('Key error' + repr(k))
return self._table[s]._value
def _bucket_setitem(self, j, k, v):
found, s = self._find_slot(j, k)
if not found:
self._table[s] = self._Item(k, v)
self._n += 1
else:
self._table[s]._value = v
def _bucket_delitem(self, j, k):
found, s = self._find_slot(j, k)
if not found:
raise KeyError('Key error' + repr(k))
self._table[s] = self._AVAIL
def __iter__(self):
for j in range(len(self._table)):
if not self._is_available(j):
yield self._table[j]._key
|
3. 散列表与链表
3.1 LRU 缓存淘汰算法
借助于散列表和链表可以实现时间复杂度降为 O(1)的 LRU 缓存淘汰算法。这里我们使用 Python 内置的 dict 与 链表一章实现的 DoubleLink。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
class LRU(object):
def __init__(self, capacity=3):
assert capacity <= 0
self.capacity = capacity
self.num = 0
self.link = DoubleLink()
self.node_mp = {}
def _re_cache(self, value):
"""
:return: 值存在更新缓存
"""
if value in self.node_mp:
node = self.node_mp[value]
self.link.delete_node(node)
self.node_mp[value] = self.link.insert_head(value)
return True
return False
def cache(self, value):
if not self._re_cache(value):
if self.num < self.capacity:
# 缓存未满
self.node_mp[value] = self.link.insert_head(value)
self.num += 1
else:
# 缓存满
node_tail = self.link._tail._pre
del self.node_mp[node_tail._element]
self.link.delete_node(node_tail)
self.node_mp[value] = self.link.insert_head(value)
def __str__(self):
r = []
s = self.link._head._next
while s != self.link._tail:
r.append(str(s._element))
s = s._next
return '-->'.join(r)
lru = LRU()
lru.cache(1)
lru.cache(2)
lru.cache(3)
print lru
lru.cache(1)
print lru
lru.cache(1)
print lru
lru.cache(4)
print lru
|
参考:
