hash - 分离链Hashing，避免Hash冲突

Question

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

我知道在这种情况下哈希桶保存指向链接列表的指针，其中映射到相同键的所有元素都被链接。所以搜索复杂度将是 o(n) 的顺序，其中 n 是链表中元素的数量。有没有办法让这更简单？

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

任何有关上述内容的更多信息以及任何帮助都将不胜感激。

Answer 1

散列冲突不应该太常见，否则你做错了什么（例如一个糟糕的散列函数或一个不够大的散列表）。所以每个链表中的元素数量应该是最少的，并且 O(n) 复杂度应该不会太差。

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

列表中的元素数量不应有最大值。如果有，您可能会诉诸探测（例如线性探测），但删除可能是一场噩梦，因为您可能需要移动很多元素。