Re:God: Scalable in Memory Data Structure Server in Go
by wisty on Tuesday February 05, 2013 @09:47PM
(#5174642)
Python'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.
Re:God: Scalable in Memory Data Structure Server in Go
by kibwen on Tuesday February 05, 2013 @10:28PM
(#5174745)
Hash randomization was actually enabled by default in Python 3.3.
http://docs.python.org/3/whatsnew/3.3.html#summary-release-h...
Re:God: Scalable in Memory Data Structure Server in Go
by slurgfest on Tuesday February 05, 2013 @11:03PM
(#5174810)
Which means this is not available in PyPy? :(
Re:God: Scalable in Memory Data Structure Server in Go
by wisty on Tuesday February 05, 2013 @11:21PM
(#5174856)
python -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).
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 has examples of collision rates for different hashes, all non-cryptographic.