This post is really great but also 
https://twitter.com/nelhage/status/801472446121422848 …
HashMap insertion is O(n) wost case. Copying a m-element HashMap by inserting each of its elements into another is O(m*n)==O(n**2).
-
-
this is an excellent example of why unqualified worst-case analysis is often very misleading/uninteresting.
-
I am sure you know HashMaps are probabilistic data structures. This is akin to pointing out QuickSort takes O(n^2) time.
-
this is actually a better comp than I thought; both are supposed to be "impossible" in practice, but then you do that one opt...
End of conversation
New conversation -
-
-
If you need better-than-linear worst-case then don't use a HashMap. A HashMap that falls back to being a tree map isn't a HashMap.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
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.