数据结构系列: Hash散列表

改不完的 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. 增量序列实现方式

1. 线性探测再散列: di = 1，2，3，...，m-1
2. 二次探测再散列: di = 12，-12，22，-22，32，-32，...，k2（k<=m/2）
3. 伪随机探测再散列： di = 伪随机数序列

2. 案例分析

在长度为11的哈希表中，已填入关键字 17，29，60的记录，哈希函数为：H(key) = key % 11

2.1 计算结果

1. H(17) = 17 % 11 =6。故将关键字“17”存在下标为6的位置，位置空着，所以存入未冲突。
2. H(29) = 29 % 11 =7。故将关键字“29”存在下标为7的位置，位置空着，所以存入未冲突。
3. H(60) = 60 % 11 =5。故将关键字“60”存在下标为5的位置，位置空着，所以存入未冲突。

2.2 散列表的存储状态

这时存入第四个关键字：38.计算：H(38) = 38 % 11 = 5。出现冲突，下标为5的位置已存有60。

2.3 实现方式

1. 1.线性探测再散列
   开始尝试逐次追加di = 1，2，3，...，m-1
2. 得到地址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. 1.用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。
   
2. 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. 散列函数生成的值要尽可能随机并且均匀分布

什么是装载因子?

当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

装载因子计算公式

如何避免低效扩容?

• 1.我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
• 2.当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

散列函数有什么特点?

1. 确定性
   如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
2. 散列碰撞（collision）
   散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。
3. 不可逆性
   一个哈希值对应无数个明文，理论上你并不知道哪个是。
4. 混淆特性
   输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

散列函数时间复杂度