表达式处理、哈希函数与冲突解决

• Scapegoat 树的平衡判定与重建时机
• 沿路径向上找 scapegoat 节点的过程
• α 取值对均摊 O(log n) 的影响

Scapegoat 树是不显式存储平衡因子的自平衡 BST。插入后若新节点到根的路径上存在某个节点，其某个子树大小超过 α 倍该节点大小（如 size(child) > α·size(node)，取 α∈(0.5,1)），则该节点被选为 scapegoat，把以它为根的整个子树重建为完全平衡的 BST。因为每次插入最多只重建一次，且一个节点被重建后至少需要大约 (1-α)/α 次新插入才能再次成为 scapegoat，势能法可证明插入的均摊复杂度为 O(log n)。

α 必须大于 0.5，否则无法保证平衡条件；α 越小树越平衡（查找更快）但重建更频繁。经典 α 取 0.7 左右。重建只发生在插入路径上第一个失衡节点，且整棵子树重建后重新平衡，势能随之释放，从而支撑均摊 O(log n)。

• 滚动哈希的增量计算
• 利用模运算避免指数溢出
• 大素数模与冲突概率

Rabin-Karp 用多项式哈希把模式串和文本的每个长度为 m 的子串映射为整数。先计算模式串哈希 h(p)，再计算文本第一个窗口的哈希，利用滚动公式 h = (h - t[i]*base^(m-1)) * base + t[i+m] 在 O(1) 内由前一个窗口推到下一个窗口，从而在 O(n) 内扫描所有 n-m+1 个窗口。每个窗口与模式哈希比较，只有哈希相等才逐字符核验，期望 O(n+m)。取大素数模（如 2^31-1 或 10^9+7）使哈希值分布更均匀，冲突概率近似 1/mod，因此大素数把误判率压到极低，使期望复杂度接近 O(n+m)。

多项式哈希 h(s)=Σ s[i]*base^i mod M，base 取一个大于字符集大小的常数。滚动计算利用前一个哈希值，避免每个窗口重新计算 O(m)。模取大素数可减少碰撞（碰撞概率约为 1/M）；虽然理论上仍可能碰撞，但实际几乎不发生，故为期望 O(n+m)。

• FNV-1a 的计算流程与 avalanche 特性
• 长输入下混淆不足的原因
• FNV-1a、MurmurHash、xxHash 的质量速度取舍

FNV-1a 以素数偏移基数为初始值，对每个字节做异或并乘以 FNV 素数。它简单快速、实现紧凑，输入短时能产生很好的 avalanche（单比特变化能扩散到整个输出），因此适合短字符串、哈希表键等场景。但它的乘法只在每个字节上做一次，扩散较慢，长输入时输入位的影响不能充分扩散到高位，混淆不足，容易产生碰撞。MurmurHash 采用多轮乘法、移位、异或混合，avalanche 强得多，适合长输入；xxHash 用 SIMD 友好的并行分块处理，速度更快。取舍：FNV 最快最简单但质量一般，Murmur 质量好速度适中，xxHash 在长输入上速度最快。

avalanche 衡量"任何输入位变化是否均匀地影响一半输出位"。FNV 的混淆随输入长度增加而减弱，因为每个字节只触发一次乘法，信息扩散慢。Murmur/xxHash 通过多轮混合和更宽的内部状态提升质量，工程上哈希表用小素数 + 好的混合函数，数据完整性/长串用 Murmur/xxHash。

• 均匀性要求（尽量随机分布、避免偏差）
• 除法散列（取模）与乘法散列（乘黄金分割比）
• 字符串哈希 BKDR/DJB 的选择

均匀性要求哈希函数把输入尽量均匀地映射到哈希表槽位，避免聚集，通常要求输入的小变化导致输出大变化，且对不同输入分布保持良好。除法散列 h(k)=k mod m，m 应取素数避免周期性的聚集；乘法散列 h(k)=floor(m·frac(k·A))，A 取黄金分割比例常数（如 0.618），不依赖 m 的因子，分布更均匀。字符串哈希：BKDR 用素数基数逐字符累乘，DJB 用 33 作为乘数（djb2: h=h*33+ch），两者都高效且对短字符串分布良好。选择上：数字键用乘法散列，字符串键用 BKDR/DJB，并配合取模到槽位。

除法散列简单但 m 选择不当会聚集；乘法散列对任意 m 都较均匀。字符串哈希本质是多项式哈希，基数选择素数（如 31、33、131）可减少碰撞。工程上会结合随机种子打散，防针对性的哈希攻击。

• 哈希碰撞攻击（hash-flooding）的原理
• 不透明随机种子（salt）的作用
• 防御 DoS 的机制

