十二.散列表

一、基础概念类

散列表（Hash Table，也叫哈希表），核心思想是用空间换时间：通过一个哈希函数把 key 映射成数组下标，直接按下标访问元素，把查找复杂度从 O (n) 降到平均 O (1)。

核心术语

• 哈希函数：把任意长度的 key，转换成固定长度的数组下标的函数，记为 hash(key) = index。
• 哈希冲突：两个不同的 key，经过哈希函数计算得到相同的下标，就是冲突，必须有解决机制。
• 负载因子（Load Factor）：负载因子 = 元素个数 / 数组长度，衡量散列表的拥挤程度；负载因子越大，冲突概率越高，性能越差。
• 扩容（Rehash）：负载因子超过阈值时，申请更大的新数组，把所有元素重新哈希搬过去，保证性能。

提问：好的哈希函数应该满足什么条件？

回答：

四个核心要求：

工业界常用的哈希函数有 MurmurHash、CityHash、XXHash，都是高性能且分布均匀的代表。

提问：常见的哈希冲突解决方法有哪些？各自有什么优劣？

回答：

主流有两大类：

开放寻址法又分三种探测方式：

• 线性探测：冲突了就往后找下一个空位，简单但容易产生 “堆积”，冲突越来越多
• 二次探测：步长是平方级增长，缓解堆积问题
• 双重哈希：用第二个哈希函数算步长，分布最均匀，计算略慢

提问：为什么散列表要扩容？什么时候扩容？

回答：

散列表的性能和负载因子强相关：元素越多、负载因子越大，冲突概率越高，查找效率就会从 O (1) 退化。扩容就是为了把负载因子降下来，维持 O (1) 的平均性能。

扩容时机由负载因子阈值决定：

• 链地址法：阈值一般在 0.75 左右（Java HashMap 就是 0.75），平衡空间和冲突率。
• 开放寻址法：阈值更低，一般在 0.6~0.7，因为开放寻址对负载因子更敏感，太高了冲突会急剧增加。

扩容过程：申请一个原大小 2 倍的新数组，遍历旧数组所有元素，重新计算哈希值放到新数组里，最后替换掉旧数组。

二、核心操作代码

1. 链地址法实现散列表

#include <vector>
#include <list>
#include <string>

using namespace std;

class HashTable {
private:
vector<list<pair<string, int>>> table; // 数组每个位置是一条链表
int size;// 元素个数
int capacity; // 数组容量
double loadFactorThreshold; // 负载因子阈值

// 哈希函数：字符串转数组下标
int hash(const string& key) {
unsigned int hashVal = 0;
for (char c : key) {
hashVal = hashVal * 31 + c;// 经典BKDR哈希算法
}
return hashVal % capacity;
}

// 扩容：容量翻倍，重新哈希所有元素
void rehash() {
int oldCapacity = capacity;
capacity *= 2;
vector<list<pair<string, int>>> newTable(capacity);

// 遍历旧表所有元素，重新哈希到新表
for (auto& bucket : table) {
for (auto& kv : bucket) {
int idx = hash(kv.first);
newTable[idx].push_back(kv);
}
}
table = move(newTable);
}
public:
HashTable(int cap = 16) : capacity(cap), size(0), loadFactorThreshold(0.75) {
table.resize(capactiy);
}

// 插入/更新
void put(const string& key, int value) {
int idx = hash(key);
// 先查是否已存在，存在则更新
for (auto& kv : table[idx]) {
if (kv.first == key) {
kv.second = value;
return;
}
}
// 不存在则插入链表头部
table[idx].push_front({key, value});
size ++ ;
// 超过负载因子阈值，扩容
if ((double)size / capacity > loadFactorThreshold) {
rehash();
}
}

// 查找，找到返回值，找不到返回-1
int get(const string& key) {
int idx = hash(key);
for (auto& kv : table[idx]) {
if (kv.first == key) {
return kv.second;
}
}
return -1;
}

// 删除
bool remove(const string& key) {
int idx = hash(key);
for (auto it = table[idx].begin(); it != table[idx].end(); ++it) {
if (it->first == key) {
table[idx].erase(it);
size –;
return true;
}
}
return false;
}
};

提醒：哈希函数选 BKDR 算法（乘 31 加字符），简单好写且分布均匀，临场演示首选。

2. 开放寻址法实现散列表

#include <vector>
#include <string>
using namespace std;

