你有没有在小区快递驿站取过包裹？柜台贴着一张告示：“取件请报手机尾号，尾号 0–9 对应 0–9 号货架。”你报出尾号，店员头也不抬：“3 号架，从上往下第二层。”二十秒取完，从不排队。隔壁老小区还在翻大海捞针，你却享受“报号即达”的畅快——秘密全在那条“尾号→货架”的规则里。如果把规则改得聪明一点，手机尾号的最后一位比第一位分布更均匀，每个货架都不会爆满；如果驿站开成连锁，每家分几片街区，新开店时只有局部快递改道。哈希表，就是计算机世界里的这套“货架管理哲学”。本文从快递驿站出发，带你搞懂哈希函数、冲突处理、负载因子、扩容再哈希、一致性哈希与碰撞攻击，掌握这套“近乎一步到位”的查找艺术。

岗位关联

哈希表是缓存、数据库索引、分布式系统的地基。理解它，你就获得了“近 O(1) 性能直觉”——这是 AI 工程师区别于普通 CRUD 开发者的分水岭。

目录
  1. 可视化演示
  2. 哈希表基础
  3. 哈希函数设计
  4. 拉链法冲突
  5. 开放寻址法
  6. 负载因子扩容
  7. 一致性哈希
  8. 碰撞与安全
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

交互展示哈希函数将键映射到桶的过程，对比拉链法与开放寻址法的冲突处理，解析负载因子与扩容再哈希策略。

本节配有交互动效（进入视口后自动加载，约 3KB）。

哈希映射流程 键经哈希函数映射到桶 近O(1)查找性能 bucket = hash(key) % N 均匀分布是性能关键

哈希表基础

小区新开了一家快递驿站，柜台上贴着告示：“取件请报手机尾号，尾号 0–9 对应 0–9 号货架。”你报出尾号，店员头也不抬：“3 号架，从上往下第二层。”两步走到货架前，二十秒取完。隔壁老小区取快递要翻大海捞针，而你从没等过半分钟。秘密在哪？“尾号→货架”这条规则，让每个包裹都有了唯一归处。这条规则在计算机世界叫哈希函数：给一个键（手机号），算出一个地址（货架号），把数据放进对应位置。取件时不用翻找，算出地址直奔目标——这就是哈希表。

形式化地说，哈希表由一个桶数组（货架排）和一个哈希函数（分货规则）组成。设桶数为 n，对任意键 k，它的存储地址是：

理想情况下，插入、查找、删除都只需 O(1) 时间，与表中已有多少元素完全无关。这比数组的 O(n) 遍历、二分查找的 O(log n) 都快一截——代价是牺牲了“有序性”，你无法高效地遍历所有键或找相邻键。实际工程中，HashMap、Redis 字典、数据库索引都建立在它之上。

驿站老板深知，只要有这条分货规则，几百个包裹也能“对号入座”。可若规则设计不好——比如只看手机尾号第一位——快递就会扎堆爆柜。下一节，我们看看怎么设计一条聪明的分货规则。

address=h(key) mod n\text{address} = h(\text{key}) \bmod n
  1. 哈希函数 h对键做一次变换，得到一个大整数。比如把字符串每个字符编码加权求和，或者把内存地址揉成一团数字。
    h(key)h(\text{key})
  2. 取余运算 mod n将大整数压缩进桶数组的下标范围 0 到 n-1，确保每个键都有对应的货架。
     mod n\bmod n
  3. 桶地址 address数据实际存放的位置。插入时算一次写进去，查找时算一次读出来。
    address=h(key) mod n\text{address} = h(\text{key}) \bmod n

哈希函数设计

驿站最初用“尾号第一位”分货架，结果发现手机号段分布不均：“1“开头的号码最多，1 号架爆满，9 号架空空如也。老板换成”尾号最后一位”，号码末尾近似随机，每个货架的包裹量立刻均匀了。分货规则的好坏，直接决定每个货架的排队长度。哈希函数同样如此——一个理想的哈希函数必须满足三个特性。确定性：同一个键永远算出同一个地址，否则取件时货架会漂移；均匀性：键被均匀映射到每个桶，不扎堆；高效性：计算开销要小，否则省下的查找时间又赔给了算哈希。

