字典是最有用的Python集合之一。字典是存储键-值对数据类型。键用来查找关联的值，这个概念常常被称作映射。
映射抽象数据类型定义如下。它是将键和值关联起来的无序集合，其中的键是不重复的，键和值之间是一一对应的关系。映射支持以下操作。
（1）Map()创建一个空的映射，它返回一个空的映射集合。
（2）put(key，val)往映射中加入一个新的键-值对。如果键已经存在，就用新值替换旧值。
（3）get(key)返回key对应的值。如果可以不存在，则返回None。
（4）del通过del、map[key]这样的语句从映射中删除键-值对。
（5）len()返回映射中存储的键-值对的数目。
（6）in通过key in map这样的语句，在键存在时返回True，否则返回False。
使用字典的一大优势是，给定一个键，能很快找到其关联的值。为了提供这种快速查找能力，需要能支持高校搜索对的实现方案。虽然可以使用列表进行顺序搜索或二分搜索，但用散列表更好，这是因为散列搜索算法的时间复杂度可以达到O(1)。
代码清单使用两个列表创建HashTable类，以此实现映射抽象数据类型。其中，名为slots的列表用语存储键，名为data的列表用于存储值。量列表中的键与值一一对应。散列表的初始大小是11.尽管初始大小可以任意指定，但选用一个素数很重要，这样尽可能地提高冲突处理算法效率。
在代码清单中，hashfunction实现了简单的取余函数。处理冲突时，采用“加1”再散列函数的线性探测法。put函数假设，除非键已经在self.slots中，否则总是可以分配一个空槽。该函数计算初始的散列值，如果对应的槽中已经有元素，就循环运行rehash函数，直到遇见一个空槽。如果槽中已有这个键，就用新的值替换旧值。
同理，get函数也先计划计算初始散列值，入代码清单所示。如果值不在初始散列值对应的槽中，就使用rehash确定下一个位置。注意，第50行确保搜索一定能结束，因为不会回到初始槽中。如果遇到初始值，就说明已经检查完多有的可能的槽，并且元素必定不存在。
HashTable类的最后两个方法提供了额外的字典功能。我们重载__getitem__和__setitem__，以通过[ ]进行访问。这意味着创建HashTable类之后，就可以使用熟悉的索引运算符了。
1 class HashTable: 2 def __init__(self): 3 self.size = 11 4 self.slots = [None] * self.size 5 self.data = [None] * self.size 6 7 def put(self, key, data): 8 hashvalue = self.hashfunction(key, len(self.slots)) 9 10 if self.slots[hashvalue] == None: 11 self.slots[hashvalue] = key 12 self.data[hashvalue] = data 13 14 else: 15 if self.slots[hashvalue] == key: 16 self.data[hashvalue] = data 17 18 else: 19 nextslot = self.rehash(hashvalue, len(self.slots)) 20 while self.slots[nextslot] != None and self.slots[nextslot] != key: 21 nextslot = self.rehash(nextslot, len(self.slots)) 22 23 if self.slots[nextslot] == None: 24 self.slots[nextslot] = key 25 self.data[nextslot] = data 26 else: 27 self.data[nextslot] = data 28 29 def hashfunction(self, key, size): 30 return key % size 31 32 def rehash(self, oldhash, size): 33 return (oldhash + 1) % size 34 35 def get(self, key): 36 startslot = self.hashfunction(key, len(self.slots)) 37 38 data = None 39 stop = False 40 found = False 41 position = startslot 42 43 while self.slots[position] != None and not found and not stop: 44 if self.slots[position] == key: 45 found = True 46 data = self.data[position] 47 48 else: 49 position = self.rehash(position, len(self.slots)) 50 if position == startslot: 51 stop = True 52 53 return data 54 55 def __getitem__(self, key): 56 return self.get(key) 57 58 def __setitem__(self, key, data): 59 self.put(key, data) 60 61 if __name__ =="__main__": 62 H = HashTable() 63 H[54] = "cat" 64 H[26] = "dog" 65 H[93] = "lion" 66 H[17] = "tige" 67 H[77] = "bird" 68 H[31] = "cow" 69 H[44] = "goat" 70 H[55] = "pig" 71 H[20] = "chicken" 72 print(H.slots) 73 print(H.data) 74 H[20] = "duck" 75 print(H.data) 76 print(H[20])