class HashTableOpen {
private:
vector<pair<string, int>> table;
vector<bool> occupied; // 标记该位置是否有元素
vector<bool> deleted; // 标记该位置是否是删除的（墓碑标记）
int size;
int capacity;

int hash(const string& key) {
unsigned int hashVal = 0;
for (char c : key) {
hashVal = hashVal * 31 + c;
}
return hashVal % capacity;
}

public:
HashTableOpen(int cap = 16) : capacity(cap), size(0) {
table.resize(capacity);
occupied.resize(capacity, false);
deleted.resize(capacity, false);
}

void put(const string& key, int value) {
int idx = hash(key);
// 线性探测找空位
while (occupied[idx] && !deleted[idx]) {
if (table[idx].first == key) {
table[idx].second = value; // 已存在，更新
return;
}
idx = (idx + 1) % capacity;
}
table[idx] = {key, value};
occupied[idx] = true;
deleted[idx] = false;
size++;
}

int get(const string& key) {
int idx = hash(key);
while (occupied[idx]) {
if (!deleted[idx] && table[idx].first == key) {
return table[idx].second;
}
idx = (idx + 1) % capacity;
}
return -1;
}

// 懒删除：只标记，不真正删除，保证探测链不断
bool remove(const string& key) {
int idx = hash(key);
while (occupied[idx]) {
if (!deleted[idx] && table[idx].first == key) {
deleted[idx] = true;
size–;
return true;
}
idx = (idx + 1) % capacity;
}
return false;
}
};

提醒：开放寻址法删除必须用墓碑标记（懒删除），不能直接清空，否则探测链会断，后面的元素就找不到了

三、进阶理解类

提问：为什么 Java HashMap 链表长度超过 8 要转红黑树？

回答：

这是一个经典的工程权衡：

• 正常情况下哈希分布均匀，链表长度很短，查找很快，链表实现简单开销小。
• 极端情况下（哈希函数不好、恶意构造冲突 key），链表会变得很长，查找退化成 O (n)，性能急剧下降。
• 当链表长度到 8 时，转成红黑树，查找变成 O (logn)，保证极端情况下的性能底线。
• 为什么是 8？根据泊松分布，链表长度达到 8 的概率不到千万分之一，正常情况几乎不会触发，只有异常情况才会转树，兼顾了正常情况的性能和极端情况的安全性。
• 元素少的时候再转回链表，因为小数据量下链表遍历比红黑树更快，且内存开销更小。

提问：散列表扩容为什么一般是 2 倍扩容？

回答：

两个核心原因：

提问：什么是一致性哈希？解决了什么问题？

回答：

一致性哈希是分布式场景下的哈希算法，解决的是普通哈希扩容 / 缩容时，大量 key 失效迁移的问题。

普通哈希：key % n，如果节点数从 n 变成 n+1，几乎所有 key 的映射位置都会变，全量迁移成本极高。

一致性哈希：把哈希空间组织成一个 0~2^32-1 的环形，节点和 key 都映射到环上，key 顺时针找到的第一个节点就是它归属的节点。增减节点时，只会影响相邻的一小段 key，绝大部分 key 的映射不变，迁移量极小。

一般还会加虚拟节点，解决节点少时分布不均、数据倾斜的问题。

典型应用：分布式缓存（Redis 集群）、负载均衡、分布式存储。

问题：普通哈希为什么不行？

假设有 3 台缓存服务器（Node0、Node1、Node2），要把 key 分布到这 3 台机器上。

普通取模哈希：

服务器编号 = hash(key) % N （N = 服务器数量）

一旦节点数变了：

几乎所有数据都要重新迁移，缓存雪崩级别的冲击。

一致性哈希原理

1、把整个哈希值空间（比如 0 ~ 2³²-1）想象成一个首尾相接的圆环

2、把服务器节点映射到环上，对每个服务器节点（用 IP、ID 等唯一标识）做哈希，把结果落在环上的某个位置

3、数据去找对应的服务器：对数据的 key 也做哈希，落在环上某个位置，然后顺时针找，遇到的第一个节点就是目标服务器，理想情况下，增删一个节点，只需要迁移 1/N 的数据。

虚拟节点，解决数据倾斜

节点太少时分布不均，比如三个节点挤在一起，大部分 key 都落到 NodeA 上了 ，这就是数据倾斜。

不给每个真实节点只映射一个点，而是映射几十个甚至几百个虚拟点，增删时影响分散在环的各处，不会集中冲击某一个节点

代码简单实现：

#include <iostream>
#include <map>
#include <string>
#include <functional>