技术上看，若键被均匀映射到 n 个桶，每个键落入任意一个桶的概率相等：

工程上常用“扰动函数”提升均匀性。JDK8 的 HashMap 把键的哈希值高 16 位与低 16 位异或后再取余，让高位信息也参与地址计算。这样即使键是连续整数（比如 1、2、3…），低位规律性也被高位打散，不会全部挤进相邻桶。字符串哈希则常乘以 31 这类质数做加权和——质数能减少同余类碰撞，这是数论给的免费午餐。

驿站换了“尾号最后一位”后，每个货架的包裹数都差不多，取件再没排过队。哈希函数就是驿站的“尾号规则”——规则越均匀，查找越稳定。但再均匀的规则也挡不住巧合：总有两个人尾号相同。下一节看驿站怎么处理“撞号”。

P(h(ki)=j)=1n,j∈{0,1,…,n−1}\displaystyle P(h(k_i) = j) = \frac{1}{n}, \quad j \in \{0,1,\dots,n-1\}
  1. 事件 h(k_i)=j第 i 个键经过哈希后恰好落入第 j 个桶。
    h(ki)=jh(k_i) = j
  2. 概率等于 1/n理想均匀分布下，每个桶被选中的机会均等，都等于桶数的倒数。
    P(h(ki)=j)=1nP(h(k_i) = j) = \frac{1}{n}
  3. j 的取值范围从 0 到 n-1 遍历所有桶，所有概率加起来恰好为 1，说明键必然落在某个桶里。
    j∈{0,1,…,n−1}j \in \{0,1,\dots,n-1\}

拉链法冲突

某天，一个包裹的收件人尾号是 3，另一个也是 3。驿站没有重新分货架，而是在 3 号架里把两个包裹叠放，再用记号笔在打包绳上标好取件顺序。取件时先到 3 号架，再沿着绳子一个个比对收件人——虽然多了一个动作，但叠放的就两三个，眨眼便找到。这就是拉链法：每个桶不再只存一个元素，而是存一条链表（那根打包绳）。发生冲突时，新元素直接挂到链表头部，无需移动已有元素，插入永远是 O(1)。

拉链法下，哈希表的实际性能由负载因子 α = 键数 / 桶数 决定。平均查找一个已存在元素的代价是：

  • 常数 1 是哈希计算找到桶的开销；
  • α/2 是链表前半段平均扫描的长度。

当 α 控制在 0.75 左右，平均查找约 1.375 步——这就是“近 O(1)”的底气。但若 α 飙到 100，每条链表平均 100 个节点，查找就和线性扫描无异。JDK8 还做了树化优化：链表长度超过 8 且桶数 ≥64 时，链表转红黑树，最坏情况从 O(n) 降到 O(log n)。

驿站的经验是：只要每个货架叠放不超过“一臂之长”，取件依旧飞快。但若某个货架堆了几百个包裹，这根打包绳就会拖垮一切。所以控制叠放比例，比换更大货架更优先。还有一种思路完全不叠放——快递柜满了就找隔壁空柜，这就是开放寻址法。

E[T]=1+α2\displaystyle E[T] = 1 + \frac{\alpha}{2}
  1. 期望 E[T]平均查找一个已存在键所需的比较次数。
    E[T]E[T]
  2. 常数 1无论桶多长，哈希计算定位桶本身只需一步。
    11
  3. α/2 项目标在链表中的平均位置大约在中间，即链表长度的一半。
    α2\frac{\alpha}{2}
  4. α=0.75 时期望查找约 1.375 步，这就是哈希表接近 O(1) 的数学来源。
    1+0.752=1.3751 + \frac{0.75}{2} = 1.375

开放寻址法

老城区的驿站用的是快递柜，一格只能放一个包裹。货格满了怎么办？柜门上都贴着编号，店员会往后找相邻的空格——1 号柜满了就瞧 2 号，2 号也满就瞧 3 号。取件时也顺着同样的路线，逐个查看直到找到目标。这就是开放寻址法：所有元素都住在数组这栋“楼”里，不借助任何额外链表。当计算出的桶被占，就按探测序列寻找下一个空位。

