3 ms·
I think "amateurish" is overly harsh here. He sets out a very professionial plan of measuring and testing. It is a nice post. Yes, probably true that requiri
by dzdt 10y ago
I think "amateurish" is overly harsh here. He sets out a very professionial plan of measuring and testing. It is a nice post.
Yes, probably true that requiring a non-broken hash function is strictly better than his preferred prime modulus workaround. Okay, so? If you notice, the whole post keeps comparing a power-of-two version of his hashtable as well. Other than the one graph showing pathological behaviour of dense_hash with in-order inputs, everything in the post applies assuming a reasonable hash function.
- ot 10y agoI didn't mean "amateurish" in a judgmental way, it's a matter of fact that the author is a novice when it comes to hash tables. He himself admits that he doesn't understand some of the details ("Why do prime numbers help? I can’t quite explain the math behind that"), so he gets some of the conclusions wrong. > Other than the one graph showing pathological behaviour of dense_hash with in-order inputs That's a pathological behavior of std::hash, not of dense_hash. > everything in the post applies assuming a reasonable hash function. No, see this paragraph: All of these problems are solvable if you’re careful about choosing a hash function that’s appropriate for your inputs. But that’s not a good user experience: You now always have to be vigilant when using hashtables. Sometimes that’s OK, but sometimes you just want to not have to think too much about this. You just want something that works and doesn’t randomly get slow. That’s why I decided to make my hashtable use prime number sizes by default and to only give an option for using powers of two. The belief is that prime number sizes will defend you against poor hash function. That's a very dangerous advice.