本文介绍了HashDoS：Hashtable的最坏情况复杂度如何为O（n ^ 2）？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
现在你们中许多人一定听说过。发现这一点的研究人员在中称，最糟糕的是Hastable的案例复杂度是 O（n ^ 2）。这怎么可能？
现在你们中许多人一定听说过。发现这一点的研究人员在中称，最糟糕的是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）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！