3 ms·
To be fair 2^64 keys is a lot, to the point that it cannot possibly fit into memory with today’s hardware.
by stingraycharles 6y ago
To 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]