sorting - HashDoS：Hashtable 的最坏情况复杂度如何为 O(n^2)？

Question

到目前为止，你们中的许多人一定听说过HashDoS。发现这一点的研究人员在他们的视频中声称 Hastable 的最坏情况复杂度是O(n^2). 怎么会这样？

Answer 1

这个问题的措辞不正确。研究人员并没有声称“哈希表的最坏情况复杂度是 O(n^2)”。

他们声称“将 n 个元素插入表的 [...] 复杂度 [...] 达到 O(n^2)”。因此，单个操作的复杂度为 O(n)。这是有道理的：如果所有的键都具有相同的哈希值，那么它们都进入同一个桶，它只是一个数组或链表，所以需要线性搜索。