网站首页优化方案/重庆网站seo外包
《Python数据结构与算法分析》（第二版）
字典是最有用的Python集合之一，使用键-值对来存储数据，并且字典是无序的，键是不重复的。键用来查找关联的值，这一概念常常称作映射。
映射支持以下操作：
- Map()创建一个空的映射，它返回一个空的映射集合。
- put(key, val)往映射中加入一个新的键-值对。如果键已经存在，就用新值替换旧值。
- get(key)返回key对应的值。如果可以不存在，则返回None。
- del 通过del map[key]这样的语句从映射中删除键-值对。
- len()返回映射中存储的键-值对的数目。
- in通过key in map这样的语句，在键存在时返回True，否则返回False。
使用字典的一大优势是，给定一个键，能很快地找到其关联的值。为了提高搜索效率，可以使用散列搜索算法，其时间复杂度可以达到O(1)。
1.使用两个列表创建HashTable类来实现映射抽象数据类型。
class HashTable:def __init__(self):# HashTable类的构造方法self.size = 11# 散列表的初始大小设置为素数，可以尽可能提高冲突处理算法的效率self.slots = [None] * self.size# 设置一个名为slots的列表，用来存储键，并初始化为Noneself.data = [None] * self.size# 设置一个名为data的列表，用来存储值，并初始化为None - 实现名为hashfunction的散列函数，要存储或查找的键对散列表的大小进行取余运算。处理冲突时，用一个名为rehash的散列函数实现‘加1’再散列函数的线性探测法。
def hashfunction(self, key, size):return key % sizedef rehash(self, oldhash, size):return (oldhash+1) % size# oldhash为hashfunction()返回的值，但由于该位置上已经有了键，所以发生了冲突，需要使用rehash确定下一个位置- 实现put函数， 除非键已经在self.slots中，否则总是可以分配一个位置（槽位）。首先使用hashfunction函数计算初始的散列值，如果对应的位置上已有元素，就循环运行rehash函数，直到遇见一个空槽。如果槽中已有这个键，就用新值替换旧值。
def put(self, key, data):hashvalue = self.hashfunction(key, len(self.slots))# 计算散列值，即key所对应的槽位if self.slots[hashvalue] == None:# 如果该槽位为空，则在该位置添加键-值对self.slots[hashvalue] = keyself.data[hashvalue] = dataelse:if self.slots[hashvalue] == key: # 如果键已经存在self.data[hashvalue] = data # 用新值替换旧值else: # 该槽位被其他键占用了，计算下一个散列值nextslotnextslot = self.rehash(hashvalue, len(self.slots))# 循环运行rehash直到遇见一个空槽，或发现键已经存在while self.slots[nextslot] != None and \self.slots[nextslot] != key:nextslot = self.rehash(nextslot, len(self.slots))if self.slots[nextslot] == None: # 找到一个空槽位self.slots[nextslot] = keyself.data[nextslot] = dataelse: # 键已经存在self.data[nextslot] = data- 实现get函数，先计算初始散列值，如果值不在初始散列值对应的槽中，就是用rehash确定下一个位置。如果遇到初始槽，就说明已经检查完所有可能的槽，并且元素必定不存在。
def get(self, key):startslot = self.hashfunction(key, len(self.slots))data = Nonestop = False# 一旦遇到初始槽，则赋值为True，停止搜索found = Falseposition = startslot# 如果一开始初始槽就为空，则说明元素必定不存在while self.slots[position] != None and \not found and not stop:if self.slots[position] == key:# 如果找到keyfound = Truedata = self.data[position]# 取出key所对应的值else:# 如果上一个position已经被其他键占用，则计算下一个位置position = self.rehash(position, len(self.slots))if position == startslot:# 如果遇到初始槽，则搜索失败，元素不存在stop = True# 停止搜索return data# 返回data，如果搜素失败，则返回None# 重载__getitem__和__setitem__, 以通过[]进行访问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])
print(H[17])
H[20] = 'duck'
print(H.data)
print(H[99])