避免哈希冲突的单独链式哈希

Question

我对哈希表的了解有限，目前我正在学习它。我有一个关于通过开放哈希或单独的链哈希解决哈希冲突的问题。

我知道本例中的散列存储桶持有指向链表的指针，在链表中映射到同一键的所有元素都被链接起来。因此，搜索复杂度大约为o(n)，其中n是链表中元素的数量。有没有办法让这件事变得更简单？

另外，如果链表的大小有限制，假设它最多只能容纳5个元素，如果超过5个元素散列到同一个存储桶中，那么处理这种情况的最佳方法是什么？

任何学习上述内容的建议和任何帮助都将不胜感激。

Answer 1

散列冲突不应该太常见，否则你正在做一些错误的事情(例如，一个坏的散列函数或不够大的散列表)。因此，每个链表中的元素数量应该是最小的，并且O(n)复杂度应该不会太差。

从理论上讲，您可以用许多其他数据结构中的一个来替换它。例如，二叉搜索树将获得O(log )搜索时间(假设项目是可比较的)，但是插入时间将达到O(log )而不是O(1)，并且它将占用更多空间。

列表中的元素数量不应该有最大值。如果有，你可能会求助于探测(例如线性探测)，但删除可能是一场噩梦，因为你可能需要移动相当多的元素。