数据结构与算法-基础(十八)哈希表

摘要

哈希表整体结构就是一个数组，元素的结构是 key-value 形式，因为 key 可以是任意可能类型，那么就需要一个标准性的生成唯一索引方式，所以就引出哈希值这个名称。本文在介绍哈希表时，也着重的说明哈希值，了解哈希值的背景以及生成逻辑，才能更好地理解哈希表。

上期使用红黑树实现映射结构，这样的结构满足 Key 必须具备可比性，元素有顺序地分布这两个特点。在实际的应用场景中，存在结构中的元素是不需要有序的，并且 Key 也不具备可比较性，哈希表完全满足这样的应用场景。

比如设计一个公司的通讯录，存放所有员工的通讯信息，就可以拿手机号作为 index，员工的名称、职位等作为 value。用哈希表的方式可以将添加、删除和搜索的时间复杂度控制在 O(1)。

这时创建一个数组，手机号作为 index，然后存放 value。这样能将复杂度控制在 O(1)，但是这种空间换时间的方式也造成了一些其他问题，比如空间复杂度大（需要更多的空间），空间使用率极其低，非常浪费内存空间。

哈希表就是空间换时间的处理方式，但是做了优化，在空间和时间两个纬度中达到适当的平衡。

哈希表也叫做散列表，整体结构就是一个数组，哈希表会将 key 用哈希函数处理之后返回 hash（哈希值），hash 就是哈希表中的 index这样的处理方式就可以满足搜索时间是 O(1)，这样的处理方式就可以满足搜索时间是 O(1)。因为哈希表中的 key 可能不具备可比较性，所以要做哈希处理。

在执行哈希函数之后返回的 hash，可能会出现相同的情况，这样的情况就是哈希冲突。解决哈希冲突常见的方法有这三种：

0. 开放定址法：按照一定规则向其他地址探测，直到遇见空的位置插入；
1. 再哈希法：设计多个哈希函数，避免出现 hash 相同的情况；
2. 链地址法：比如通过链表将相同 index 的元素串联起来。

JDK1.8 解决哈希冲突的方式就是使用链地址法，其中的链表就是通过链表+红黑树的组合来实现。比如当哈希表中的容量大于等于 64，并且单向链表的节点数大于 8 时，转换为红黑树，不满足这个条件时就使用单向链表。

哈希函数是生成哈希值的实现方法，哈希函数的实现步骤大致分为两步：

1. 生成 key 的哈希值（哈希值为整数值）
2. key 的哈希值与数组的大小进行相关运算，生成一个索引值

public int hash(Object key) {
  return hash_code(key) % table.length;
}

hash_code 是生成哈希值的函数，也可以直接用 JAVA 中的标准函数 hashCode()。

这里可以用 & 位运算替换 % 运算，来提高效率。因为 & 位运算是二进制运算，所以在设计数组的时候，需要将数组的长度设计为 2 的幂次方。

public int hash(Object key) {
  return hash_code(key) & table.length;
}

一个良好的哈希函数，可以让生成的哈希值分布更加均匀，减少哈希冲突的次数，最终可以提升哈希表的性能。

Key 的常见类型可能有证书、浮点数、字符串或者自定义对象，不同的类型生成哈希值的方式也会不一样，但是目标是一致的，就是尽量让每个 Key 的哈希值唯一，尽量让 Key 中的所有信息参与运算。

比如在 Java 中，Long 的哈希值实现如下代码：

public static int hashCode(long value) {
    return (int)(value ^ (value) >>> 32));
}

这里的 >>> 和 ^ 就是将高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值。

在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如 jack，将它拆解成 j、a、c、k（字符的本质就是一个整数，所以 jack 的哈希值可以表示为 j * n3 + a * n2 + c * n1 + k * n0，表达式也可以写成 [(j * n + a) * n + c] * n + k，代码实现如下：

String string = "jack";
int hashCode = 0;
int len = string.length();
for (int i = 0; i < len; i++) {
    char c = string.charAt(i);
    hashCode = 31 * hashCode + c;
}

看上面代码时，可以发现，表达式中的 n 使用的是 31 这个数字，那么为什么用 31 呢？

因为 31 不仅符合 22 - 1 , 而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。

JDK 中，乘数 n 也是用 31，31 也是经过观测分布结果后的选择，关于 31 的变体可以有以下几种：

31 * i = (25 - 1) * i = i * 25 - i = (i << 5) - i