最基本的是线性探测，冲突时逐格后移：

它的缺点是“聚集效应”：连续占用的桶会像堵车一样越排越长，插入一个新元素可能要扫过大半个数组。改进方案是二次探测，步长取平方：

步长为 1、4、9、16…，跳跃式探测让占用点分散开，显著减少聚集。更高级的双重哈希则用第二个哈希函数决定步长，完全打散规律。还有一个经典陷阱：删除元素时不能直接清空，否则会中断探测链，让后面的元素“失联”——必须留一个特殊标记“墓碑”，表示这里曾经有元素、探测链还得继续穿过去。

快递柜的好处是不需要额外绳子和空间，但代价也很明显：柜子越满，“找空格”越慢。所以开放寻址法对负载因子更苛刻，通常控制在 0.5 以下。驿站老板心里清楚：柜子越空，取件越爽。但无论哪种冲突方案，都躲不过一个终极问题——货架总会被塞满，怎么办？答案只有两个字：扩建。

hi(k)=(h(k)+i) mod m,i=0,1,2,…h_i(k) = (h(k) + i) \bmod m, \quad i = 0,1,2,\dots
hi(k)=(h(k)+i2) mod mh_i(k) = (h(k) + i^2) \bmod m
  1. 初始地址 h(k)第一次尝试的位置，和普通哈希完全一样。
    h(k)h(k)
  2. 探测次数 i从 0 开始递增，i=0 是原位，i=1 是第一次探查下一个位置。
    i=0,1,2,…i = 0,1,2,\dots
  3. 平方步长 i²二次探测的核心，让探测位置 0、1、4、9…跳跃分布，避免挤成一团。
    i2i^2
  4. 取余 mod m保证探测地址永远在数组 0 到 m-1 内循环，不会越界。
     mod m\bmod m

负载因子扩容

驿站渐渐火爆，货架上的包裹快堆到天花板，取件开始要拨开层层叠叠的包裹。老板咬咬牙，决定搬到两倍大的新门面，并让所有快递按新尾号规则重新分架。搬家那天虽累，但之后半年取件都飞快——这就是一次“扩容再哈希”。哈希表里的“拥挤度”由一个核心指标刻画：

其中 n 是已有键数，m 是桶数。当 α 超过阈值（JDK 的 HashMap 默认 0.75），触发扩容：桶数翻倍，所有键重新哈希进新桶。

扩容绝不是“把数据搬过去”这么简单。桶数变了，原来的 h(key) mod m 的结果全部失效——曾经在 3 号架的包裹，在新规则下可能该去 7 号架。所以每个键都必须重新计算地址：

扩容的代价是 O(n)，但均摊到每一次插入上仍然接近 O(1)：每次插入为将来可能的扩容“存”一点开销，数学上叫均摊分析。工程上还有渐进式 rehash（如 Redis）：不一次性完成 O(n) 重哈希，而是每次插入时顺便迁移几个旧桶，同时保留新旧两张表查询，避免大键集扩容时卡顿几百毫秒。

聪明的老板不会等货架完全塞满才搬家，而是在七成满时就动手。既不让空间闲置太多，也不让取件变慢。但单个驿站再大也有上限——城市扩张后，连锁驿站的智慧是分片区服务。下一节看看多驿站怎么分配快递。

α=nm\displaystyle \alpha = \frac{n}{m}
m′=2m,h′(k)=h(k) mod m′\displaystyle m' = 2m, \quad h'(k) = h(k) \bmod m'
  1. 负载因子 α键数 n 与桶数 m 的比值，衡量哈希表的“拥挤程度”。
    α=nm\alpha = \frac{n}{m}
  2. 扩容公式 m'=2m桶数翻倍，为未来插入预留空间，哈希表重新“宽敞”。
    m′=2mm' = 2m
  3. 再哈希 h'(k)所有键用新桶数重新取余，地址全部重新计算。
    h′(k)=h(k) mod m′h'(k) = h(k) \bmod m'
  4. 0.75 阈值太小浪费内存，太大查询变慢——0.75 是空间与时间权衡的黄金分割点。