哈希攻击即 hash-flooding：攻击者构造大量哈希值相同的键填入哈希表，使所有键落入同一桶，让链地址法下查找退化为 O(n)，从而造成 DoS。若哈希表使用固定、可预测的哈希函数，攻击者可离线推算出碰撞集。防御方法是在哈希函数中注入一个运行时随机选择、不对外暴露的种子（salt/随机密钥），使攻击者无法预知最终的哈希值，也就无法构造碰撞集。不可预测的种子把攻击者从"可离线构造"变为"必须在线探测"，大大增加攻击成本。

SipHash 等以随机密钥初始化的哈希函数正是为此设计。核心是让攻击者不能提前知道哈希值，因此随机种子必须在进程启动时生成、对攻击者不可见，且每次启动/重启更换。这与密码学哈希（MD5/SHA）的用途不同，前者要求有碰撞（分桶）但不可预测，后者要求无碰撞。

• 平衡因子与回溯更新
• 四种旋转的判定与效果
• 删除时 O(log n) 次旋转的上限

AVL 树平衡因子定义为左高减右高（范围 -1,0,1）。插入后从新节点向上回溯，更新祖先平衡因子，当某节点 |bf|=2 时按失衡形态旋转：LL 型（左子树的左子树高）右旋、RR 型左旋、LR 型先左旋再右旋、RL 型先右旋再左旋。四种旋转都能使该失衡子树旋转后高度恢复为插入前的高度，因此插入只需一次旋转（或一次双旋）即可恢复整体平衡，回溯可停止。删除时，一次旋转可能使祖先前高度减 1 而继续失衡，需要沿路径向上持续旋转，最多 O(log n) 次。

旋转的被旋转子树在旋转后高度等于插入前高度，所以插入后只追溯一次即完成。删除则因子树高度可能减少，需要继续向上检查，最坏一路旋转到根，故 O(log n)。

• 开放寻址三种探测方式的差异
• 链地址法的指针开销与缓存不友好
• 负载因子对两类方法的影响

开放寻址把所有元素存在连续数组里，无指针开销，缓存友好，但冲突时需探测空位，负载因子高时探测次数急剧上升、性能退化快，且删除操作需要"墓碑"标记导致复杂度上升。链地址法每个桶挂条链表，冲突时直接插入链表，可以容忍较高负载因子（>1 仍可用），但每个节点有指针和分配开销，遍历时缓存不友好。线性探测实现最简单但易主聚集；二次探测缓解主聚集但有次聚集；双重哈希用两个哈希函数产生更均匀的探测序列，冲突最少但计算更重。

工程上：内存紧张、键较小、负载因子可控（如 ≤0.7）时用开放寻址（如 Go 的 map、Python 早期版本）；键较大、负载因子高、删除频繁时用链地址法（如 Java HashMap）。缓存友好性是开放寻址的核心优势，但高负载下退化是其主要短板。

• 二次探测的探测序列数量
• 双哈希的探测序列丰富度
• 表长与步长互质的必要条件

二次探测的探测序列为 h(k), h(k)+1², h(k)+2², ... mod m，因为 i² 与 (m-i)² 模 m 相等，所以探测序列具有对称性，实际遍历的槽位约只有一半。双哈希的序列为 h(k), h(k)+h2(k), h(k)+2·h2(k), ... mod m，步长由 h2(k) 决定，不同键可产生不同的步长，因此理论上可产生更多种不同的探测序列（最多 m 种）。为保证探测能覆盖整个表（从而插满而不纠缠），要求 h2(k) 与表长 m 互质；若 m 为素数，则任意 1≤h2(k)<m 都与之互质，序列必然覆盖全表。

二次探测由于序列数量近似 m/2，负载因子高时可能出现无空位可插（尽管表未满）的情况。双哈希通过可变步长扩大探测序列多样性，接近随机探测，但要求互质保证序列遍历全部槽位，这也是双哈希通常取表长为素数的原因。

• 装载因子的定义与影响
• 链地址法在负载 α 下的期望探测次数
• 线性/二次/双重探测的期望探测次数

装载因子 α = n/m（元素数/槽位数）。链地址法下，不成功查找期望访问 1+α 个节点、成功查找期望 1+α/2。线性探测下，不成功查找期望约 (1+1/(1-α)²)/2，成功查找约 (1+1/(1-α))/2，α 接近 1 时急剧恶化。二次探测与双重挖掘的期望性能接近随机探测，好于线性探测，但二次探测序列有限。链地址法在 α 较大时仍可用（链表可增长），开放寻址通常在 α 达到 0.7 左右就应扩容。

