【摘要】哈希表通常被描述成“均摊 \(O(1)\)”的数据结构。这个说法在日常编程里很好用，但它暗含了一个前提：输入没有系统性地撞向同一批桶。只要这个前提失效，哈希表就会从一个轻快的工具变成一条很长的链表，或者一段反复探测的泥潭。 当输入可能很坏，或者你无法相信输入分布时，怎样用随机化把坏运气挡在门外。 确 阅读全文