一致性哈希

城市扩张后，驿站开成了连锁。每家负责一片街区：新街区的快递送 A 站，老城区的送 B 站。倘若某天新增一家 C 站，只有离它最近的 A 站的部分快递需要搬到 C，其余驿站完全不动——这就是一致性哈希的“最小化迁移”。在分布式缓存（Redis Cluster、Cassandra、Elasticsearch）中，数据分布在各节点上。若用朴素取余分片 node = hash(key) % N，节点数一旦从 N 变成 N+1，几乎所有键的取余结果都变了，意味着全量数据迁移——这是不可接受的灾难。

一致性哈希把节点和键都映射到一个逻辑环上（0 到 2³²-1 的圆环）。每个键从自己的位置出发，沿环顺时针找到的第一个节点，就是它的归属节点：

新增节点时，只有它逆时针方向到上一个节点之间那一小段弧上的键需要迁移，其余数据原地不动。但还有一个隐患：真实节点只有几十个时，映射到环上可能扎堆，导致某些节点负载超高。解决办法是虚拟节点——每个物理节点在环上复制出上百个“影子锚点”，让数据分布像撒胡椒面一样均匀。

连锁驿站的智慧在于：新开店时只有局部街区改道，老客户毫无感知。集群扩缩容时，大部分缓存仍命中原地——这就是“哈希不翻车”的艺术。但无论单机还是分布式，哈希表都撑着一道看不见的暗门：如果有人故意捣乱呢？

pos(nodek)=hring(nodek),key→顺时针最近节点\displaystyle \text{pos}(\text{node}_k) = h_{\text{ring}}(\text{node}_k), \quad \text{key} \to \text{顺时针最近节点}
  1. 节点锚点 pos(node_k)把节点 ID 也哈希到环上，形成环上的“锚点”。
    pos(nodek)=hring(nodek)\text{pos}(\text{node}_k) = h_{\text{ring}}(\text{node}_k)
  2. 顺时针最近键从自己的环位置出发，顺时针遇到的第一个锚点即归属节点。
    key→next clockwise node\text{key} \to \text{next clockwise node}
  3. 虚拟节点每个物理节点对应多个锚点，环上的锚点密度更高，负载更均匀。

碰撞与安全

有个恶意收件人，注册了上千个手机号，尾号全是 3。3 号架瞬间被几千个包裹淹没，所有到 3 号架取件的人都要在打包绳上翻千百次——驿站的“对号入座”秒变“大海捞针”。这就是哈希碰撞攻击：攻击者利用已知哈希函数的规律，构造大量碰撞键，让哈希表退化为链表，查询从 O(1) 恶化到 O(n)，拖垮整个服务。历史上 Java 版本的哈希碰撞攻击曾让多个 Web 框架的请求体解析被 DoS。

碰撞真的很难避免吗？生日悖论告诉我们：碰撞远比直觉常见。随机选 k 个键，至少有一对碰撞的概率约为：

当 n = 2³²（32 位哈希值）时，随机选约 6.5 万个键就有 1/2 的概率发生碰撞。所以碰撞不可怕——可怕的是所有键“精准”砸进同一个桶。防御手段有四个层次：一是每次启动随机哈希种子，让攻击者无法预测碰撞键（Java 的 random hash seed）；二是链表超阈值转红黑树，把最坏情况从 O(n) 压到 O(log n)；三是限制键的长度与数量，切断攻击者的弹药；四是在防篡改场景直接用密码学哈希（SHA-256），让构造碰撞在计算上不可行。

驿站老板最终给 3 号架加了护栏：每个收件人限领 5 个包裹（限制数量），打包绳太长就换成“红黑树快递柜”（树化）。系统设计者同样需要“坏人视角”——哈希表不仅要快，还要扛得住恶意。处理完安全，我们把镜头拉回日常工作：哈希表在 AI 场景里到底怎么用？

