4 ms·
> I'm not sure if there is a way to achieve O(1) in the worst case. Then you're not at O(1). You cannot say "O(1) except in the worst case". That is like sayi
by KirinDave 8y ago
> I'm not sure if there is a way to achieve O(1) in the worst case.
Then you're not at O(1). You cannot say "O(1) except in the worst case". That is like saying, "It is blue except when you look at it."
But you don't need these mitigations (most of which are O(log n)) because you never had the hash table. You should look at American Flag sort, because morally it's actually doing something that closely approximates what you're thinking about. That's why I brought it up elsewhere in the thread.
- recursive 8y agoIt's O(1) in the sense that git works. Git uses "commit hashes". If these collide, something would break, on par with the universe stopping working, I presume. But I'm sure, since this never actually happens in practice.
- KirinDave 8y agohttps://arstechnica.com/information-technology/2017/02/watershed-sha1-collision-just-broke-the-webkit-repository-others-may-follow/ https://arstechnica.com/information-technology/2017/02/water... It was a bad design to rely on hashing algorithms to never collide. But it's worth noting that even SHA1 is much more robust than most hash table algorithms, which are meant to run even faster.