18-散列表

Posted on | Post modified:
Words count in article: 4.3k | Reading time ≈ 14

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呢

有问题？发送 issues 给我~

0%