P≈1−e−k(k−1)2n\displaystyle P \approx 1 - e^{-\frac{k(k-1)}{2n}}
  1. 指数项 exp(-k(k-1)/(2n))表示“没有任何碰撞”的概率。k 个键两两配对共有 k(k-1)/2 对。
    e−k(k−1)2ne^{-\frac{k(k-1)}{2n}}
  2. 1 减去无碰撞概率结果就是至少存在一对碰撞的概率。
    P≈1−e−k(k−1)2nP \approx 1 - e^{-\frac{k(k-1)}{2n}}
  3. 值空间 n 的影响n 越大（哈希值越长），碰撞概率越小，安全边际越高。

AI 应用场景

大模型语义缓存

阶段：推理服务优化

解决的问题：大模型 API 重复收到相同 prompt 时，每次都做完整前向推理，延迟高、GPU 成本昂贵。用哈希表做语义缓存：对 prompt 计算哈希作为键，缓存完整回答，命中时直接返回，平均加速 30%–80%。

具体案例：某 LLM 应用网关对用户请求的 prompt 做规范化后取 SHA-256 哈希，存入 Redis Hash（底层是哈希表）；相同 prompt 再次到达时 O(1) 命中缓存，无需调用模型。缓存键还会拼接模型版本号，模型升级后自动失效。

向量数据库的 IVF 索引

阶段：特征检索与召回

解决的问题：百万级 embedding 向量线性扫描太慢。IVF（倒排文件）索引先用聚类中心把向量库分割成 nlist 个“桶”，查询时先算出向量最近的聚类中心，只在对应桶内精确匹配——这正是哈希表“桶地址 + 桶内扫描”思想的向量版。

具体案例：使用 faiss 构建 IVF 索引时，设置 nlist=100，训练阶段用 K-means 得到 100 个聚类中心；查询向量先与 100 个中心比较，选出最近的桶，再在桶内做精确距离计算，检索时间从毫秒级降到亚毫秒级。

分布式检索分区路由

阶段：训练与推理数据经路

解决的问题：分布式向量库（Milvus、Redis Search）需要把数据分片到多台机器。一致性哈希让扩缩容时只有 1/N 的数据迁移，且查询路由稳定，AI 服务在多租户场景下不因集群变动而大规模缓存失效。

具体案例：某智能问答系统把用户会话向量按一致性哈希写入 8 节点 Redis Cluster，某次扩容到 10 节点时，只有约 20% 的会话发生迁移，其余用户会话无感继续命中。

Python 演示

python46 行
class HashTable:    """拉链法实现的简单哈希表"""    def __init__(self, cap=8):        self.cap = cap        self.buckets = [[] for _ in range(cap)]        self.size = 0        self.threshold = 0.75     def _hash(self, key):        return hash(key) % self.cap     def put(self, key, val):        idx = self._hash(key)        for i, (k, v) in enumerate(self.buckets[idx]):            if k == key:                self.buckets[idx][i] = (key, val)                return        self.buckets[idx].append((key, val))        self.size += 1        if self.size > self.cap * self.threshold:            self._resize()     def get(self, key):        idx = self._hash(key)        for k, v in self.buckets[idx]:            if k == key:                return v        raise KeyError(key)     def _resize(self):        old = self.buckets        self.cap *= 2        self.buckets = [[] for _ in range(self.cap)]        self.size = 0        for bucket in old:            for k, v in bucket:                self.put(k, v)  if __name__ == '__main__':    ht = HashTable()    for i in range(50):        ht.put('user:' + str(i), i * 10)    ht.put('user:10', 999)    print('user:10 ->', ht.get('user:10'))    print('桶数:', ht.cap, '键数:', ht.size)
目的：展示哈希表的核心生命周期——哈希取模、链表冲突处理、负载因子触发扩容。运行后你会看到键数 50 时桶数从 8 扩到 32。
  1. self.buckets = [[] for _ in range(cap)]初始化桶数组，每个桶是一个空链表
  2. hash(key) % self.cap哈希取余，计算桶地址
  3. self.buckets[idx].append((key, val))冲突时挂到链表尾部，拉链法写入
  4. self.size > self.cap * self.threshold负载因子超过 0.75 触发扩容
  5. old = self.buckets暂存旧桶数组，为迁移做准备
  6. self.size = 0重置计数，避免 put 时重复累加导致死循环
  7. ht.put('user:10', 999)更新已有键，走的是链表内替换分支