/**
* @brief 一致性哈希环（带虚拟节点）
*
* 原理：
* – 用 std::map 维护"哈希值 → 真实节点名"的有序映射（模拟哈希环）
* – 每个真实节点对应多个虚拟节点，均匀分布在环上
* – 查找 key 时，找第一个 >= key哈希值 的虚拟节点
* – 如果找不到（key 在最后一个节点之后），取第一个节点（环的特性）
*/
class ConsistentHash {
public:
/**
* @brief 构造函数
* @param virtual_node_count 每个真实节点对应的虚拟节点数量
*/
explicit ConsistentHash(int virtual_node_count = 150)
: virtual_node_count_(virtual_node_count) {}

/**
* @brief 添加一个真实节点
* @param node 真实节点标识（如 IP、主机名）
*
* 为该节点生成 virtual_node_count_ 个虚拟节点，全部加入哈希环
*/
void addNode(const std::string& node) {
for (int i = 0; i < virtual_node_count_; ++i) {
// 虚拟节点 key = "真实节点#序号"，再哈希
std::string virtual_key = node + "#" + std::to_string(i);
size_t hash = std::hash<std::string>{}(virtual_key);
hash_ring_[hash] = node;
}
}

/**
* @brief 移除一个真实节点
* @param node 要移除的真实节点标识
*
* 把该节点对应的所有虚拟节点从哈希环上删掉
*/
void removeNode(const std::string& node) {
for (int i = 0; i < virtual_node_count_; ++i) {
std::string virtual_key = node + "#" + std::to_string(i);
size_t hash = std::hash<std::string>{}(virtual_key);
hash_ring_.erase(hash);
}
}

/**
* @brief 根据 key 找到应该去的真实节点
* @param key 数据的 key
* @return 目标真实节点名；环为空返回空字符串
*
* 核心查找逻辑：
* 1. 对 key 做哈希
* 2. 在有序 map 中找第一个 >= key哈希值 的节点（lower_bound）
* 3. 找到了就返回；没找到说明在末尾，绕回第一个节点
*/
std::string getNode(const std::string& key) const {
if (hash_ring_.empty()) {
return "";
}

size_t key_hash = std::hash<std::string>{}(key);

// lower_bound: 找第一个 >= key_hash 的元素
auto it = hash_ring_.lower_bound(key_hash);

if (it == hash_ring_.end()) {
// 绕回环的起点
it = hash_ring_.begin();
}

return it->second; // 返回真实节点名
}

/**
* @brief 获取当前虚拟节点总数（调试用）
*/
size_t size() const {
return hash_ring_.size();
}

private:
int virtual_node_count_; ///< 每个真实节点的虚拟节点数

/**
* 哈希环：有序 map，key = 虚拟节点哈希值，value = 真实节点名
* 用 std::map（红黑树）保持有序，方便 lower_bound 查找
*/
std::map<size_t, std::string> hash_ring_;
};

// ============ 测试 ============
int main() {
ConsistentHash ch(200); // 每个真实节点 200 个虚拟节点

// 加 3 台服务器
ch.addNode("192.168.1.10");
ch.addNode("192.168.1.11");
ch.addNode("192.168.1.12");

std::cout << "虚拟节点总数: " << ch.size() << std::endl; // 600

// 测试一些 key 落在哪个节点
std::string keys[] = {"user:1", "user:2", "user:3", "order:100", "product:50"};

std::cout << "\\n=== 3 台节点时 ===" << std::endl;
for (const auto& k : keys) {
std::cout << k << " → " << ch.getNode(k) << std::endl;
}

// 加一台新服务器
ch.addNode("192.168.1.13");
std::cout << "\\n=== 4 台节点时 ===" << std::endl;
for (const auto& k : keys) {
std::cout << k << " → " << ch.getNode(k) << std::endl;
}

return 0;
}

四、实战场景

1. 缓存系统

Redis、Memcached 等分布式缓存，本质就是超大的分布式散列表，key-value 存储，O (1) 读写，是后端系统性能优化的标配。

本地缓存（Guava Cache、Caffeine）也都是基于散列表实现的。

2. 编程语言内置容器

几乎所有主流语言的字典 / 映射容器都是散列表实现：

• C++：unordered_map、unordered_set（链地址法）
• Java：HashMap、HashSet（链地址法 + 红黑树优化）
• Python：dict、set（开放寻址法）
• Go：map（开放寻址法变种）

3. 数据库索引

MySQL 的 Memory 存储引擎支持哈希索引，等值查询 O (1)，比 B+ 树还快；但不支持范围查询、排序，适用场景有限。

Redis 的字典、内部元数据管理，全部基于散列表实现。

4. 去重与计数

海量数据去重、词频统计、用户 UV 统计，都是散列表的经典应用：

• 日志分析：统计每个接口的访问次数
• 爬虫：URL 去重，避免重复爬取
• 推荐系统：用户历史行为去重，避免重复推荐

5. 路由与负载均衡

Nginx、API 网关的路由匹配，用散列表快速根据 URL 找到对应的后端服务；

一致性哈希负载均衡，保证同一用户的请求落到同一台服务器，实现会话保持。

6. 编译与解释器

编译器的符号表，用散列表存储变量名、函数名到地址的映射，查找极快，是编译过程的核心数据结构。