4 ms·

a hash function that produce hashes that are already in the hash table should, IMO, not be called a hash function. I get why technically it is a hash function,

a hash function that produce hashes that are already in the hash table should, IMO, not be called a hash function. I get why technically it is a hash function, but still, no.

phinnaeus 7mo ago
Here is a hash function that does not have hash collisions: fn hash(data): return data
- Charon77 7mo ago
  Well it no longer constrains the data in a fixed output length.
  - dbdr 7mo ago
    Sure, but if you constrain to fixed output length, you will definitely have collisions (Pigeon Hole Principle). There's no way around that.
    - hsbauauvhabzb 7mo ago
      padding with zeroes to a fixed length and prepending the original length would suffice, but you’d have to have a fixed length of double infinity to account for both the length information and the hash information, and the hash is less efficient than the original information.
- oliver236 7mo ago
  what programming language is this?
- tux3 7mo ago
  That is a function, but not a hash function!
ahazred8ta 7mo ago
A perfect hash function https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function has to be specially constructed for each desired set of inputs. Generic hash functions cannot be 'perfect'.
baruch 7mo 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 7mo 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.
  - kro 7mo 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 7mo 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 7mo 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 7mo ago

a hash function that produce hashes that are already in the hash table should, IMO, not be called a hash function. I get why technically it is a hash function, but still, no.

phinnaeus 7mo ago

Here is a hash function that does not have hash collisions: fn hash(data): return data

Charon77 7mo ago
Well it no longer constrains the data in a fixed output length.
- dbdr 7mo ago
  Sure, but if you constrain to fixed output length, you will definitely have collisions (Pigeon Hole Principle). There's no way around that.
  - hsbauauvhabzb 7mo ago
    padding with zeroes to a fixed length and prepending the original length would suffice, but you’d have to have a fixed length of double infinity to account for both the length information and the hash information, and the hash is less efficient than the original information.
oliver236 7mo ago
what programming language is this?
tux3 7mo ago
That is a function, but not a hash function!

ahazred8ta 7mo ago

A perfect hash function https://en.wikipedia.org/wiki/Perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function has to be specially constructed for each desired set of inputs. Generic hash functions cannot be 'perfect'.

baruch 7mo 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 7mo 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.
- kro 7mo 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 7mo 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 7mo 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 7mo ago