15.散列

作者: 学海一乌鸦 | 来源:发表于2020-06-06 17:53 被阅读0次

1.定义

1.1几个概念

键值(key)
散列函数(hash)
散列值
一句话:键值通过散列函数得到散列值；

image.png
装载因子:衡量哈希冲突的概率,该值越大，表示哈希冲突的概率越高；

散列表的装载因子=填入表中的元素个数/散列表的长度

1.2散列思想

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。
我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。
当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

1.3 关键设计

总结下来，对于散列，主要有两个地方需要考虑:散列函数的设计(尽可能不产生散列冲突)和处理散列冲突(冲突总是难免的)

1.3.1 散列函数的设计

决定了散列表冲突的概率大小，也直接决定了散列表的性能。

设计原则

散列函数计算得到的散列值是一个非负整数；
如果 key1 = key2，那 hash(key1) == hash(key2)；
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。(基本做不到)

即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突

1.3.2 冲突解决办法

开放寻址法(open addressing)

开放寻址法的核心思想:如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

线性探测
核心思想:经过哈希函数后，槽位已经被占据，那就沿着槽继续找空位插入；
散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)极端情况下时间复杂度会降低到O(n)
二次探测

跟线性探测很像，线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+1^2 ,hash(key)+2^2……

双重散列
所谓双重散列，意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置.

链表法(chaining)

在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

image.png

这样插入的时间复杂度为O(1),查找和删除的时间复杂度为O(k),k为链表上元素的个数，理想情况下，k=n/m(n为元素的总个数，m为槽数)

2.进阶

2.1 如何设计散列函数

再谈设计原则

第一:散列函数的设计不能太复杂。过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能。
其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。

常用的散列函数

数据分析法
直接分析数据的特点，比如手机号后四位；
取模法
比如:将单词中每个字母的ASCll 码值“进位”相加，然后再跟散列表的大小求余、取模，作为散列值。

hash("nice")=(("n" - "a") * 262626 + ("i" - "a")2626 + ("c" - "a")*26+ ("e"-"a")) / 78978

直接寻址法
平方取中法
折叠法
随机数法

2.2 装载因子的设计

装载因子越大，说明表内元素越多，空闲位置越少，哈希冲突的概率越大；插入、查找、删除的时间复杂度都会提高很多；

装载因子的设计原则

使用动态扩容，插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)；
装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重；
装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
高效扩容
问题:虽然扩容的均摊时间复杂度为O(1),但是针对特定的某一次，时间复杂度为O(n),如果该操作是对客的，那么这个时间是无法容忍的
解决办法:在装载因子达到阈值时，申请新的内存空间，但是不是立刻把所有的元素都放入新的数组中，而是均摊到每次，这样每次插入的时候复杂度还是O(1)。对于查找，首先查到新的散列表，再去查找老的散列表；

image.png

2.3 哈希冲突的解决选型

实例:Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突

开放寻址法

优势:实现简单，数据直接存在数组中，复杂度低，同时可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单；
缺点:查找和删除数据比较麻烦，同时冲突的概率也比较高；
试用场景:数据量小，装载因子小的时候适合使用

链表法

对内存的利用率高，在创建的时候无须预先申请好，这也是链表对比数组的优势；
对装载因子的容忍度高，对于开放寻址法当装载因子接近1的时候，会有大量的冲突，但是对于链表法，即使装载因子的值为10，对于散列函数设计良好的散列表，也就是链表的长度为10，查找速度也比顺序查找高效很多。
对于小的对象来说，因为要存储指针，可能使内存翻倍，而且由于内存空间不连续，无法利用CPU缓存的高效性能，但是对于大的内存对象来说，存储指针的内存其实可以忽略不计
适用场景:基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

3工业级散列表

3.1hashMap

初始大小
HashMap 默认的初始大小是 16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。
装载因子和动态扩容
最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
散列冲突解决方法
HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况。
在 JDK1.8 版本中，为了对 HashMap 做进一步优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树。可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
散列函数

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}

3.2设计思想

何为工业级散列表

支持动态的查找、删除和增加；
占用内存合理；
性能稳定，极端情况下，性能也不会退化到无法忍受的地步；

3.3 如何设计

散列函数的选择
装载因子大小的考虑，考虑动态扩容的方案
哈希冲突后的处理办法

开放场景题:

Word文档中的单词拼写检查功能是如何实现的？
利用散列表的思想，常用的单词数量在20w左右，单词的平均长度比如说为10，那么每个单词的大小是10字节，20w单词占据的大小约为2m，将这20w个单词放入散列表中(利用散列函数的能力，将单词可以对应到数组的某个下标里面)，当用户输出单词后从散列表搜索，如果查不到，那么可以提示用户单词可能拼写出错；
假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
step1:确定这10w条url的访问次数，利用散列表，将这10w条url存入散列表中，key为url，值为出现的次数，并记录出现次数最大值为K。时间复杂度为O(n)
step2：经过step1，可以得到一个url及对应的次数，然后根据次数进行排序，如果k值不是特别大，可以采用桶排序，时间复杂度为O(n)，或者使用快排，复杂度为O(nlgn)
有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？
step1:将数组一中的值存入散列表中，key为字符串，value为1，1表示至少出现一次；
step2:数组二遍历，每个值依次去散列表中查找，vaue为1，表示相同，没有找到则不相同；
DOS(Denial of Service)拒绝服务供给
前提:散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。
在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。