（《算法图解》）
一 散列函数
无论你给它什么数据，它都还你一个数字。即散列函数“将输入映射到数字”。
eg: “hello” —>2
“Apple”—>4
它必须是一致的，即输入“Apple”时得到的是4，那么每次输入“Apple”时得到的必须为4。
它应将不同的输入映射到不同的数字。
二 散列表
1.将“apple”作为输入交给散列函数，输出为3（通过散列函数决定将苹果价格存放在数组中哪个位置），因此将苹果的价格（0.67元）存储到数组的索引3处。
2.将“milk”作为输入交给散列函数，输出为0，因此将牛奶的价格（1.49元）存储到数组的索引0处。
3.散列函数准确的指出了价格的存储位置。
4.散列表也被称为散列映射、映射、字典和关联数组。
5.大部分语言中都提供了散列表实现。python中提供的散列表实现为字典。
book = dict()#创建散列表book["apple"] = 0.67#一个苹果的价格为0.67元book["milk"] = 1.49#一盒牛奶的价格为1.49元book["avocado"] = 1.49print(book)输出如下：
让我们来查询鳄梨的价格：
输出如下：
散列表（字典）由键和值组成。在上述的散列表中，键为商品名，值为商品价格。散列表将键映射到值。
三 应用案列
1 将散列表用于查找
输出：
散列表被被用于大海捞针式的查找，比如访问网站时，计算机必须将网址转化为ip地址
Google.com–>74.125.239.133
2 防止重复
假设你负责一个投票站，每人只能投一票，为了避免重复投票，你先询问这个人的名字，并在已投票名单中对比，如果投过了，就不让他投了。
为此，首先创建一个散列表，用于记录已投票的人：
有人来投票时，检查他是否在散列表中：
value = voted.get("Tom")如果Tom在散列表中，函数get返回True，否则返回None。
完整代码：
输出如下：
如果你将已投票者的姓名存储在列表中，这个函数的速度终将变得非常慢，因为它必须使用简单查找搜索整个列表。
但这里将它们存储在散列表中，让你迅速知道来投票的人是否投过票。
3 将散列表用作缓存
假如你有个沙雕舍友总问你问题，火星离地球多远？水星呢？月球呢？你每次都要打开浏览器搜索，再告诉他答案，这要花费个几分钟。但是你很快记住了月球距离地球238900公里，因此你就不用再去花几分钟搜索，可以直接告诉他答案。
这就是缓存的原理：网站将数据记住，而不再重新计算。
需要将页面url映射到页面数据：
facebook.com/about -->About页面的数据
facebook.com–>主页的数据
zjdds访问facebook的页面时，它首先检查散列表中是否存储了该页面。
仅当url不在缓存中时，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返回它。当下次有人请求该url时，就可以直接发送缓存中的数据，而不用再让服务器进行处理了。
四 冲突
若你选择的散列函数为按照首字母映射，
apple和avocado就会冲突
最简单的方法： 如果两个键映射到了同一个位置，就在这个位置存储一个链表。
但是，假如销售的商品全部都是a开头，那么第一个位置就包含一个很长的链表，后面的散列表都是空的。这种情况散列表的情况急剧下降。
所以散列函数的选择很重要。
五 性能
平均状况 /最糟状况/ 数组/ 链表查找O（1）/ O(n) /O(1)/O(n)插入O（1）/ O(n)/ O(n) / O(1)删除O（1）/ O(n)/ O(n) / O(1)O(1)被称为常量时间，并不意味着马上，而是说不管散列表多大，所需的时间都相同。
意味着无论散列表包含一个元素还是10亿个元素，从中获取数据所需的时间都相同。
实际上，常量时间——从数组中获取一个元素所需的时间就是固定的：不管数组多大，从中获取一个元素所需的时间都是相同的。
平均状况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快。
最糟情况下，各种操作速度都很慢。
为此要避免冲突，需要：
1.装填因子（度量散列表中有多少位置是空的）
公式：散列表包含的元素数/位置总数
一旦装填因子大于0.7，就调整散列表长度
2.良好的散列函数
良好的散列函数让数组中的值成均匀分布
糟糕的散列函数让值扎堆，导致大量的冲突