数据结构与算法——散列表

什么是散列表

散列表（hash table），我们平时叫它哈希表或者Hash 表，你肯定经常听到它。

散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

由定义我们可以知道，散列表用的是数组支持下标访问数据的特性，所以散列表是数组的一种扩展，有数组演化而来。

举个例子

假如我们一共有 50 人参加学校的数学竞赛，然后我们为每个学生分配一个编号，依次是 1 到 50.

如果我们想要快速知道编号对应学生的信息，我们就可以用一个数组来存放学生的信息，编号为 1 的放到数组下标为 1 的位置，编号为 2 的放到数组下标为 2 的位置，依次类推。

现在如果我们想知道编号为 20 的学生的信息，我们只需要把数组下标为 20 的元素取出来就可以了，时间复杂度为 O(1)，是不是效率非常高呢。

但是这些学生肯定来自不同的年级和班级，为了包含更详细的信息，我们在原来编号前边加上年级和班级的信息，比如 030211 ，03 表示年级，02 表示班级，11 原来的编号，这样我们该怎么存储学生的信息，才能够像原来一样使用下标快速查找学生的信息呢？

思路还是和原来一样，我们通过编号作为下标来储存，但是现在编号多出了年级和班级的信息怎么办呢，我们只需要截取编号的后两位作为数组下标来储存就可以了。

这个过程就是典型的散列思想。其中，参赛学生的编号我们称之为键（key)，我们用它来标识一个学生。然后我们通过一个方法（比如上边的截取编号最后两位数字）把编号转变为数组下标，这个方法叫做散列函数（哈希函数），通过散列函数得到的值叫做散列值（哈希值）。

散列函数

通过上边的例子，我们知道了散列函数的用途，散列函数在整个过程中起着非常关键的作用。

它本质就是一个函数，我们把它定义为 hash(key)，key 就是元素的键值，通过 hash 函数得到的值就是散列值。

在上边的例子中，散列函数就是截取编号后两位作为数组的下标，我们通过代码一块来看一下：

public int hash(String key)
{
    String lastTowNum = key.substring(key.length()-2,key.length());
    int index = Integer.parseInt(lastTowNum);
    return index;
}

那我们自己在设计散列函数的函数时应该遵循什么规则呢？

得到的散列值是一个非负整数
两个相同的键，通过散列函数计算出的散列值也相同
两个不同的键，计算出的散列值不同

虽然我们在设计的时候要求满足以上三条要求，但是对于第三条来说，想要找到不同的 key 对应的散列值都不一样的散列函数是不可能的。即使现在非常著名的 MD5、SHA、CRC 哈希算法，也没办法避免这用哈希冲突。而且因为数组的存储空间有限，也会加大这种哈希冲突。

哈希冲突

既然我们无法避免哈希冲突，那我们应该怎么解决它呢？常用的方法有两种，开放寻址法和链表法。

开放寻址法

开发寻址法就是但我们遇到了哈希冲突，我们就重新探索一个空闲位置，然后插入。

我们探索空闲位置有以下几种方法。

线性探测

当我们往散列表中插入数据时，经过散列函数发现位置已经被占用了，我们就从当前位置开始，依次往后查找，直到找到空闲位置为止。

比如一个散列表的大小为 10，一个数据经过散列函数之后，到了下标为 8 的位置，但是发现这个位置已经有数据了，那么就依次往后遍历，如果到了尾部，还是没有找到空闲位置，那么就再从头开始找，直到找到空闲位置。

查找元素和插入类似，通过散列函数计算出哈希值，然后找到对应位置数据，然后与查找的元素进行比较，如果相等，则它就是我们要找的数据，如果不相等，就依次往后遍历，如果遍历到空闲位置还没找到，就说明元素不在散列表中。

但是删除的时候稍微有点特别，我们不能直接删除数据，因为我们在查找的时候，如果找到一个空闲位置，就说元素不在散列表中，如果我们直接删除了之后可能会导致某些元素找不到。所以我们将要删除的元素，标记为 deleted，当我们查找的时候，遇到标记为 deleted 的元素，继续往下遍历。

