前言
学习散列表——最有用的基本数据结构之一
学习散列表的内部机制：实现、冲突、散列函数
假如你在一家杂货店上班，有顾客来买东西时，你得在本子中查找价格。如果本子的内容不是按照字母顺序排序的，使用简单查找需要O(n)，如果本子的内容是按首字母顺序排列的，可使用二分查找来找出苹果的价格，时间为O(n)。如果每秒能看十行，则：
本子中的商品数量 O(n) O(logn) 100 10 s 1 s log₂100 = 7行 1000 1.66 min 1 s log₂100 = 10行 10000 16.6 min 2 s log₂100 = 14行
二分查找速度非常快，但是在查找价格时，顾客有时会有怒气，当有一名能够记住所有商品价格的雇员，就不用查找了：问他马上就能知道不管商品有多少，报出任何商品的价格的时间都为O(1)，速度比二分查找还快
本子中的商品数量 简单查找 二分查找 MAGGIE（雇员） O(n) O(logn) O(1) 100 10 s 1 s 立即 1000 1.6 min 1 s 立即 10000 16.6 min 2 s 立即
前面介绍了两种数据结构：数组和链表（其实还有栈，但栈并不能用于查找）你可以使用数组来实现记录商品价格的本子。
（EGGS,2.49） (MILK,1.49) (PEAR,0.79)
这种数组的每个元素包含两项内容：商品名和价格。如果将这个数组按商品名排序，就可使用二分查找在其中查找商品的价格。这样时间将为O(logn)。然而你希望时间为O(1)，那么就需要散列函数
一、散列函数
1.散列函数
无论你给他什么数据，他都还给你一个数字
2.专业术语
散列函数“将输入映射到数字”
3.散列函数必须满足一些要求
①它必须是一致的
假设你输入Apple时得到的是4，那么每次输入Apple时，得到的都必须为4
②它应将不同的输入映射到不同的数字
最理想的情况，将不同的输入映射到不同的数字，如果一个散列函数不管输入是什么都返回1，他就不是好的散列函数
4.运行机制
①首先创建一个空数组，将在这个数组中存储的商品价格
②将Apple作为输入交给散列函数
③散列函数输出为3，因此我们将苹果的价格存储到数组的索引处
④下面将牛奶的价格存储到数组中，所以将牛奶作为散列函数的输入
⑤散列函数的输出为0，因此我们将牛奶的价格存储在索引0处
⑥不断的重复这个过程，最终整个数组将填满价格
⑦现在假设需要知道鳄梨(avocado)的价格，你无需在数组中查找，只需将avocado作为输入交给散列函数
⑧它将告诉你鳄梨的价格存储在索引4处，果然，你在那找到了！
AVOCADO = 1.49
散列函数准确地指出了价格的存储位置，你根本不用查找，因为：
①散列函数总是将同样的输入映射到相同索引
②散列函数将不同的输入映射到不同的索引
③散列函数知道数组有多大，只返回有效的索引
5. 散列表
你结合使用散列函数和数组创建了一种被称为散列表的数据结构。散列表是第一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
在你将学习的复杂数据结构中，散列表可能是最有用的，也被称为散列映射、映射、字典和关联数组。散列表的速度很快。
你可能不需要自己去实现散列表，任一优秀的语言都提供了散列表实现。Python提供的散列表实现为字典，可使用函数dict来创建散列表。
创建散列表book：
book = dict() book["apple"] = 0.67 book["milk"] = 1.49 book["avocado"] = 1.49 print(book)
{'apple': 0.67, 'milk': 1.49, 'avocado': 1.49}
查询鳄梨的价格：
print(book["avocado"]) #--> 1.49
二、应用案例
1. 将散列表用于查找
手机都内置了方便的电话簿，其中每个姓名都有对应的电话号码，该电话簿需要以下功能：
1> 添加联系人及其电话号码
2> 通过输入联系人来获悉其电话号码
创建电话簿：
phone_book = dict() #或 phone_book = {} phone_book["jenny"] = 8765309 phone_book["emergency"] = 911 #添加联系人
散列表被用于大海捞针式的查找。
APIT.IO ---> 173.255.248.55
GOOGIE.com ---> 74.125.239.133
FACEBOOK.com ---> 173.252.120.6
例如像访问http://adit.io这样的网站时，计算机必须将adit.io转换为IP地址。无论访问哪个网站，其网址都必须转换为IP地址。这不就是将网址映射到IP地址，非常适合使用散列表，这个过程被称为DNS解析，散列表是提供这种功能的方式之一。
2.防止重复
假设你负责管理一个投票站，每人只能投一票，如何避免重复投票呢？
有人来投票时，你询问他的全名，并将其与已投票者名单进行比对。如果名字在名单中，就说明这个人已经投过票了，因此将他拒之门外，否则就将他的名字加到名单中，并让他投票。现在假设有很多人投过了票，因此名单非常长。每次有人来投票时，你都得浏览这个长长的名单，但有种更好的办法，就是用散列表。
创建一个散列表用于记录：
voted = {} value = voted.get("tom")
如果“tom”在散列表中，函数get将返回它；否则返回None，用这个函数来检查来投票的人是否投过票
代码如下：
voted = {} def check_voter(name): if voted.get(name): print("kick them out!") else: voted[name] = True print("let them vote!") #测试 check_voter("tom") check_voter("milk") check_voter("milk")
let them vote! let them vote! kick them out!
如果将他们存储在了列表中，这个函数的速度终将变得非常慢，因为它必须使用简单查找搜索整个列表
但将它们存储在了散列表中，散列表让你能迅速知道来投票的人是否投过票。使用散列表来检查是否重复，速度非常快。
3. 将散列表用作缓存
如果你在网站工作，可能听说过进行缓存是一种不错的做法。下面简单介绍其中的原理。假设你访问网站facebook.com
1> 你向Facebook的服务器发出请求
2> 服务器做些处理，生成一个网页并将其发送给你
3> 你获得一个网页
Facebook服务器必须为数以百万的用户提供服务，每个人的几秒钟累积起来就相当多了，有没有办法让Facebook的服务器少做些工作，从而提高Facebook的访问速度呢？
假设你有个侄女总是问你有关星球的问题，你每次都在Google搜索，再告诉他答案。但如果你记住了问题的答案，就可以直接告诉她。这就是缓存的工作原理：网站将数据记住，而不再重新计算。
当你登陆了Facebook，你每次访问facebook.com，其服务器都要考虑你感兴趣的是什么内容。但如果没有登录，看到的将是登录页面。
Facebook被反复要求做同样的事情：“当我注销时，请向我显示主页。”他不让服务器去生成主页，而是将主页存储起来，并在需要时将其直接发送给用户。
这就是缓存。
4. 缓存有两个优点
1> 用户能够更快的看到网页
2> Facebook需要做的工作更少
缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！
Facebook不仅缓存主页，还缓存About页面，Contact页面，Terms and Conditions页面等众多其他的页面。因此他需要将页面URL映射到页面数据。
具体代码：
cache = {} def get_page(url): if cache.get(url): return cache[url] #返回缓存的数据 else: data = get_data_from_server(url) cache[url] = data #先将数据保存到缓存中 return data
仅当URL不在缓存中时，你才让服务器做一些处理，并将处理生成的数据存储到缓存中，再返回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进行处理了。
三、冲突
首先，前面有一个善意的谎言：散列表函数总是将不同的键映射到数组的不同位置
实际上，几乎不可能编写出这样的散列函数。
假设有一个数组，它包含26个位置
而你使用的散列函数非常简单，他按字母表顺序分配数组的位置
①如果你要将苹果的价格存储到散列表中，分配给你的是第一个位置
②接下来，你要将香蕉的价格存储到散列表中，分配给你的是第二个位置
③现在你要将鳄梨的价格存储到散列表中，分配给你的又是第一个位置，因为它们都是A开头，但是这个位置已经存储给苹果的价格了
这种情况被称为冲突：给两个键分配的位置相同
将鳄梨的价格存储到这个位置，将覆盖苹果的价格。冲突很糟糕，必须要避免。处理冲突的方式很多，最简单的办法如下：
如果两个键映射到了同一个位置，就在这个位置存储一个链表
Apple和avocado映射到了同一个位置，因此在这存储一个链表，查询苹果的价格时，速度要慢些，因为要在相应链表中找到Apple，而香蕉就会相对很快。
经验教训：
①散列函数很重要，前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表不同的位置
②散列表很长，散列表的速度将急剧下降
好的散列表很少导致冲突
四、性能
1. 散列表的性能：
在平均情况下，散列表执行各种操作的时间都为O(1)
散列表的性能
| 平均情况 | 最糟情况 | 数组 | 链表 | |
| 查找 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | O(n) | O(1) |
| 删除 | O(1) | O(n) | O(n) | O(1) |
散列表中查找所花费的时间为常量时间
一条水平线，意味着无论散列表包含一个元素还是10亿个元素，从中获取数据所需的时间相同。最糟糕的情况下，散列表所有操作的运行时间都为O(n)---线性时间
平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟糕情况下，散列表的各种操作速度都很慢。因此在使用散列表时，避开最糟糕情况至关重要。
2. 要避免冲突，需要有
1> 较低的填装因子
2> 良好的散列函数
五、如何实现散列表（非必读）
1. 填装因子
散列表的填装因子很容易计算： 散列表包含的元素数 / 位置总数
散列表使用数组来存储数据，因此你需要计算数组中被占用的位置
当散列表的填装因子为1，如果这个列表只有50个位置（要填100个），填装因子将为2.填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整常度。例如：
假设有一个像下面这样相当满的散列表：
你需要调整它的长度，首先创建一个更长的新数组：通常将数组增长一倍
接下来，你需要使用函数hash将所有的元素都插入到这个新的散列表中
填装因子越低，发生冲突的可能性越小，散列表的性能越高
一个不错的经验规则：一旦填装因子大于0.7，就调整散列表的长度
调整散列表长度的工作需要很长时间！但平均而言，即使考虑到调整长度所需的时间，散列表操作所需的时间也为O(1)
2. 良好的散列函数
糟糕的散列函数让值扎堆，导致大量的冲突
什么样的散列函数是良好的呢？可以研究一下SHA函数（最后一章将做简要的介绍）
六、小结
编程语言提供了散列表实现
散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型，你可能很快会发现自己经常在使用它
①你可以结合散列函数和数组来创建散列表
②冲突很糟糕，应使用可以最大限度减少冲突的散列函数
③散列表的查找、插入和删除速度都非常快
④散列表适合用于模拟映射关系
⑤一旦填装因子超过0.7，就该调整散列表长度
⑥散列表可用于缓存数据（例如，在web服务器上）
⑦散列表非常适合用于防止重复
