2 ms·

But it requires a perfect hash. You need to guarantee over any potential input that you don't have collisions. How do you do that over all inputs? If there is

• recursive 8y ago
  No, it doesn't require a perfect hash. There are collision mitigations. In practice there several that can get to O(1). I'm not sure if there is a way to achieve O(1) in the worst case. But the worst case can be made arbitrarily unlikely, even against adversarial inputs.
  • 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 ago
      It'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 ago
        https://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.