7 ms·

It is mathematically impossible for a proper hash function (one with an output range smaller than its input range) to not have collisions. The proof uses the Pi

by baruch 5mo ago

It is mathematically impossible for a proper hash function (one with an output range smaller than its input range) to not have collisions. The proof uses the Pigeon Hole Principle https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle

bryanrasmussen 5mo ago
ok damn, I did not know this, obviously. Thanks. I guess I've never actually had this problem because was always hashing things that were static, or specialty cases like password hashes where the salt obviously guarantees uniqueness.
- deleted 5mo ago
  [deleted]
- kro 5mo ago
  It's very very unlikely to get collisions there, but still not impossible. Whenever you map data of arbitrary length (infinite possibilities) to a limited length collisions are possible.
  - eru 5mo ago
    Doesn't even have to be arbitrary length. Whenever you map into a smaller space, you get collisions. The bigger space doesn't have to be infinite.
    - bryanrasmussen 5mo ago
      with a password you may be mapping into a smaller space or a bigger space, because what you want is to get them all same length, but yeah you may in some cases be mapping into a smaller space, hadn't thought of that, although I sort of also think it is unlikely. But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide even if they could in theory.
      - eru 5mo ago
        For passwords: the input _space_ is bigger. That doesn't say anything about the length of any particular password. > But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide even if they could in theory. For passowrds, you are not worried so much about two users accidentally getting the same hash, you are worried about people finding a pre-image that hashes to the same output as your user's password.
        bryanrasmussen 5mo ago
        >For passowrds, you are not worried so much about two users accidentally getting the same hash right I was thinking I've probably personally never had a situation where a collision would have affected anything, but then I thought of one, when I had to do image hashing it was a potential problem.
- ogogmad 5mo ago
  Let's consider a hash table with an allocation of 1MB, which is about 2^20 bytes. Assume also that each entry occupies a byte. Assuming that the hash function's values are distributed randomly, the probability of there being a collision with only 1000 entries is approximately 38% = 1-(2^20)!/(2^20 - 1000)!/(2^20)^1000. See the "Birthday Problem".

by baruch 5mo ago

bryanrasmussen 5mo ago

ok damn, I did not know this, obviously. Thanks. I guess I've never actually had this problem because was always hashing things that were static, or specialty cases like password hashes where the salt obviously guarantees uniqueness.

deleted 5mo ago
[deleted]
kro 5mo ago
It's very very unlikely to get collisions there, but still not impossible. Whenever you map data of arbitrary length (infinite possibilities) to a limited length collisions are possible.
- eru 5mo ago
  Doesn't even have to be arbitrary length. Whenever you map into a smaller space, you get collisions. The bigger space doesn't have to be infinite.
  - bryanrasmussen 5mo ago
    with a password you may be mapping into a smaller space or a bigger space, because what you want is to get them all same length, but yeah you may in some cases be mapping into a smaller space, hadn't thought of that, although I sort of also think it is unlikely. But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide even if they could in theory.
    - eru 5mo ago
      For passwords: the input _space_ is bigger. That doesn't say anything about the length of any particular password. > But there it doesn't matter anyway because the password is put together with the email to identify the user so in practicality passwords will never collide even if they could in theory. For passowrds, you are not worried so much about two users accidentally getting the same hash, you are worried about people finding a pre-image that hashes to the same output as your user's password.
      - bryanrasmussen 5mo ago
        >For passowrds, you are not worried so much about two users accidentally getting the same hash right I was thinking I've probably personally never had a situation where a collision would have affected anything, but then I thought of one, when I had to do image hashing it was a potential problem.
ogogmad 5mo ago
Let's consider a hash table with an allocation of 1MB, which is about 2^20 bytes. Assume also that each entry occupies a byte. Assuming that the hash function's values are distributed randomly, the probability of there being a collision with only 1000 entries is approximately 38% = 1-(2^20)!/(2^20 - 1000)!/(2^20)^1000. See the "Birthday Problem".