15.散列

2020-06-06  本文已影响0人  学海一乌鸦

1.定义

1.1几个概念

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

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

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

1.2散列思想

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

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

1.3 关键设计

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

1.3.1 散列函数的设计

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

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

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

1.3.2 冲突解决办法

开放寻址法(open addressing)

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

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

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

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

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

image.png

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

2.进阶

2.1 如何设计散列函数

再谈设计原则

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

常用的散列函数

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

2.2 装载因子的设计

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

装载因子的设计原则

2.3 哈希冲突的解决选型

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

开放寻址法

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

链表法

3工业级散列表

3.1hashMap

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

3.2设计思想

何为工业级散列表

3.3 如何设计

开放场景题:

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

猜你喜欢

热点阅读