18-散列表

tip:该篇有点长,请合理安排时间~

散列介绍

散列思想

散列表的英文叫”Hash Table”,平时也有人叫哈希表或者Hash表。

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。

我们用一个例子来解释一下。假如我们有89名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息,你会怎么做呢?

我们可以把这89名选手的信息放在数组里。编号为1的选手放在下标为1的位置;编号为2的选手,我们放在数组下标为2的位置。以此类推。

因为参赛编号跟数组下标一一对应,当我们需要查询参赛标号为x的选手的时候,时间复杂度就为O(1)。

实际上,这个例子就已经用到了散列的思想。在这个例子里,参赛编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的时候,时间复杂度是O(1)这一特性,就可以实现快速查找编号对应的选手信息。

这就是典型的散列思想。其中,参赛选手的编号我们叫做 或者 关键字。我们把参赛编号转为数组小标的方法叫做 散列函数,而散列函数计算得到的值被称为 散列值

hash-function

通过这个例子,我们可以总结出:散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。

散列函数

从上面的例子我们可以看出,散列函数在散列表中起着非常关键的作用。现在我们来学习一下散列函数。

散列函数,我们把它定义hash(key)。

刚刚我们举的例子中,散列函数很简单,直接将编号对应数组下标就好了。但是,如果参赛选手的编号是随机生成的几位数字,又或者用的是a到z之间的字符串,那我们该如何构造散列函数呢?简言之,散列函数就是将key转化为hash(key)的一套规则,这套规则设计的基本要求:

  • 通过规则,计算得到的散列值是一个非负整数。
  • 如果key1 = key2,那hash(key1) == hash(key2)
  • 如果key1 ≠ key2,那hash(key1) ≠ hash(key2)

前两点都还好理解。关于第三点,这个要求看起来合情合理,但是在真实情况下,想要找到一个不同的key对应的散列值都不一样的散列函数,几乎是不可能的。即便是著名的 MD5、SHA、CRC等哈希算法,也无法完全避免这种 散列冲突

散列冲突

再好的散列函数也无法避免散列冲突。我们常用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)。

1. 开放寻址法

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将数据插进去。那应该怎么探测新的位置呢?我们先说一个简单的探测方法,线性探测

当我们往散列表中插入数据时,如果某个数据经过散列函数散列后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。

hash-liner-detection

在散列表中查找元素的过程和插入有点类似。我们通过散列表函数求出要查找元素的键值对应的散列值,然后进行比较。如果相等,则当前元素即为要找的元素,否则就依次往下找。

hash-query

散列表跟数组一样,不仅支持插入、查找操作,还支持删除操作。对于使用线性探测法解决冲突的散列表,删除操作稍微有些特别。我们不能单纯的将要删除的元素置空。这是为什么呢?

在前面的查找操作中,我们通过线性探测方法,找到一个空闲位置,我们就认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来查找算法失效。本来存在的数据,会被认定为不存在。那我们应该怎么办呢?

我们可以将需要删除的元素标记起来。比如标记为deleted。当线性探测查找的时候,遇到被标记的元素继续仍然往下探测。

hash-deleted

你可能已经发现了,线性探测法其实存在很大的问题。当散列表中插入的数据越来越多时,散列冲突发生的可能性就越来越大,空闲位置越来越少,线性探测的时间就会越来越久。极端的情况下,我们需要探测整张表。同理,在删除和查找时,也有可能会线性探测整张表,才可能找到数据。

对于开放寻址法冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)、双重散列(Double hashing)

所谓二次探测,和线性探测很像。线性探测每次探测的步长是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)……我们先用第一个散列函数,如果计算得到的存储位置已经被占用就使用第二个,以此类推。

不管使用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子(load factor)来表示空位的多少。

装载因子的计算公式是:

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

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能越低。

2. 链表法

链表法是一种更加常用的散列冲突解决办法。我们来看下面这张图,在散列表中,每个“桶”或“槽”会对应一张链表,所有散列值相同的元素都被放到相同槽位对应的链表中。

