4 ms·
I agree that not storing keys is riskier, and it's not a risk that's mitigated even if it is a perfect uniform distribution because you can still have collision
by graderjs 6y ago
I agree that not storing keys is riskier, and it's not a risk that's mitigated even if it is a perfect uniform distribution because you can still have collisions. Maybe I don't understand the reasons for that design but personally I don't think it's a good design for a hash table. But even so the hash underlying it is a very good hash.
Big crush and smhasher give a good indication of uniform distribution, but nothing can guarantee no collisions because you're always going to have collisions it's always a possibility. Even if you have a perfect permutation of the 64 bit space, the minute you go beyond 64 bits of keys you're going to collide within 64 bits of hash.
By all the tests they run md5 is a much poorer hash than many others. But it's a or it was a cryptographic hash. It's different.
- stingraycharles 6y agoTo be fair 2^64 keys is a lot, to the point that it cannot possibly fit into memory with today’s hardware.
- Bootvis 6y agoAccording to the Birthday paradox you can expect a collision after approx 2^32 keys. Whether this is small or big probably depends on your use case.
- kaoD 6y agoBut even after only one item is inserted the probability of collision is >0. Yes, it is very very very (very) small, but it's still there!
- hansvm 6y agoWe're getting close. There's way more RAM than that in the world, and a quick search turned up a single machine from a few years ago that was only off by 160x or so. Even without relying on the pigeonhole principle though you still have the birthday paradox. As a ballpark estimate, if you have N keys then you'd expect a 50/50 chance of at least one collision with sqrt(N) hashes -- 2^32 for this problem.
- deleted 6y ago[deleted]