Le dimanche 01 janvier 2012 à 17:34 +0100, Christian Heimes a écrit :
Am 01.01.2012 17:09, schrieb Antoine Pitrou:
On Sun, 01 Jan 2012 16:48:32 +0100 Christian Heimes email@example.com wrote:
The talkers claim and have shown that it's too easy to pre-calculate collisions with hashing algorithms similar to DJBX33X / DJBX33A. It might be a good idea to change the hashing algorithm, too. Paul as listed some new algorithms. Ruby 1.9 is using FNV http://isthe.com/chongo/tech/comp/fnv/ which promises to be fast with a good dispersion pattern.
We already seem to be using a FNV-alike, is it just a matter of changing the parameters?
No, we are using something similar to DJBX33X. FNV is a completely different type of hash algorithm.
I don't understand. FNV-1 multiplies the current running result with a prime and then xors it with the following byte. This is also what we do. (I'm assuming 1000003 is prime)
I see two differences: - FNV starts with a non-zero constant offset basis - FNV uses a different prime than ours
(as a side note, FNV operates on bytes, but for unicode we must operate on code points in [0, 1114111]: although arguably the common case is hashing ASCII substrings (protocol tokens etc.))