hash table

·data-structure-and-algorithm
#data-structure

哈希表的基本概念与原理

什么是哈希表？

哈希表是一种通过“键”（Key）直接访问“值”（Value）的数据结构，核心思想是借助哈希函数 h(key) 将任意大小或形式的 key 映射为数组下标，从而实现平均 O(1) 时间的插入、查找和删除

哈希函数（Hash Function）

需要将 key 映射到 [0, N) 的整数范围，其中 N 是哈希表的桶（bucket）数量

桶其实就是哈希表里存放元素的位置槽，负责处理多个 key 映射到同一个位置时的冲突

好的哈希函数应当“分布均匀”，避免大量 key 落在同一个桶中

冲突解决（Collision Resolution）

当不同的 key 映射到同一索引时，就产生冲突，常见的解决策略有：

  • 拉链法（Separate Chaining）：每个桶维护一个链表/动态数组，冲突的元素都挂到这个链表上

  • 开放寻址法（Open Addressing）：当桶已被占用时，按照某种探测（probe）策略（线性探测、二次探测、双重哈希等）寻找下一个空桶

不同实现各有优劣，拉链法更易处理删除操作，开放寻址法往往省空间且对缓存友好

性能指标

  • 负载因子（Load Factor）：α = 元素数量 / 桶数量，控制在一定范围（如 0.7 以下）可以保证平均 O(1)

  • 扩容（Rehash）：当负载因子超过阈值时，通过分配更大的桶数组并重新哈希所有元素来降低冲突

算法刷题与面试中的应用

典型题型

  • 两数之和：利用哈希表记录已访问元素及其索引，边遍历边查找 target - nums[i] 是否已在表中

  • 无重复子串：滑动窗口结合哈希表（记录字符最后出现位置）快速跳过冲突位置

  • 子数组求和：前缀和 + 哈希表，用哈希表存储前缀和出现次数或索引

  • LRU 缓存设计：链表 + 哈希表结合，实现 O(1) 的访问和淘汰

面试考察要点

  • 复杂度分析：能否说明平均与最坏情况下的时间/空间复杂度区别

  • 哈希函数设计：如何为自定义对象（如结构体、类）设计或指定合适的哈希函数

  • 冲突处理细节：明确不同冲突解决策略的实现原理与优缺点

  • 并发安全（高级题目）：在多线程环境中，如何保障哈希表的安全（读写锁、分段锁、无锁设计等）

在 C++ 中使用哈希表

C++11 之后，标准库提供了高性能的哈希表容器：

std::unordered_map<Key, T>

底层通常基于拉链法实现

典型用法：

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

unordered_map<string, int> cnt;
cnt["apple"] = 3;
if (cnt.count("banana"))
{
    // 查找
    int v = cnt["banana"];
}
// 遍历
for (auto &p : cnt)
{
    cout << p.first << " -> " << p.second << endl;
}

性能调优

预留空间：如果能预先知道元素数量 n，调用 cnt.reserve(n) 避免多次 rehash

自定义哈希：针对特殊 Key 类型，可自定义 struct MyHash 并在模板参数中指定：

struct Point { int x, y; };

struct PointHash
{
    size_t operator()(Point const& p) const noexcept
    {
        return p.x * 31u + p.y;
    }
};
struct PointEq
{
    bool operator()(Point const& a, Point const& b) const noexcept
    {
        return a.x==b.x && a.y==b.y;
    }
};

unordered_map<Point, int, PointHash, PointEq> mp;

在 Go 中使用哈希表

Go 语言内置了 map，其底层也是哈希表，使用非常简洁：

基本用法

// 声明并初始化
m := make(map[string]int, 100)  // 第二个参数为预估大小，可选
m["apple"] = 5

// 读取与存在性检查
v, ok := m["banana"]
if ok {
    fmt.Println("banana:", v)
}

// 删除
delete(m, "apple")

// 遍历
for k, v := range m {
    fmt.Println(k, v)
}

性能与并发

Go 的 map 非并发安全：多 goroutine 并发读写会 panic

并发场景可用 sync.RWMutex 加锁，或使用标准库的 sync.Map（针对读多写少场景做了优化）

自定义 Key

Go map 的 Key 必须是可以比较的类型（可用 ==），如基本类型、指针、接口、字符串、数组，不支持切片、映射、函数

若要用复杂结构体做 Key，可自行实现为内置基础类型的组合或使用序列化

刷题/面试常考点

  • map 的底层机制：红黑树、哈希桶链表或数组？（Go1.9+ 开始使用哈希表 + 链表 + 红黑树混合结构）

  • 零值与初始化：var m map[string]int 是 nil，不能直接写入，需要先 `make

  • 删除后空洞：删除后桶内空间可重用，但不会缩容；map 长期膨胀如何处理？

实际工程中的典型应用场景

  • 缓存（Cache）

    • LRU 缓存、TTL 缓存、布隆过滤器背后的哈希结构

    • C++ 中可结合 unordered_map + 双向链表 实现；Go 中可以找到第三方库或自己手写

  • 路由与分发

    • HTTP 路由表、RPC 方法注册表，Key 是路由或服务名，Value 是处理函数

    • 高性能框架（如 Go 的 gin、fasthttp）在启动时把路由映射进哈希表中

  • 唯一性校验与计数

    • 去重（如电子商务订单号、用户名排重），实时统计（UV 计数、日志字段频率）

    • 批量数据处理时，哈希表提供快速过滤与聚合

  • 编译器/解释器符号表

    • 记录变量、函数、类型的作用域信息，支持快速查找与作用域嵌套

  • 分布式系统中的一致性哈希

    • 将请求或数据划分到不同节点，保证扩容/缩容时的最小数据迁移

    • 一致性哈希环通常用排序数组或跳表，但核心映射逻辑依然是哈希。

小结

哈希表因平均 O(1) 的高效查找性能，在刷题和面试中是必考数据结构

C++ 利用 std::unordered_map 可快速上手并在性能上做精细调优

Go 则内置 map，用法简洁，但要注意并发安全与 Key 类型限制

在实际项目中，缓存、路由、去重、符号表、一致性哈希等场景都离不开哈希表