哈希表原理：从 HashMap 到 BM25 倒排索引

slug

type

Post

status

Published

date

Jun 7, 2026

一、哈希表为什么快

核心思想

普通数组按下标访问是 O(1)（直接定位内存地址），但前提是你得知道下标。哈希表的本事是：给任意 key，通过 hash function 算出一个数组下标。

查找流程：

算 hash(key) —— 一次计算，O(1)

拿到 index，直接访问 array[index] —— O(1)

全程不遍历，所以平均查找 O(1)。

对比

结构	按值查找复杂度
数组（array）	O(n)
平衡树（balanced tree）	O(log n)
哈希表（hash table）	O(1)（平均）

关键认知

位置不是被"记住"的，是被算出来的。存的时候用 hash(key) 算出下标放进去；查的时候用同一个 hash(key) 算出同一个下标取出来。 存和查用同一个公式，所以查询时根本不需要"查找位置"这个动作——计算本身就是定位。

二、绕不开的问题：哈希冲突（hash collision）

不同的 key 可能算出同一个 index。主流解决方案：

链地址法（chaining）：每个桶挂一个链表 / 红黑树，撞车的都塞进去。Java HashMap 用此法，链表过长（≥8）转红黑树。

开放寻址法（open addressing）：桶被占了就按规则找下一个空桶（线性探测等）。Python dict 走这类思路。

O(1) 是平均情况

最坏情况（所有 key 全冲突）退化成 O(n)。因此两件事很重要：

hash function 要散得均匀 —— key 尽量分散到不同 index。

load factor（负载因子）= 元素数 / 桶数 —— 超过阈值（Java 默认 0.75）触发 rehash 扩容，重新分配更大数组并搬迁元素，避免冲突堆积。

三、场景应用：RAG 里的 BM25 怎么快速找到"接口"这个词

先破一个概念混淆

BM25 是一个打分公式（scoring / ranking function），负责"这篇文档跟这个词有多相关"——解决的是排序，不是定位。

真正负责"快速找到包含某词的文档"的，是 inverted index（倒排索引）。BM25 建立在它之上。

倒排索引：把映射反过来

正排（普通思路）：文档 → 包含哪些词，找一个词要翻遍所有文档，O(n)。

倒排（inverted index）：词 → 出现在哪些文档里。

这张 词 → posting list 的映射表叫 term dictionary（词典），它的查找就是哈希表：

储物柜类比	倒排索引
key = 物品名	key = 词（"接口"）
value = 物品本身	value = posting list `[doc3, doc17...]`
hash(物品名) → 柜号	hash("接口") → 数组下标

完整检索链路

查询 "接口" 时：

分词：把 query 切成词（"接口"）。

查倒排索引：hash("接口") → 拿到 posting list [doc3, doc17, doc88]。← 快的来源（O(1)）

BM25 打分：只对这几篇候选文档算分（TF、IDF、文档长度归一化）。

排序返回 Top-K。

定位与排序是两件事：倒排索引（哈希）负责快速缩小范围，BM25 负责精排。BM25 只对筛出的候选打分，不碰其它文档。

生产级补充

Lucene / Elasticsearch 的 term dictionary 不止用 hash table，还用 FST（有限状态转换机） 压缩词典、支持前缀查询、节省内存。但底层仍是"哈希思想"。

四、`hash(key) % array_size` 这一步拆解

为什么是取模（modulo）不是除法

目的是把可能很大的整数压回 [0, array_size-1] 的合法下标范围，保证不越界。

array_size：底层数组容量，也叫桶的数量（number of buckets），每个格子是一个 bucket。

五、位运算优化：`x % 16 == x & 15`

Java HashMap 把数组长度强制设为 2 的幂，就是为了用位运算替代取模。

拼图 1：二进制

拼图 2：`&` 按位与（bitwise AND）

逐位比较，两位都是 1 才得 1：

拼图 3：`& 15` 为什么等于 `% 16`

array_size = 2^n 时，size - 1 就是"低 n 位全 1"的 mask。

用 & 15 和任意数做按位与，效果是高位全被 0 闸掉，只保留最低 4 位：

为什么"截断低位" = 取余

类比十进制：8237465 % 100 = 65，余数就是最后两位（砍高位、留低位）。

二进制同理，% 16 对应"留最后 4 位二进制"：

因为 16 是 2 的幂，"除以它取余"在二进制里退化成"砍高位、留低位"，砍位用一次 & 就完成。

为什么快

%（取模）底层是除法，CPU 做除法慢。

& 是最基础的位操作，一个时钟周期搞定。

HashMap 每次 put / get 都要算落桶位置，调用极频繁，这点差距值得抠。

一句话总线收口

size 取 2 的幂 → size - 1 是全 1 mask → hash & (size - 1) 用一次按位与完成取模，把慢除法换成快位运算。
而这一切的根基只有一句：给定 key，位置是 O(1) 算出来的，不是找出来的。

面试速记卡

哈希表 O(1) 是平均，最坏 O(n)（全冲突）。

冲突解决：chaining（Java HashMap）/ open addressing（Python dict）。

load factor 默认 0.75，超过触发 rehash 扩容。

BM25 = 打分；倒排索引 = 定位；两者分工。

倒排索引 term dictionary 底层 = 哈希 + FST（Lucene/ES）。

HashMap 数组长度 = 2 的幂 → hash & (n-1) 替代 % n，位运算省除法。