为什么当使用单独的链接时，哈希图插入`O(1)`不是最坏的情况？

Question

我已经了解了哈希图是如何实现的：如果使用单独的链接，则它是一个链表数组。我知道，当插入键值对

(key, val)

时，哈希映射会将该对

{key, val}

插入链表中底层数组中条目

hash(key) % array.size

处。

所以，对于插入过程，要做的就是

• 哈希函数的计算；还有，
• 取模运算（对数组大小取哈希模）；还有，
• 数组访问；最后，
• 分配一个链表节点并将其插入到链表中。

但是，这个插入过程不就是

O(1)

吗，假设hash是

O(1)

，因为那么除了可能是链表插入之外，一切都是

O(1)

，而对于链表插入，我们是不是总是选择插入链表begin处的对，即

O(1)

？这不是一直都是

O(1)

吗？如果是这样，那么为什么哈希表不使用这种策略呢？

Answer 1

通常，您不希望 HashMap 中出现重复的键，即当您尝试插入一对

(key, value)

时，您需要检查该

key

是否已存在于 HashMap 中。对于这项检查，您必须

1. 通过

   hash(key)

找到相应的存储桶
2. 检查

   key

   是否已存在于该存储桶中

为了检查键是否已经存在，您必须迭代存储桶，该存储桶可以有

n

元素。因此，将存储桶实现为链表时，插入仍然是 O(n)

还有其他实现，将存储桶实现为平衡树。通过该实现，您可以将插入降低到 O(log n)