On 21.03.2012 10:29, Philip Martin wrote: > In passing I note that the way APR "randomises" the hash is not all > that random. It just adds a fixed prefix to the keys passed to the > default hash function. I thought the point of the APR change was to > make it harder for the user to predict hash collisions and I do wonder > whether this has been achieved. If two strings S1 and S2 collide then > does adding a constant prefix stop the collision?
Yes, it does; however, since the prefix is constant per hash table, it won't change the total number of collisions. The point of the randomization is that collisions aren't predictable amongst different hash table instances, which makes collision-based DoS attacks a bit harder. Which was the whole point of the exercise. Anyway, if we're aiming for stable ordering in the output, and the data are currently stored in a hash table, then the only sane option is to sort the data, not make the hash function more predictable. -- Brane
