apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bojan Smojver" <bo...@rexursive.com>
Subject Re: svn commit: r1237078 - /apr/apr/trunk/tables/apr_hash.c
Date Sun, 29 Jan 2012 12:56:31 GMT
------- Original message -------
> From: Ruediger Pluem

> Don't we have the same issue here as with the XOR version of the patch?
> If two different keys (key1, key2) result in the same hash value (so 
> ht->hash_func(key1, &klen1) == ht->hash_func(key2,
> &klen2);) doesn't hashfunc_default result in the same hash value for both 
> keys since the input value to hash
> is the same?

For two keys to cause a collision, the modulo (i.e. the index) has to be 
the same, not necessarily the whole hash. So, with xor, we don't gain 
anything by using seed against the final hash (modulo will change, but in 
the same way for both hash values - the collision will move to a different 
bucket). With the hash function, as long as the hash is not completely the 
same, we will most likely get a different modulo and therefore a different 
index into the table.

Make sense?


View raw message