HashDoS：Hashtable的最坏情况复杂度如何为O（n ^ 2）？ [英] HashDoS: how can worst case complexity of Hashtable be O(n^2)?

问题描述

现在你们中许多人一定听说过 HashDoS 。发现这一点的研究人员在视频中称，最糟糕的是Hastable的案例复杂度是 O（n ^ 2）。这怎么可能？

解决方案

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

他们声称的是将n个元素插入表格的复杂性到O（n ^ 2）。所以，单个操作的复杂度是O（n）。这是有道理的：如果所有的键都有相同的散列，那么它们都会进入同一个桶，这只是一个数组或链表，所以需要线性搜索。

By now many of you must have heard about HashDoS. The researchers who found this, claim in their video that the worst case complexity of Hastable is O(n^2). How can this be?

解决方案

The question is worded in an incorrect way. The researchers do not claim that "the worst case complexity of Hashtables is O(n^2)".

What they claim is that "The [...] complexity of inserting n elements into the table [...] goes to O(n^2)." So, the complexity of a single operation is O(n). Which makes sense: if all keys have the same hash, then they all go into the same bucket, which is just an array or a linked list, so it needs to be searched linearly.

这篇关于HashDoS：Hashtable的最坏情况复杂度如何为O（n ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！