05_hash_tables

第5章 散列表（哈希表）

1. 散列函数

散列函数是这样的函数：即无论你给他什么数据，它都还你一个数字。

散列函数必须满足一些要求：

1. 它必须是一致的

   每次相同的输入，都必须得到相同的输出。

2. 它应将不同的输入映射到不同的数字

   最理想的情况是，将不同的输入映射到不同的数字。

• Python提供的散列表实现为字典，可以使用dict函数来创建散列表
• 散列表由键和值组成，它将键映射到值

示例：

book = dict()       # 等价于book = {}
book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.49
print(book)
print(book["avocado"])

输出：

{'apple': 0.67, 'milk': 1.49, 'avocado': 1.49}
1.49

---

2. 散列表的应用

1. 用于查找

   如 电话簿

2. 防止重复

   示例如下：

   def check_voter(voted, name):
       if voted.get(name):
           print("Kick him/her out!")
       else:
           voted[name] = True
           print("Let him/her vote!")

3. 用作缓存

   如 页面缓存

……

---

3. 冲突

冲突（collision）：给两个键分配的位置相同。

冲突处理：方法很多，最简单的方法是

如果两个键映射到了同一个位置，就在这个位置存储一个链表。

注意：

• 散列函数很重要。最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
• 如果散列表存储的链表很长，散列表的速度将急剧下降。但是如果使用的散列函数很好，这些链表就不会很长。

---

4. 性能

在平均情况下，散列表执行各种操作的时间都为常量时间O(1)。

它不是说马上，而是说不管散列表多大，所需时间都相同。

在最坏情况下，散列表所有操作时间都为O(n)

---	散列表（最佳）	散列表（最坏）	数组	链表
查找	O(1)	O(n)	O(1)	O(n)
插入	O(1)	O(n)	O(n)	O(1)
删除	O(1)	O(n)	O(n)	O(1)

所以使用散列表避开最坏情况十分重要，为此需要避免冲突。避免冲突需要：

• 较低的填装因子
• 良好的散列函数

1. 填装因子

   填装因子 = 散列表元素数 / 位置总数

   填装因子度量的是散列表中有多少位置是空着的。

   一般填装因子大于0.7时，就需要调整散列表的长度。

2. 散列函数

   本书不做讨论。SHA函数可以作为散列函数。