常见误区

误区哈希表就是 O(1)，任何情况下都快，所以数据结构选它准没错。

正解“O(1)“是平均情况，不是最坏情况。当哈希函数设计糟糕、负载因子失控或遭遇恶意碰撞时，查找会退化成 O(n)，和链表一样慢。工程上必须控制负载因子、使用随机种子和树化兜底，才能让”近 O(1)”成立。

为何常见：教材和面试题总说“平均 O(1)”，初学者把“平均”两个字自动过滤，忽略了它背后的前提条件。

误区哈希函数设计得越复杂、越“高级”，就越不容易冲突。

正解哈希函数要在确定性、均匀性、高效性三者间平衡。CRC32 比 SHA-256 快几个数量级，均匀性足够应付普通场景；若给每个键计算 SHA-256，哈希的开销本身就会成为性能瓶颈。均匀性够用就好，不是越复杂越优。

为何常见：直觉上“复杂=安全=更好”，但哈希表的总耗时 = 哈希耗时 + 桶内比较耗时，哈希占比过重反而拖后腿。

误区哈希表扩容就是把数据原样复制到更大的数组里，跟 `ArrayList` 扩容差不多。

正解普通数组扩容确实是复制，但哈希表不行——桶数变了，hash(key) % m 的取余结果整体改变，地址全部失效，必须逐键重新计算哈希，即“再哈希”。这正是扩容是 O(n) 且耗时较高的原因。

为何常见：把其他容器的扩容经验套用到哈希表上，忽略了“地址 = 哈希 % 桶数”这一耦合关系。

误区一致性哈希把数据均匀分布在环上，所以每个节点负载必然均衡。

正解一致性哈希只解决“最小迁移”，不保证均衡。节点只有几个时，它们在环上的锚点可能扎堆，导致某个节点承接超量数据。必须引入虚拟节点，让每个物理节点在环上有上百个影子锚点，分布才趋于均匀。

为何常见：教科书上的环图画得圆润漂亮，让人误以为随机映射天然均匀，忽略了“小样本随机性不足”。

误区好的哈希函数不会产生碰撞，所以设计哈希表就是要找“无碰撞哈希”。

正解鸽巢原理决定了碰撞必然存在——键空间远大于桶空间，必然有两个键映射到同一个桶。哈希表设计的目标不是消灭碰撞，而是让碰撞可控、影响最小化（拉链、探测、树化）。

为何常见：把哈希函数等同于“一一对应的数学映射”，忽略了它是一种有损压缩。

面试题

Q1. 哈希表在理想情况下的查找时间复杂度是多少？

单选题 · easy

  • A.O(1)← 正确答案
  • B.O(log n)
  • C.O(n)
  • D.O(n log n)

答案：A。理想情况下哈希函数均匀分布且无冲突，一次哈希计算直接定位到桶地址，插入、查找、删除都是 O(1)。O(log n) 属于平衡树，O(n) 是线性扫描。

Q2. 一个合格的哈希函数最基本的要求是什么？

单选题 · easy

  • A.输出结果随机变化
  • B.同一个键总是算出同一个地址← 正确答案
  • C.输入不同的键结果一定不同
  • D.输出长度可动态调整

答案：B。确定性是哈希表的基石——同一个键在插入和查找时必须算出相同的桶地址。若输出随机变化，插入到 3 号架、查找却跑去 7 号架，数据永远找不到。C 是理想但不可能的（碰撞必然存在）。

Q3. 关于拉链法与开放寻址法，下列说法正确的有？

多选题 · mid

  • A.拉链法用链表存储冲突元素← 正确答案
  • B.开放寻址法删除元素比拉链法更简单
  • C.拉链法负载因子可以大于 1← 正确答案
  • D.开放寻址法通常要求负载因子低于 0.5← 正确答案

