哈希表算法：哈希函数与冲突处理的硬件实现
哈希表，说白了就是一张大表格。你给我一个Key，我通过一个函数算出位置，直接去那个位置拿数据。听起来简单，但硬件实现时坑不少。我这些年做路由芯片，哈希表这块踩过的雷，今天跟你好好聊聊。
哈希函数的选择：CRC vs XOR
哈希函数是哈希表的灵魂。选错了，后面全是泪。
CRC哈希
CRC（循环冗余校验）本来是用来做数据校验的，但它的数学特性特别好——输入稍微变一点，输出就天翻地覆。这在哈希表里叫「雪崩效应」。我个人习惯在路由芯片的查表场景中用CRC，因为IP地址前缀往往很相似，比如192.168.1.0/24和192.168.1.128/25，如果哈希函数不够「散」，它们就会挤到同一个桶里。
硬件实现要点：CRC可以用线性反馈移位寄存器（LFSR）实现，面积小、速度快。我建议用并行CRC，一次算32位或64位，别用串行的，太慢了。
// 并行CRC-32的Verilog伪代码
// 输入：data[31:0]，输出：hash[31:0]
// 实际项目中需要根据多项式展开组合逻辑
wire [31:0] crc_next;
assign crc_next[0] = data[31] ^ data[30] ^ ...; // 展开后的逻辑
// 嗯，这里只是示意，真正写起来有32个等式
XOR哈希
XOR哈希就简单粗暴了——把输入按位异或。硬件实现几乎零成本，一个异或门阵列搞定。但你要小心，XOR哈希的冲突率比CRC高不少。我记得有一次项目，用XOR哈希做MAC地址查表，结果两个不同厂商的MAC地址频繁冲突，查表效率掉了30%。
我的建议：如果输入数据分布均匀（比如随机ID），XOR够用。如果输入有规律（比如IP前缀），老老实实用CRC。
| 哈希函数 | 硬件面积 | 延迟 | 冲突率 | 适用场景 |
|---|---|---|---|---|
| CRC | 中等（约500门） | 1-2周期 | 低 | IP路由、MAC查表 |
| XOR | 极小（约50门） | 0.5周期 | 中高 | 流分类、随机ID |
哈希冲突处理：链地址法 vs 开放地址法
冲突是哈希表逃不掉的宿命。你想想看，10个鸡蛋放9个洞，总有一个洞要挤两个蛋。怎么处理？
链地址法
每个桶后面挂一个链表。冲突了，就往链表后面加节点。硬件实现时，链表节点存在SRAM里，每个节点有个指针指向下一个。
我曾经在10Gbps的转发芯片上用链地址法，结果发现链表遍历太慢了。最坏情况下，一个桶挂了100多个节点，查一次要读100多次SRAM。嗯，这显然不行。
避坑指南：链地址法在硬件里要慎用。链表遍历的延迟不可控，而且指针存储额外消耗带宽。我曾经因为链表太长，导致查表延迟从10ns飙到200ns，整个流水线都堵死了。
开放地址法
冲突了，就往后找空位。线性探测、二次探测、双重哈希，都是这个思路。硬件实现简单，所有数据都在一个数组里，没有指针开销。
但开放地址法有个致命问题——删除操作。你删了一个元素，后面的元素可能就找不到了。我一般用「墓碑标记」来解决：删除时标记为已删除，但不真正清空。查找时跳过墓碑，插入时可以覆盖墓碑。
// 开放地址法查找流程（伪代码）
// 输入：key，输出：data或未命中
index = hash(key);
while (table[index] != EMPTY) {
if (table[index] == key && !tombstone) {
return data[index];
}
index = (index + 1) % TABLE_SIZE; // 线性探测
}
return NOT_FOUND;
并行哈希查找架构
单哈希表查一次要几个周期，对于高速路由芯片来说太慢了。怎么办？并行！
我做过一个设计，用4个哈希表并行查找。输入一个Key，同时送到4个哈希函数，4个表同时查。哪个先出结果就用哪个。这样查表延迟从4个周期降到了1个周期。
并行架构的关键：4个哈希函数要相互独立，否则冲突会集中在某几个表上。我一般用CRC-32、CRC-32C、CRC-16和XOR-32四个不同的函数。
布谷鸟哈希的硬件实现
布谷鸟哈希，名字挺可爱，原理也简单：两个哈希函数，两个表。插入时，如果第一个位置被占了，就把原来的踢出去，让它去第二个位置。如果第二个位置也被占了，再踢，循环往复。就像布谷鸟占窝一样。
硬件实现布谷鸟哈希，我踩过最大的坑是「踢出循环」。两个表互相踢，永远停不下来。解决办法是设置最大踢出次数，比如10次。超过10次还没找到位置，就触发rehash——重新建表。
硬件优化技巧：布谷鸟哈希的查找是确定性的——最多查两个位置。这非常适合流水线设计。我一般把两个表的查找放在两个流水级里，第一级查表1，第二级查表2，结果在第二级末尾合并。
// 布谷鸟哈希插入流程（硬件视角）
// 输入：key, data
// 输出：成功/失败（触发rehash）
pos1 = hash1(key);
if (table1[pos1] == EMPTY) {
table1[pos1] = {key, data};
return SUCCESS;
}
// 踢出table1中的旧数据
old_key = table1[pos1].key;
table1[pos1] = {key, data};
// 尝试将old_key插入table2
pos2 = hash2(old_key);
if (table2[pos2] == EMPTY) {
table2[pos2] = {old_key, old_data};
return SUCCESS;
}
// 继续踢...最多10次
// 如果超过10次，触发rehash
布谷鸟哈希的查找延迟是固定的，2个周期就能出结果。这在路由芯片里太宝贵了。我做过一个项目，用布谷鸟哈希做L2转发表，查表延迟从5个周期降到了2个周期，整芯片的吞吐量提升了40%。
注意：布谷鸟哈希的装载率不能太高。理论上是50%，实际做到40%就比较稳了。我曾经贪心，想塞到45%，结果rehash频繁触发，性能反而下降了。嗯，硬件设计就是这样，有时候「留白」才是最好的设计。
好了，哈希表这块就聊到这儿。CRC和XOR怎么选，链地址法和开放地址法各有什么坑，并行架构怎么搭，布谷鸟哈希怎么实现，我都用自己的血泪史给你讲了一遍。下次做路由芯片的查表模块，希望你能少走些弯路。