Hash Table

定义：散列表（Hash Table），利用数组随机访问的特性，通过散列函数（Hash函数）把元素的键值（key）映射为数组的下标（Hash 值），将数据存储在数组对应下标的位置。

查询时间复杂度原理上是 O(1)，但是取决于散列函数、装载因子、散列冲突等。

散列函数

基本要求：

1. 计算得到的值是非负整数

2. 若 key1 = key2，则 hash(key1) = hash(key2)

3. 若 key1 != key2，则 hash(key1) != hash(key2) // 几乎不可能实现，无法避免散列冲突

设计原则：

• 不能太复杂，因为不能消耗过多的计算资源。

• 生成的值要尽可能随机并且均匀分布。

例子：

• 数据分析法，比如手机号前面几位重复叫多，所以取后四位作为散列值。

• 平方取中法

• 随机数法

• 折叠法

• 直接寻址法

哈希算法

定义：将任意长度的二进制值串映射为固定长度的二进制串，这个映射规则就是哈希算法。映射之后得到的值就是哈希值。

哈希算法的要求：

1. 从哈希值不能反推原始数据

2. 对输入数据敏感，修改原始数据一个 bit，得到的 hash 值也大不相同

3. 散列冲突的概率很小，但是不能完全避免（鸽巢原理）

4. 执行效率要高，针对较长的文本，也能快速计算 hash 值

Hash 算法的应用：

• 安全加密，MD5（Message Digest Algorithm），SHA（Secure Hash Algorithm）。第 1、3 点很重要。

• 唯一标识，在海量图库中搜索图片是否存在，每张图片取 hash 值，先比较 hash 值，再比较原始图片。

• 数据校验，BT 下载文件分割成很多块，每块计算 hash 值，保存在种子文件中，这样可以保证下载数据完整。

• 散列函数，注重第 4 点，第 1、3 点不太重要。

• 负载均衡，会话粘滞（session sticky）的实现，计算客户端的 IP 的 hash 值，对服务器数量取余。

• 数据分片，在第二个例子中，图片量巨大，一台机器无法存储，所以对图片计算 hash，然后对机器数取余，放入对应服务器。

• 分布式存储，海量数据单台机器无法存储，根据 hash 值存储在不同机器上。当数据量增加，需要增加服务器，那么需要重新计算 hash，搬迁到正确的机器。一致性 hash 算法，可以大量减少数据搬迁。

散列冲突

散列函数的第三点要求几乎是不可能的，所以会存在散列冲突，解决方案有两种，开放寻址法（open addressing）和链表法（chaining）。

开放寻址法

出现散列冲突，则重新探测位置，将其插入。

不管使用哪种探测方法，当空闲位置较少时，冲突概率会大大增加。可通过装载因子（Load Factor）保证空闲比例。

优点：

• 数据都存在数组中，可有效利用 CPU 缓存加快查询速度。

• 序列化简单。

缺点：

• 删除数据较麻烦，需要标记数据已删除。

• 所有数据在数组中，冲突的代价更高

总结：数据量较小、装载因子较小的时候，适合开放寻址。Java 的 ThreadLocalMap 使用的是开放寻址。

线性探测（Linear Probing）

插入数据时若发现被占用，则依次往后找，直至有空闲位置。

查找数据时，先计算散列值找到对应位置，然后比较，若不相等，则往后找，若遇到空闲位置还没找到，说明数据不存在。

删除数据时，不能直接把元素设置为空，因为查找会有问题，而应该标记为删除。

问题较大，当数据较多时，冲突更多，时间复杂度降为 O(n)。

二次探测（Quadratic Probing）

二次探测步长为 hash(key) + 0, hash(key) + 1 ^ 2, hash(key) + 2 ^ 2, …….

双重散列（Double Hashing）

双重散列使用一组散列函数，hash1(key), hash2(key), hash3(key), ......

链表法

散列表中每个桶（bucket）或槽（slot）会对应一个列表，散列值相同的元素放入相同槽位对应的列表中。

优点：

• 对内存利用率高，因为结点可以在需要时再创建。

• 对装载因子的容忍度更高，即便装载因子为 10，也不会太慢。

缺点：

• 需要存储指针，所以对于小对象，比较消耗内存。

• 对 CPU 缓存不友好。

总结：比较适合存储大对象、大量数据的情况；更加灵活，支持更多优化策略，比如用红黑树替代链表。

装载因子

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

当装载因子过大时，可动态扩容。散列表的动态扩容需要重新计算每个数据的存储位置。

动态扩容的散列表的时间复杂度，摊还分析法，插入最好 O(1)，最坏 O(n)，平均 O(1)。

动态扩容的散列表，删除较多数据后，空闲空间较多，需不需要缩容取决于数据。

扩容的方式：

• 一次性扩容，当需要扩容时，全部搬迁数据。这样遇到某个插入操作就会很慢。

• 分批扩容，当需要扩容时，仅申请空间。每次插入新数据，都插入到新的散列表，并将老的散列表拿一个数据放入新的散列表。查询时，需要查询新旧两个散列表。

工业级散列表

Java 的 HashMap：

• 默认初始大小 16，可以设置

• 默认最大装载因子 0.75，扩容时会扩容两倍。

• 散列冲突，采用链表法，JDK1.8 后，引入红黑树。链表超过默认 8 时，转换为红黑树。红黑树结点小于 8 时，转换为链表。

• 散列函数

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
}

散列表与数组结合

LRU缓存淘汰

基于链表的 LRU 算法时间复杂度 O(n)（见链表）。结合散列表与双向链表时间复杂度可到 O(1)。

实现：每个结点有四个数据，data 存储主要数据，prev 和 next 用于双向链表中，hnext 用于散列表的列表中。还需维护一个双向链表的尾结点，用于快速删除数据。

查找：通过散列表查找，时间复杂度 O(1)，查到数据后，移动到双向链表的头结点。

删除：通过散列表 O(1) 查找到需要删除的结点，然后分别在散列表的链表和双向链表中删除。

添加：首先确认是否存在，若存在，则移动到头结点；若不存在且没满，直接放入首部；若不存在且满，还需先删除双向链表的尾结点，再将数据放入首部。

Redis有序集合

Redis 有序集合中元素有两个属性，key 和 score。

Redis 有序集合的 API 有：

1. 增加

2. 按照 key 删除

3. 按照 key 查找

4. 按照 score 区间查找

5. 按照 score 排序

实现：先按照 score 建立跳表，可以快速实现 API 4 和 5，然后与 LRU 类似，再按照 key 构建一个散列表。

Java LinkedHashMap

// 10 是初始大小，0.75 是装载因子，true 是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
​
m.put(3, 26); // 会替换之前的 3，这个 3 会放到双向链表尾部
m.get(5); // 访问 5 后，被访问到的数据会移动到链表尾部
​
for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());
}

// output: 1 2 3 5

LinkedHashMap 按照访问时间排序，Linked 表示的是双向链表。本质上，与 LRU 实现原理一样。

例题

• LeetCode 242：判断两个字符串是否由相同的字母构成。

• LeetCode 1：两数之和。

• LeetCode 15：三数之和。

• LeetCode 36：判断数独问题是否有效。