algorithm - 哈希表中 CRUD 操作的冲突和复杂性之间有什么联系？

Question

在 Aditya Bhargava “Grokking Algorithms：程序员和其他好奇的人的插图指南”一书中，我读到如果我们避免碰撞，则可以避免最坏情况的复杂性。据我了解，冲突 - 是哈希函数在不同键的情况下返回相同的值。它如何影响 CRUD 操作中的哈希表复杂性？谢谢

标签： algorithmhashtablecomplexity-theorycollision

Answer 1

我读到，如果我们避免碰撞，则可以避免最坏情况的复杂性。

这是正确的——当存储在哈希表中的元素的所有哈希值映射到同一个桶并在同一个桶上发生冲突时，就会发生最坏情况的复杂性。

据我了解，冲突 - 是哈希函数在不同键的情况下返回相同的值。

最终，使用哈希函数将值映射到哈希表中的存储桶。也就是说，将整个概念散列函数实现为产生巨大数值范围内的值的散列函数是很常见的（例如，0 到 2^32-1 之间的 32 位散列，或 0 之间的 64 位散列）和 2^64-1)，然后使用%运算符根据当前哈希表存储桶计数将该值映射到特定存储桶。因此，假设您的哈希表有 137 个桶，您可能会生成 139 的哈希值，然后说 139 % 137 == 2 并使用第三个 ([2]在一组桶中）。无论表的大小如何，这种两步方法都可以轻松使用相同的散列函数（生成 32 位或 64 位散列）。如果您改为创建一个直接生成 0 到 136 之间数字的哈希函数，那么对于稍微更小或更大的存储桶计数，它根本无法正常工作。

回到你的问题...

据我了解，冲突 - 是哈希函数在不同键的情况下返回相同的值。

...对于我上面描述的“32 位或 64 位哈希函数后跟 %”方法，有两种不同类型的冲突：32 位或 64 位哈希函数本身可能产生完全相同的 32-或 64 位值用于被散列的不同值，或者它们可能会产生不同的值，这些值在 % 操作之后 - 永远不会映射到散列表中的同一存储桶。

它如何影响 CRUD 操作中的哈希表复杂性？

哈希表通过将值概率性地分布在桶中来工作。当许多值在同一个存储桶中发生冲突时，必须使用辅助搜索机制来处理所有冲突值（可能还有其他混合值，如果您使用开放寻址来尝试哈希表中的存储桶序列，而不是将碰撞元素的链表或二叉树挂在每个桶上）。所以基本上，碰撞率越差，你得到的理想化 O(1) 复杂度就越远，尽管如果你有一个特别糟糕的哈希函数，你真的只会开始显着影响 big-O 复杂度，因为一组值是存储。