BTW, there are methods to avoid collisions: perfect hashing & cuckoo hashing. I have not tried the latter, but the former seems to be a 2-3x times slower than regular hashing on average despite having “ideal” properties.
Cuckoo hashing assumes some degree of “randomness” (as measured by k-wise independence). So while it is interesting in how it deals with collisions, it does not do away with the question of how much randomness is involved.
Grahamsays:
I like the fact that a man named Pigeon is investigating the Pigeonhole Principle.
A single collision is not necessarily bad.
Of course, they are not. The question, is how far do they diverge from randomness?
BTW, there are methods to avoid collisions: perfect hashing & cuckoo hashing. I have not tried the latter, but the former seems to be a 2-3x times slower than regular hashing on average despite having “ideal” properties.
No. My only point is that treating hash values as if they are truly random can be misleading.
@Itman
Cuckoo hashing assumes some degree of “randomness” (as measured by k-wise independence). So while it is interesting in how it deals with collisions, it does not do away with the question of how much randomness is involved.
I like the fact that a man named Pigeon is investigating the Pigeonhole Principle.