3 ms·
> MurmurHash3 wasn't _designed_ with low collision rates in mind There is a difference between "low collision rate" and "collision resistance". Real-world dat
by tveita 14y ago
> MurmurHash3 wasn't _designed_ with low collision rates in mind
There is a difference between "low collision rate" and "collision resistance".
Real-world data often contain regular patterns that can cause "bad" hash functions to give very non-random output, e.g. numbers at fixed intervals, pointers all aligned to 4k boundaries, or long strings that differ only by a short suffix.
For instance, early versions of Java would sample only a few of the characters in a long string to calculate the hash code, which caused horrendous performance if you stored a bunch of related file paths in a hash map.
Most hash functions try to avoid bad behaviour on this kind of good-natured input, but some are better at it than others, due to careful design for random-like distribution, and low collision rates.
http://www.strchr.com/hash_functions http://www.strchr.com/hash_functions has examples of collision rates for different hashes, all non-cryptographic.
- wisty 14y agoPython's hash, for example, will generate lower collisions than a "good" hash function. 'file1', 'file2', and 'file3' will not collide, but end up in sequential boxes, which is very efficient. Of course, you can send python web apps a "cookie of death", in which all cookies collide. There's a patch, but I think it's disabled by default.
- kibwen 14y agoHash randomization was actually enabled by default in Python 3.3. http://docs.python.org/3/whatsnew/3.3.html#summary-release-highlights http://docs.python.org/3/whatsnew/3.3.html#summary-release-h...
- slurgfest 14y agoWhich means this is not available in PyPy? :(
- wisty 14y agopython -R should enable it in 2.X (in the patched version, 2.7.3 is fine). PyPy does not include hash randomization (see http://doc.pypy.org/en/latest/cpython_differences.html http://doc.pypy.org/en/latest/cpython_differences.html).