为了节省平均O(1)的时间复杂度,我是否必须对整个密钥进行哈希处理？

Question

假设我有哈希表和均匀分布的哈希函数,它使用链接列表的单独链接.

保存在表中的密钥是成对的(a,b)(无限数量),我根据hash(a)(我忽略b)将它们插入到表中.

是行动find,insert而delete仍然在O(1)时间上平均？或者我必须哈希整个密钥,包括b？

Answer 1

不,这不能保证您期望O(1)查找.想象一下,例如,您散列(0,0),(0,1),(0,2),(0,3),...,(0,n-1).这些值中的所有n将散列到表中的相同位置(因为忽略了第二个组件),因此无论散列函数如何散列第一个组件(0),您最终将在同一位置使用n个元素哈希表,使您的查找退化为在最坏情况下花费时间Θ(n).

一般来说,在使用哈希表时需要对整个键进行哈希处理.否则,您可以通过保持密钥的一部分不变并更改其他部分来轻松地结束哈希冲突.