hash-link

当插入的时候,我们只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,插入的时间复杂度是O(1)。当查找、删除元素时,时间复杂度与链表的长度k成正比,也就是O(k)。

如何设计一个工业级散列表

如何设计散列函数

首先,散列函数的设计不能太复杂。其次,散列函数生成的值要尽可能随机并且均匀分布,避免最小化散列冲突,即便冲突,每个槽里的数据也会比较平均,不会出现某个槽中数据特别多的情况。

在实际工作中,我们还要综合考虑各种因素。这些因素有关键字的长度、特点、分布、还有散列表的大小等。

几个常用的、简单的散列函数的设计方法。

  1. 数据分析法
  2. 直接寻址法
  3. 平方取中法
  4. 折叠法
  5. 随机数法

装载因子过大了怎么办?

前面说过,装载因子不能太大,不然影响散列表的性能。不仅插入数据的过程要多次寻址或者拉很长的链,查找的过程也会因此变的缓慢。

对于没有频繁插入和删除的静态数据集合来说,我们很容易根据数据的特点、分布等,设计出完美的、极少冲突的散列表。

对于动态散列表,数据集合是频繁变动的,我们事先无法预估将要加入的数据个数,所以也无法事先申请一个足够大的散列表。但是随着装载因子的增大,散列冲突就会变得不可接受。这个时候,我们该如何处理呢?

还记得之前讲的”动态扩容“嘛?回忆一下,我们是如何做数组、栈、队列的动态扩容的。(之前课程的文章总结笔者没有写~可以自己考虑一下~)

针对数组扩容,数据搬移操作比较简单。但是,针对散列表的扩容,数据搬移操作要复杂很多。因为散列表的大小变了,数据存储位置也变了,所以我们需要通过散列函数重新计算每个数据的存储位置。

插入一个数据,最好情况下,不需要扩容,时间复杂度是O(1)。最坏情况下,装载因子过高,启动扩容。我们需要重新申请内存空间,重新计算哈希位置,并且搬移数据,所以时间复杂度是O(n)。用摊还分析法,均摊情况下,时间复杂度接近最好情况,时间复杂度就是O(1)。

我们前面讲到,当装载因子超过某个阈值时,就需要进行扩容。装载因子阈值需要选择得当。如果太大,会导致冲突过多;如果太小,会导致内存浪费严重。

装载因子阈值的设置要权衡时间、空间复杂度。

如何避免低效扩容

为了解决一次性扩容耗时过多的情况,我们可以将扩容操作穿插在插入操作的过程中,分批完成。当装载因子触达阈值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中。

当有新数据要插入时,我们将新数据插入散列表中,并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表,我们都重复上面的过程。

那这期间的查询操作怎么来做呢?对于查询操作,为了兼容新、老散列表的数据,我们先从新散列表中查找,如果没有找到再去老的散列表中查找。

通过这样的均摊的方法,将一次性扩容的代价均摊到多次插入操作中,就避免了一次性扩容耗时过多的情况。这种实现方式,任何情况下,插入一个数据的时间复杂度都是O(1)。

如何选择冲突解决方法?

上面讲了两种主要的散列冲突的解决方法,开放寻址法和链表法。这两种冲突解决办法在实际的软件开发中都非常有用。比如,Java中LinkedHashMap就采用了链式法解决冲突,ThreadLocalMap是通过线性探测的开放寻址法来解决冲突的。现在我们来看看,这两种冲突解决方法各有什么优势和劣势,又各自适用在哪些场景。

1. 开放寻址法

优点:

  1. 散列表中的数据都存储在数组中,可以有效利用CPU缓存,加快查询速度。
  2. 序列化起来比较简单,不要小看序列化,很多场合都会用到。

