土法炼钢兴趣小组的算法知识备份

Cuckoo Hashing：最坏 O(1) 查找的优雅设计

2026-04-06 | algorithms | #cuckoo-hashing #hash-table #dpdk #network #worst-case-optimal

传统哈希表的 O(1) 查找是'期望'——运气不好时，线性探测可能走 50 步。Cuckoo Hashing 给出了'确定性' O(1)：最多查 2 次（或 d 次）就知道元素在不在。这个保证对网络设备中的精确匹配至关重要。