改不完的 Bug，写不完的矫情。公众号 杨正友 现在专注移动基础开发 ，涵盖音视频和 APM,信息安全等各个知识领域；只做全网最 Geek 的公众号，欢迎您的关注！
什么是散列表?
一个函数。我们可以把它定义成hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。
散列表和数组有什么关系?
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
散列函数代码实现?
如何解决散列冲突?
一、开放定址法
为产生冲突的地址H(key)求得一个新的地址序列：Hi =（H(key)+ di）% m （i=1，2，3，...，m-1），其中H(key)为哈希函数，m为表长，di称为增量序列。
1. 增量序列实现方式
- 线性探测再散列: di = 1，2，3，...，m-1
- 二次探测再散列: di = 12，-12，22，-22，32，-32，...，k2（k<=m/2）
- 伪随机探测再散列： di = 伪随机数序列
2. 案例分析
在长度为11的哈希表中，已填入关键字 17，29，60的记录，哈希函数为：H(key) = key % 11
2.1 计算结果
- H(17) = 17 % 11 =6。故将关键字“17”存在下标为6的位置，位置空着，所以存入未冲突。
- H(29) = 29 % 11 =7。故将关键字“29”存在下标为7的位置，位置空着，所以存入未冲突。
- H(60) = 60 % 11 =5。故将关键字“60”存在下标为5的位置，位置空着，所以存入未冲突。
2.2 散列表的存储状态
这时存入第四个关键字：38.计算：H(38) = 38 % 11 = 5。出现冲突，下标为5的位置已存有60。
2.3 实现方式
- 1.线性探测再散列
开始尝试逐次追加di = 1，2，3，...，m-1 - 得到地址6 => 依然冲突
得到地址7 => 仍然冲突，
得到地址8 => 不冲突，存入。
2.二次探测再散列
尝试追加 di = 12，-12，22，-22，32，-32，...，k2（k<=m/2）
首先，追加12，地址6仍然冲突。
再，追加-12，地址4无冲突，可以存入
3.伪随机探测再散列
假设伪随机数为9,H(38) = (38+9)%11 = 3。地址3不冲突，存入。
使用范围
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
缺陷
- 1.用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。
- 2.使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间
二、链表法
概念
将所有哈希地址相同的记录都链接在同一链表中，以此来解决冲突,
举例
已知一组关键字为（19，14，23，01，20，68，84，27，55，11，10，79）。 则按哈希函数H(key) = key % 13
- 在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中
- 当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。
- 当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
优点
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表
三、再哈希法
概念
产生冲突时计算另一个哈希函数（散列函数）的地址，直到冲突不再发生为止
优点
这种方法不容易产生聚集。
缺点
增加了计算的时间成本。
四、建立公共溢出区：
概念
把冲突的都放在另一个溢出表中，而不会存在基本表里。
具体操作
这也是解决哈希冲突的一种办法，假设哈希函数的值域为[0，m-1]，那就创建一个[0，m-1]的基本数组，每块内存存放一个记录，另外创建一个溢出数组，一旦发生哈希冲突，就将冲突的值添加至溢出表。
如何设计散列函数?
- 散列函数的设计不能太复杂
- 散列函数生成的值要尽可能随机并且均匀分布
什么是装载因子?
当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
装载因子计算公式
如何避免低效扩容?
- 1.我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
- 2.当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。
散列函数有什么特点?
- 确定性
如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。 - 散列碰撞（collision）
散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。 - 不可逆性
一个哈希值对应无数个明文，理论上你并不知道哪个是。 - 混淆特性
输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
散列函数时间复杂度