缺点:

  1. 开放寻址法解决冲突的散列表,删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。
  2. 在开放寻址法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。
  3. 使用这种方法时,装载因子的上限不能太大。
  4. 比链表更浪费内存。
2. 链表法

优点:

  1. 链表法对内存的利用率比寻址法要高。
  2. 链表法比开放寻址法,对大装载因子的容忍度更高。开放寻址只能适用装载因子小于1的情况。接近1时,就可能会有大量的散列冲突,导致大量的探测、再散列等,性能会下降很多。但对于链表法来说,只要散列函数的值随机均匀,即便装载因子变成10,也就是链表的长度变长而已,虽然查找效率有所下降,但比起顺序查找还是要快很多。

缺点:

  1. 链表因为要存指针,所以对于比较小的存储,是比较消耗内存的,还可能会让内存的消耗翻倍。而且,因为链表中的结点是零散分布再内存中的,所以对CPU缓存是不友好的,这也会对执行效率产生一定的影响。

实际上,我们只要对链表法稍加改造,就可以实现一个更加高效的散列表。那就是,将链表法中的链表改造为其它高效的动态数据结构,比如跳表、红黑树。这样,即便出现散列冲突,极端情况下,所有的数据都散列到同一个桶内,那最终退化成的散列表的查找时间也只不过是O(logn)。这样也就避免了前面讲到的散列碰撞攻击。

所以,总结一下,基于链表的散列冲突处理方法比较适合存储大对象、大数据的散列表。而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如红黑树代替链表。

工业级散列表举例分析

刚刚讲了一个工业级散列表需要设计的一些关键技术。现在,就拿Java中的HashMap这样一个工业级的散列表来具体看下,这些技术是怎么应用的。

1.初始大小
HashMap默认的初始大小是16,当然这个默认值是可以设置的。如果事先知道大概的数据量有多大,可以通过修改默认初始大小,减少动态扩容的次数,这样会大大提高HashMap的性能。

2.装载因子和动态扩容
最大装载因子默认是0.75,当HashMap中元素个数超过0.75*capacity的时候,就会启动扩容,每次扩容都会扩容为原来两倍大小。

3.散列冲突解决方法
HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计的再合理,也免不了会出现拉链过长的情况,一旦出现,则会严重影响HashMap的性能。

在JDK1.8版本中,为了对HashMap做进一步优化,引入了红黑树。而当链表长度太长(默认是8),链表就会转换为红黑树。我们可以利用红黑树快速增删改查的特点,提高HashMap的性能。

4.散列函数
散列函数的设计并不复杂,追求的简单高效、分布均匀。

1
2
3
4
int hash(Object key) {
int h = key.hashCode();
return (h ^ (h >>> 16)) & (capacity - 1);
}

其中,hashCode()返回的是java对象的hash code。
比如String类型的对象的hashCode()就是下面这样:

1
2
3
4
5
6
7
8
9
10
11
public int hashCode() {
int var1 = this.hash;
if(var1 == 0 && this.value.length > 0) {
char[] var2 = this.value;
for(int var3 = 0; var3 < this.value.length; ++var3) {
var1 = 31 * var1 + var2[var3];
}
this.hash = var1;
}
return var1;
}

内容小结

如果现在有个面试题摆在你的面前,问你,如何设计一个工业级的散列表,你会怎么回答呢?

首先,要思考,何为一个工业级的散列表?工业级的散列表应该具有哪些特性?

有这样几点要求:

  1. 支持快速的查询、插入、删除操作;
  2. 内存占用合理,不能浪费太多的内存空间;
  3. 性能稳定,极端情况下,散列表的性能;也不会退化到无法接受的情况

如何实现这样一个散列表?

设计思路:

  1. 设计一个合适的散列函数;
  2. 定义装载因子阈值,并且设计动态扩容策略
  3. 选择合适的散列冲突解决方法

文末链接:
hashmap中的localFactor(装在因子)的值为什么是0.75呢

感谢你对我的支持 让我继续努力分享有用的技术和知识点.