开放寻址的期望性能随 α 增大而超线性恶化，尤其线性探测在 α→1 时趋向无穷；链地址法退化是线性的（链表变长）。因此链地址法可以容忍更高负载因子，开放寻址靠更低的负载因子保持性能，这在工程上决定了扩容阈值的选择。

• 扩容时 rehash 的必要性
• 一次性 rehash 的停顿问题
• 渐进式 rehash 的分批迁移机制

哈希表负载因子超过阈值时需扩容为新表并重新计算所有元素哈希（rehash）。一次性 rehash 需要遍历旧表全部元素逐个迁移，当表很大时会造成长时间停顿（STW），对延迟敏感的服务（如 Redis 单线程）不可接受。渐进式 rehash 把迁移分散到每次操作：维护旧表和新表两个表，每次读写操作时顺带迁移一小部分元素（如若干桶），直到全部迁完再丢弃旧表。这样单次操作只承担 O(1) 的迁移量，避免长停顿，代价是操作复杂度有轻微常数增加、且需同时维护两张表。

渐进式 rehash 的本质是"把 O(n) 的一次性工作摊到 O(n) 次操作中，每次 O(1)"，从而把延迟尖峰变成均匀的小开销。期间读写需同时查新旧两表，新插入只进新表。这是延迟均衡（amortized bound）的典型工程应用。

• 布隆过滤器结构与假阳性率定义
• 某位未被置 1 的概率推导
• 最优 k 的求导

布隆过滤器用 m 位数组和 k 个各自独立的哈希函数。插入 n 个元素后，某特定位仍为 0 的概率为 (1-1/m)^(kn) ≈ e^(-kn/m)。对某个不在集合中的元素，k 个位置都为 1 的概率（假阳性率）为 (1 - e^(-kn/m))^k。令 f(k) = (1-e^(-kn/m))^k，对 k 求导并令导数为 0，可得最优 k = (m/n)·ln2，此时最小假阳性率约 (0.6185)^(m/n)。该式给出 k 的最优值与 m/n 成正比、与 ln2 相关。

推导用 (1-1/m)^(kn) ≈ e^(-kn/m) 的近似简化。最优 k 使假阳性率最小，其直观意义是"每个键平均置位 ln2·(m/n) 个位置，使数组约一半位为 1"。工程上按 m/n 和目标假阳性率估算位数组大小，m ≈ -n·ln(p)/(ln2)²。

• 三种表达式的定义与区别
• 中缀转后缀（调度场算法）与转前缀
• 后缀表达式用栈求值

中缀把运算符放在两操作数之间（如 a+bc），需括号或优先级；前缀（波兰式）把运算符放最前（+abc）；后缀（逆波兰式）放最后（abc*+）。中缀转后缀用"调度场算法"：维护一个操作符栈，遇到数字直接输出，遇到运算符按优先级弹出栈顶更高或相等的运算符，括号单独处理。求后缀表达式用栈：遇数字压栈，遇运算符弹出栈顶两数计算，结果压回，扫描完栈顶即为结果。中缀转前缀可先逆转表达式再走后缀流程再逆转，或直接构造表达式树。

后缀表达式无需括号和优先级，天然适合用栈求值，因此编译器常把中缀表达式转化为后缀再求值。转换核心是操作符栈的优先级处理。

• 环形哈希空间与顺时针就近分配
• 虚拟节点解决负载不均
• 节点增删时数据迁移量

一致性哈希把哈希值空间看成一个环，每个节点（服务器）按哈希值映射到环上某位置，每个键哈希后顺时针找到第一个节点，即为该键所属节点。节点增删时，只影响该节点与其前驱节点之间的键，其余键保持不变，因此迁移量约为总数的 1/N（N 为节点数），远小于普通取模哈希（需要迁移几乎全部数据）。虚拟节点把一个物理节点映射为环上多个虚拟位置，使各节点承接的键更均匀，也便于按权重分配。

传统取模哈希在节点数变化时所有键的映射都会改变，导致几乎全量重排。一致性哈希通过环上有序分布，只在局部移动数据，适合缓存、分布式存储等节点频繁变化的场景。虚拟节点缓解了节点数少时分配不均的问题。

• LCG 的递推公式与低位周期性质
• LCG 作为哈希函数的缺陷
• splitmix64/Murmur 的混合策略

LCG 递推为 X_{n+1} = (a·X_n + c) mod m，其低位比特的周期很短（第 k 位周期至多 2^k），因此直接取低位做哈希会呈现明显周期性，随机性差；且相邻输入的相关性可能被保留。作为哈希函数需要混淆输入各位，LCG 的线性结构无法提供足够 avalanche，容易导致分布不均和碰撞。工程上 splitmix64 通过多次乘法、异或、移位把输入充分混合（如 x ^= x>>30; x *= 0xbf58476d1ce4e5b9; x ^= x>>27; ...），Murmur 用多轮乘法与移位混合，都能把输入的每一位扩散到整字的输出，从而提供良好的随机性。