答案：ACD。拉链法每个桶是一条链表，冲突元素挂链上，负载因子超过 1 也只在链表里追加。开放寻址法删除元素必须留“墓碑”标记，比拉链法复杂得多，且因探测链的存在要求低负载因子。

Q4. 负载因子 0.75（HashMap 默认值）代表什么？

单选题 · easy

  • A.有 75% 的桶被占用
  • B.键数与桶数的比值达到 0.75 时触发扩容← 正确答案
  • C.哈希函数计算出错概率为 75%
  • D.链表长度最大为 75

答案：B。负载因子 = 键数 / 桶数，0.75 是扩容阈值。它不等于“桶占用率”——因为冲突键会共享桶。达到阈值后桶数翻倍、重新哈希，让哈希表恢复“宽敞”。

Q5. 为什么哈希表扩容后必须重新计算每个键的地址？

单选题 · mid

  • A.桶数变了，原取余结果全部失效← 正确答案
  • B.数据会自动过期
  • C.为了删除旧桶中的重复数据
  • D.为了降低哈希函数的计算复杂度

答案：A。地址公式是 hash(key) % m，m 从 8 变 16 后，同一个键的取余结果几乎必然改变。所以必须逐键重算地址并迁移到新桶，这就是“再哈希”，复杂度 O(n)。

Q6. 一致性哈希解决了分布式缓存中的哪些问题？

多选题 · mid

  • A.节点扩缩容时只需迁移部分数据← 正确答案
  • B.让所有键在所有节点间完美均匀分布
  • C.通过虚拟节点提升负载均衡← 正确答案
  • D.完全消除哈希碰撞

答案：AC。一致性哈希把键分配到环上顺时针最近的节点，新增节点只影响局部弧段，迁移最小化。虚拟节点提升均衡性。但它不保证完美均匀，也完全不处理碰撞。

Q7. 哈希值空间为 n（如 2³²），随机选 k 个键出现至少一对碰撞的概率约为？

单选题 · extreme

  • A.1 - e^{-k(k-1)/(2n)}← 正确答案
  • B.e^{-k/n}
  • C.1/n
  • D.k/n

答案：A。这是生日悖论的公式：无碰撞概率约 e^{-k(k-1)/(2n)}，1 减去它就是至少一对碰撞的概率。当 n=2³² 时，约 6.5 万个键就有 50% 碰撞率——所以碰撞在工程中无法避免，只能管控。

Q8. 开放寻址法中，线性探测（逐一后移找空位）最大的问题是什么？

单选题 · mid

  • A.聚集效应：连续占用形成长列，插入和查找变慢← 正确答案
  • B.无法处理整数键
  • C.需要额外内存存放链表
  • D.不支持删除操作

答案：A。线性探测的地址序列是 h(k), h(k)+1, h(k)+2…，连续占用的桶会越排越长，形成“堵车”。二次探测（步长 1²、2²、3²…）就是为了打散这种聚集。开放寻址法支持删除，只是需要墓碑标记。

Q9. 防御哈希碰撞攻击的常见手段有哪些？

多选题 · hard

  • A.使用随机哈希种子← 正确答案
  • B.链表超过阈值转为红黑树← 正确答案
  • C.限制键的长度与数量← 正确答案
  • D.把负载因子阈值调大到 1.5

答案：ABC。随机种子让攻击者无法预知哈希结果，红黑树化把最坏情况从 O(n) 压到 O(log n)，限制键长度和数量切断攻击源头。调大负载因子只会让桶更长、退化更严重，是反向操作。

Q10. 分布式缓存用一致性哈希替代 hash(key) % N 取余分片，核心原因是什么？

单选题 · hard

  • A.取余分片在节点数变化时导致大量键迁移← 正确答案
  • B.取余分片计算开销更大
  • C.一致性哈希能避免所有哈希冲突
  • D.一致性哈希支持有序遍历所有键

答案：A。取余分片里节点数 N 是分母，N 从 10 变 11 时几乎所有键的取余结果都改变，等于全量迁移。一致性哈希让键沿环顺时针归位，新增节点只影响局部弧段，迁移量约 1/N。它不避免冲突，也不支持有序遍历。