0204：数据结构-散列表
本文依照学习难度，分成入门、进阶两个部分。
入门部分以直观、易于理解为主；进阶部分重点在于概念、推导等。
目录
入门
散列表是什么
散列表，又被成为散列映射、映射、字典和关联数组。由键和值组成，直观来看是：
查询某一种水果时，可以立即获得对应的价格。
散列表和数组、链表有什么关系呢？
一句话来说，散列函数和数组共同创建了散列表
数组和链表都是被直接映射到内存的
散列表则使用散列函数来确定元素的存储位置
也就是散列表是，数组中的元素多经过一道函数计算后（散列函数），再映射到内存。
是数组的拓展
到这一步为止，知道了有散列函数这么个神奇的事物存在，后面再继续相似了解。
前面的例子，希望实现的是：当查找苹果时，会告诉我们苹果的价格是3.
换句说，我们有一个放价格数据的数组：
希望能够通过散列函数将水果准确映射到价格数组上
如上图，通过散列函数即可得到索引，而得到了索引就可以充分利用数组随机查找的优点。
关键在于散列函数
散列函数想要实现上述获取索引的功能，至少要满足
一致性： “苹果”永远映射为1，每次映射都得到相同的索引值
差异性：“苹果”和“梨”应该映射的索引不相同。保证不同的输入映射到不同的数字。
为保证效率，散列函数还应知道数组有多大，像上面长度为3的数组，返回的索引应在0~2之间，不会返回无效索引，如100
散列表的应用
1、DNS解析（DNS resolution）
非常常见的将网址映射到IP地址。
2、防止重复 比如投票，防止重复投票。每个人投票，就将这个人的姓名映射到一个固定的数值上，如果这个人曾经投过票就很容易查询出来。
3、缓存
缓存就是网站将数据记住，而不是每次收到用户打开的命令都重新计算。
这时候就是将页面URL映射到页面数据上，如下图：
缓存是一种常用的加速方式，所有大型网站都是要缓存，而缓存的数据则存储在散列表中。
在实际使用散列表时，需要考虑性能等因素，情况会更复杂。
因此，如何实现散列函数，接下来做进一步的探讨。
实现散列函数的一些算法
- SHA算法（secure hash algorithm，安全散列算法）
这是一个系列，包括SHA-0，SHA-1，SHA-2，SHA-3
实现结果例如 “hello” ==> "2cf24db"
可通过SHA判断两个文件是否相同
计算密码的散列值
目前最安全的密码散列函数是 brypt 局部不敏感 Simbash 局部敏感（检查两项内容相似程度时很有用）
- Diffie-Hellman 密钥交换
对消息加密
使用两个密钥：公钥和私钥。
有人向你发消息时，使用公钥对其进行加密。加密的消息只有自己的私钥才能打开，公钥可以用各种途径传播。
优良的散列函数
良好的散列函数让数组中的值呈均匀分布
散列函数的结果必须是均匀分布，这很重要
它们的映射范围必须尽可能的大
最糟糕的散列函数莫过于将所有输入都映射到散列表的同一位置
填装因子越低，发生冲突的可能性越小，散列表的性能越高
填装因子 = 列表包含的元素数/位置总数
经验规则：一旦填装因子大于0.7，就调整散列表的长度
当然调整长度的开销也挺大。
进阶
[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)