upvote

points

by bryanrasmussen7 hours ago |
comments
upvoteby baruch6 hours ago|
next
[-]
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
reply
upvoteby bryanrasmussen5 hours ago|
parent|
[-]
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.

reply
upvoteby 3 hours ago|
parent|
next
[-]
deleted
reply
upvoteby kro4 hours ago|
parent|
prev|
next
[-]
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.
reply
upvoteby eru4 hours ago|
parent|
[-]
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.

reply
upvoteby bryanrasmussen13 minutes ago|
parent|
[-]
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.

reply
upvoteby eru8 minutes ago|
parent|
[-]
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.

reply
upvoteby ogogmad2 hours ago|
parent|
prev|
[-]
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".
reply
upvoteby ahazred8ta6 hours ago|
prev|
next
[-]
A 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'.
reply
upvoteby phinnaeus7 hours ago|
prev|
[-]
Here is a hash function that does not have hash collisions:

  fn hash(data):
    return data
reply
upvoteby tux33 hours ago|
parent|
next
[-]
That is a function, but not a hash function!
reply
upvoteby Charon776 hours ago|
parent|
prev|
next
[-]
Well it no longer constrains the data in a fixed output length.
reply
upvoteby dbdr5 hours ago|
parent|
[-]
Sure, but if you constrain to fixed output length, you will definitely have collisions (Pigeon Hole Principle). There's no way around that.
reply
upvoteby hsbauauvhabzb5 hours ago|
parent|
[-]
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.
reply
upvoteby oliver2365 hours ago|
parent|
prev|
[-]
what programming language is this?
reply