LCG 适合做快速伪随机数生成（连续序列），但作为"把任意键映射到均匀分布"的哈希函数，其低位周期短和线性相关是致命缺陷。splitmix64/Murmur 通过非线性混合（乘大奇常数、移位异或）打破线性结构，实现强 avalanche。

• 前缀树中单分支路径的冗余
• 路径压缩减少节点数
• 在 IP 路由最长前缀匹配中的应用

普通前缀树中，一个节点只有一个孩子的情况（单分支路径）很常见，每个分支都对应一个字符/比特，会浪费大量单子节点。Patricia/radix tree 把单分支的连续路径压缩进一条边，边上记录一段字符串（或比特串），中间不再有节点，从而显著减少节点数，节省空间。在 IP 路由中，路由表是前缀集合，最长前缀匹配（LPM）可用 radix tree 实现：按 IP 比特建立前缀树，查找时沿路径匹配比特并记录最后一个匹配的前缀，即可得到最长前缀对应的下一跳。IPv4/IPv6 的 32/128 位地址配合压缩树，查找效率高。

路径压缩的本质是消除"无分支"的冗余节点，使节点数正比于实际分支数而非总长度。对 IP 路由，压缩不仅省空间，还让沿路径匹配更快；LPM 用"记录最后一个可匹配前缀"实现最长的优先匹配。

• Trie 前缀分层与 B+树的组合
• 共享前缀压缩与缓存友好的权衡
• 版本号 CAS 的乐观并发

Masstree 是一种内存键值索引，把键按 8 字节（64 位）分段，用 Trie 分层，每层内部用 B+树组织。这样共享前缀的键被压缩在 Trie 上层，避免重复存储；而每层用 B+树可对节点做连续内存布局，缓存友好。查找时逐层下降，每层在 B+树中二分/线性查找。并发方面，Masstree 用乐观并发控制：读节点时先读版本号，扫描后再次读版本号验证节点未被修改，若版本变化则重试；修改通过 CAS 原子更新版本号。这样读操作无需锁，写操作在修改节点时用 CAS 更新版本，保证一致性与高并发。

Trie 消除共享前缀冗余，B+树提供缓存友好的批量节点访问；乐观并发用"版本号校验 + CAS"让读不加锁，写冲突时靠重试解决，兼顾低延迟与高吞吐。这是内存数据库索引在并发与缓存上的典型权衡。

• MinHash 的定义与 Jaccard 相似度
• min-hash 相等概率 = Jaccard 的证明
• 达到 ε 误差所需哈希函数数量的推导

Jaccard 相似度 J(A,B) = |A∩B|/|A∪B|。MinHash 对每个集合用 k 个独立哈希函数，取集合中每个元素哈希值的最小值作为该函数的签名。对单个哈希函数 h，min(h(A)) = min(h(B)) 的概率等于 J(A,B)：因为 A∪B 中最小哈希的元素，若落在 A∩B 则两者相等，概率恰为 |A∩B|/|A∪B|。因此用 k 个哈希函数估计，相等签名的比例作为 J 的估计。每个签名是独立伯努利试验，用切比雪夫/切尔诺夫界可得，要使估计误差超过 ε 的概率小于常数，需要 k = O(1/ε²) 个哈希函数。

关键证明是最小哈希元素落在交集中的概率等于 Jaccard。k 个独立哈希给出 k 个独立同分布样本，样本均值的方差随 k 增大而减小，误差界 O(1/ε²) 由中心极限定理/切比雪夫界保证。这是 MinHash 用于大规模集合去重、相似度检索的基础。

• 前缀树与基数树的节点结构差异
• 按二进制位分叉与路径压缩的空间节省
• 在 IP 路由、字典前缀上的应用

前缀树（Trie）每个节点按字符集大小（如 26 个字母）开子节点，节点多、空指针多。Radix Tree（基数树）按二进制位（2 叉）分叉，并把无分支的连续路径压缩为单边，因此节点数正比于有效分支数，远小于字符级 Trie，显著省空间。在 IP 路由中，radix tree 按地址比特建立，支持最长前缀匹配；在字典前缀中，它用于前缀查询、自动补全。基数树本质是 Patricia 树的空间优化版本。

按二进制位分叉把每个节点的分支因子降为 2（最省），配合路径压缩消除单分支冗余，是空间最优的索引结构之一。其代价是节点深度可能增加（每节点 1 bit），但路径压缩使深度正比于实际分支长度。