3 ms·
To me, the most interesting part: >> Even if [...] worse hash functions will lead to more collisions, the overall speed advantage beats the slightly worse qual
by winnin_the_game 8y ago
To me, the most interesting part:
>> Even if [...] worse hash functions will lead to more collisions, the overall speed advantage beats the slightly worse quality.
- mises 8y agoI'm not sure if that part is correct. If I use something like SHA1 or MD5 (yes, I know they're no longer considered secure), know with essentially 100% certainty that I will not get a collision. This means I don't have to implement chaining, quadratic probing, or another method of collision avoidance. Though it might cost some speed on the end use of the app, it's often easier for initial development because I simply have to write less code. Maybe a more experienced dev can comment on this? Still learning here, and haven't spent time in a lot of large codebases.
- winnin_the_game 8y agoThe strong collision avoidance guarantee is mostly a result of the large space of hashes those functions generate. So, yes, if you have a hashmap with 2^128 slots, you're technically right. But you don't have a hashmap with 2^128 slots. So you have to smash that output space into a smaller space somehow. And then you're back to considering what to do when you have collisions.