1

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

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

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

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

4

1 回答 1

1

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

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

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

于 2013-02-26T17:06:08.623 回答