线性探测法存在很大的问题，当散列表中插入的元素越来越多时，发生散列冲突的概率就越来越大，空闲的位置就越来越少，先行探索的时间就会越来越长，甚至在极端情况下，我们需要遍历整个散列表。

二次探索

二次探索，和线性探索原理一样，先行探索每次的步长为 1 ，探索的下标依次为 hash(key)+0，hash(key)+1，hash(key)+2...，二次探索每次的步长变为原来的二次方，所以每次探索的下边为 hash(key)+0，hash(key)+1^{2，hash(key)+2}2。

双重散列

原来我们使用一个散列函数，双重散列，我们使用多个散列函数，我们先用第一个散列函数，如果计算得到的位置已经被占用，就使用第二个散列函数，以此类推，直到找到空闲时的位置。

不管用哪个探索方法，当空闲位置变少的时候，散列冲突的概率会变得很高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子来表示空位的多少。
装载因子 = 填入散列表的元素个数 / 散列表的长度

链表法

链表法是一种更为常用的解决散列冲突的方法，比开放寻址法更加简单。在散列表中每个下标位置对应一个链表，所有经过散列函数得到的散列值相同的元素，我们都放到对应下标位置的链表中。

插入元素时，经过散列函数得到散列值，然后插入到对应下标位置的链表中即可，时间复杂度为 O(1)。查找和删除同样的对对应位置的链表进行操作，对应的时间复杂度和链表的长度有关系，也就是 O(n)。

怎样设计散列函数

通过上边介绍，我们知道散列函数在散列表中占非常重要的作用，关系到散列冲突的概率的大小，从而影响散列表的性能。那么怎么来判断一个散列函数的好坏呢？

首先散列函数不能太复杂，太复杂肯定会消耗更多的时间，从而影响散列表的性能。

散列函数得到的散列值尽可能随机且均匀分布，这样才能减少散列冲突，即使有冲突，每个位置对应的元素也会比较平均，不会有的特别多，而有的特别少的情况。

散列表动态扩容

前边我们提到过，当散列表的装载因子过大的时候，散列表的空闲位置变得很少，散列冲突的概率就变得很大，而且插入和查找数据的效率也会变得很低。
这个时候我们就需要对散列表动态扩容，重新申请一个更大的散列表，然后把原有的数据移到新的散列表中。

如果扩容的时候我们重新申请一个原来散列表两倍大的新散列表，原来的转载因子如果为 0.8，那么重新申请的散列表的装载因子即为 0.4。前边我们讲过数组的动态扩容，数据的迁移比较简单，而散列表数据的迁移就相对比较复杂了，因为散列表的大小变了，那么数据存储的位置也就变了，我们需要通过散列函数重新计算数据的存储的位置。

我们可以设定一个阈值，当装载因子大于阈值的时候，就需要对散列表动态扩容。

如果我们内存空间比较紧张，也可以设定另外一个阈值，当散列表的装载因子小于阈值的时候，对散列表进行动态缩容，但这样做散列表的执行效率就会降低。

所以装载因子的阈值我们要选择得当，根据实际情况来权衡时间、空间复杂度的平衡。如果更在意性能，可以适当的牺牲一些内存空间；如果内存空间紧张，可以牺牲一些性能来换取内存空间。

当我们插入数据的时候，如果装载因子大于阈值，就需要先扩容，再执行插入操作，如果散列表很大，我们扩容搬迁数据的就会非常慢，所以就导致插入数据变得非常慢。

为了解决一次性扩容的耗时问题，我们把数据的迁移分批完成，每次插入操作迁移一部分数据。当达到阈值的时候我们只申请新的散列表，然后把新数据放到新的散列表中，当再有新数据插入的时候，我们将新数据插入到新的散列表，并把一部分数据从老的散列表迁移到新的散列表中。然后重复这样的操作，直到所有数据迁移完成。这样就解决了一次性迁移耗时过长的情况。

数据迁移期间，如果有查询操作，我们首先在新的散列表中进行查找，如果没有，再去老的散列表中查找。