Hash table insertions are O(1) in the best case, but O(n) in case of a hash collision. For n items, that’s O(n) vs. O(n²).
-
-
-
Hash flooding attacks trigger the worst-case scenario by sending precomputed data, where all keys hash to the same value.
- 8 more replies
New conversation -
-
-
I swear this was in V8 3 or 4 years ago wasnt it? Maybe just a similar case
-
Hmm… Are you thinking of `Math.random()` not being random enough until late 2015? https://v8project.blogspot.com/2015/12/theres-mathrandom-and-then-theres.html …
- 3 more replies
New conversation -
-
-
Why n^2? Isn’t an only-collisions-map just a linked list with O(n) cost? Or is it worse in v8 for some js reason?
-
No, I messed up that tweet
I meant it’s O(n) in the best case but O(n²) in the worst case *for n lookups*. - 1 more reply
New conversation -
-
-
Uh, O(n) is the linked-list worst-case. O(log n) if you use a self-balancing tree.
-
The typical O(n^2) attack relies on O(n) insertion upon collision, and inserting n items.
- 2 more replies
New conversation -
-
-
This Tweet is unavailable.
-
Not sure if you’re being sarcastic, but if not: is this really necessary?
End of conversation
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.
JavaScript, HTML, CSS, HTTP, performance, security, Bash, Unicode, i18n, macOS.
Node.js is vulnerable to hash flooding. Install security updates now!