注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为6分钟。
映射抽象数据类型及Python实现
在Python字典中，我们可以通过“键”访问对应的“值”。字典这种键值关联的方法称为映射（map）。
字典就是这样一种抽象数据类型映射（ADT Map）结构。ADT Map结构是键-值关联的集合。在这个集合中，关键码具有唯一性，我们可以通过关键码唯一确定一个数据值。
抽象数据类型映射（ADT Map）定义的操作如下：
- Map()——创建一个空映射，返回空映射对象。
- put(key, val)——将key-val关联对加入到映射中。若映射中key已存在，则val将替换key的旧关联值。
- get(key)——给定key，返回关联的数据值。如key不存在，则返回None.
- del——通过del map[key]的语句形式删除key-val关联。
- len()——返回映射中key-val关联的数目。
- in——通过key in map的语句形式，返回key是否存在于关联中，布尔值。
字典的优势在于，给定关键码key，能够很快找到关联的数据值data。
为了达到快速查找的目标，需要一个支持高效查找的ADT（Abstract Data Type，抽象数据类型）实现——可以采用列表数据结构加顺序查找或者二分查找，当然，更为合适的是，使用散列表来实现，因可以达到最快O(1)的性能。
实现抽象数据类型映射
下面，我们用一个Hash Table类来实现ADT Map，该类包含了两个列表作为成员：一个是slot列表，用于保存key；另一个是平行的data列表，用于保存数据项。
在slot列表查找到一个key的位置以后，在data列表对应的相对位置的数据项即为关联数据。
保存key的列表就作为散列表来处理，这样可以迅速查找指定的key。
注意散列表的大小，虽然可以是任意数，但考虑到要让冲突解决算法能有效工作，应该选择为素数。
hashfunction方法采用了简单求余方法来实现散列函数，而冲突解决则采用线性探测“加1”再散列函数。
综上所述，ADT Map的put、get等方法的实现的完全代码如下：
# 实现抽象数据类型映射的实现。
class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
# ADT Map的put方法。
def put(self, key, data):
hashvalue = self.hashfunction(key)
if self.slots[hashvalue] == None: # key不存在的情况。
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key: # key存在的情况。
self.data[hashvalue] = data # 替换。
else:
nextslot = self.rehash(hashvalue)
# 散列冲突，再散列，直到找到空槽或者key。
while self.slots[nextslot] != None and self.slots[nextslot] != key:
nextslot = self.rehash(nextslot)
if self.slots[nextslot] == None:
self.slots[nextslot] = key
self.data[nextslot] = data
else:
self.data[nextslot] = data # 替换。
def hashfunction(self, key):
return key % self.size
def rehash(self, oldhash):
return (oldhash + 1) % self.size
# ADT Map的get方法。
def get(self, key):
startslot = self.hashfunction(key) # 标记散列值为查找起点。
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and not found and not stop:
# 找到key，直到空槽或者回到起点。
if self.slots[position] == key:
found = True
data = self.data[position]
else: #未找到key，再散列继续找。
position = self.rehash(position)
if position == startslot:
stop = True # 没找到key，回到起点，停下来了。
return data
# 通过特殊方法实现[]访问。
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, data):
self.put(key, data)
H = HashTable()
H[54]="cat"
H[26]="dog"
H[93]="lion"
H[17]="tiger"
H[77]="bird"
H[31]="cow"
H[44]="goat"
H[55]="pig"
H[20]="chicken"
print(H.slots)
print(H.data)
print(H[20])
<<<
[77, 44, 55, 20, 26, 93, 17, None, None, 31, 54]
['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
chicken
<<<
散列的算法分析
散列在最好的情况下，可以提供O(1)即常数级的时间复杂度的查找性能。当然，因为实际情况中不免有散列冲突的存在，所以查找比较次数就没这么简单。
评估散列冲突的最重要信息就是负载因子λ，一般来说：
- 如果λ较小，散列冲突的几率就小，数据项通常会保存在其所属的散列槽中；
- 如果λ较大，意味着散列表填充较满，冲突会越来越多，冲突解决也越来越复杂，也就需要更多的比较来找到空槽；如果采用数据项链的方式，则意味着每条链上的数据项增多。
如果采用线性探测的开放定址法来解决冲突问题（λ在0~1之间），则：
- 成功的查找，平均需要比对次数为：(1+1/(1-λ))/2。
- 不成功的查找，平均比对次数为：(1+(1/(1-λ))^2)/2。
如果采用数据项链法来解决冲突问题（λ可大于1），则：
- 成功的查找，平均需要比对次数为：1+λ/2。
- 不成功的查找，平均比对次数为：λ。
To be continued.
