本章内容

学习散列表——最有用的基本数据结构之一
学习散列表内部机制——实现、冲突和散列函数。

小结

其实你几乎不用自己去实现散列表，因为常用的编程语言已经提供了非常好的散列表实现，例如python的字典函数。

  • 你可以结合数组和链表来创建散列表。
  • 冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
  • 散列表的查找、插入和删除速度都非常快。
  • 散列表适合用于模拟映射关系。
  • 一旦填装因子超过0.7，就该调整散列表的长度。
  • 散列表可用于缓存数据。
  • 散列表非常适合用于防止重复。

散列表适合于

  • 模拟映射关系；
  • 防止重复；
  • 缓存数据，以免服务器再通过处理来生成它们。

练习

感性认识散列表

  • 一个能够直接报价，而不用查价目表的雇员。

image.png

5.1 散列函数

  1. 散列函数”将每个输入都映射到一个数字并输出这个数字”

image.png

  1. 散列函数的规矩：
    • 就像是单调数列一样，每个输入所映射的数字都是唯一的，且相同的输入所映射的数字是固定不变的。
    • 专业点：将所有的键都映射到一个位置，而理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
  2. 数组和链表都被直接存储在内存中，但散列表更复杂，它使用散列函数来确定元素的存储位置。
  3. 散列表非常有用，也被称为散列映射、映射、字典和关联数组。Python提供的散列表实现为字典，你可以使用函数dict来创建散列表。
  4. 散列表由键和值组成

image.png

5.2 散列表的应用案例

5.2.1 散列表用于查找

手机的通讯录、域名解析DNS resolution

  1. # 创建一个散列表
  2. >> phone_book = dict()  # 等价于 python_book = {}
  3. # 添加键值对
  4. >> phone_book["jenny"] = 10086
  5. >>phone_book["ken"] = 10001
  6. # 查找电话号码
  7. >>print(phone_book("ken")) 
  8. 10001

5.2.2 防止重复

投票站，每人只能投一票。
image.png

  1. # 创建一个散列表，用于记录已投票的人
  2. # 有人来投票时，检查他是否在散列表中
  3. voted = {}
  5. def check_voter(name):
  6.     if voted.get(name):
  7.         print("kick it out")
  8.     else:
  9.         voted[name] = True
  10.         print("let it vote")

5.2.3 将散列表用作缓存

image.png
image.png
读取网页缓存，当没有缓存时，才让服务器去处理，并将服务器放回的数据存储到缓存中。

  1. cache = {}
  3. def get_page(url):
  4.     if cache.get(url):
  5.         return cache[url]   #<=============-返回缓存的数据
  6.     else:
  7.         data = get_data_from_server(url)
  8.         cache[url] = data    #<=============先将数据保存带缓存中
  9.         return data

5.3 冲突

键是有限的，所以键值对也是有限的，当不同的输入足够多时，这就出现了冲突。

  • 最简单的办法是：如果两个键映射到同一个位置，就在这个位置存储一个链表。

image.png

  • 上述解决办法的缺陷：某个位置的链表过长，但事实上散列表并没有填满。这会导致散列表的速度变得很慢。

image.png

5.4 性能

  • 散列表性能与数组和链表同时比较，可以发现，在平均情况下，散列图的性能兼具数组和链表的优点，但是在最糟情况下，散列图的各项速度都很慢。因此，避开冲突尤为重要。

image.png

  • 较低的填充因子、良好的散列函数可以有效降低冲突。
    • 填装因子计算公式： 散列表包含的元素数/位置总数
    • 良好的散列函数：
      • image.png