on a pas du aller au meme cours sur le hachage je pense: ce sont là les fonctions de hashage les plus mauvaises que j'ai jamais vu. C'est la garantie de mauvaise performance lors de l'utilisation des hash_* de SGI.
si vous utilisez cette extension avec les types déjà pris en charge par SGI, vous pouvez améliorez tout ça en redéfinissant tres vite un hasher. pour les types entiers de base, un petit xor et quelques rotations de bits me paraissent les bienvenus. pour les string et par réduction pour les char *, j'utilise courrement ça (il en existe beaucoup d'autres)
Code :
/* FNV hash algorithm
The core of the FNV hash algorithm is as follows:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash * FNV_prime
hash = hash xor octet_of_data
return hash
NOTES:
hash in an unsigned integer.
The multiplication is performed modulo 2n where n is the bit length of hash.
The xor is performed on the low order octet (8 bits) of hash.
The FNV-0 is the historic FNV algorithm. It has an offset_basis of 0.
Use of the historic FNV-0 hash is not recommended. Use FNV-1 with its non-zero offset_basis instead.
The FNV-0 hashes all buffers that contain only 0 octets to a hash value of 0.
The FNV-1 does not suffer from this minor problem. The only difference between FNV-0 and FNV-1offset_basis.
The offset_basis for FNV-1 is dependent on n, the size of the hash:
32 bit hash: offset_basis is 2166136261
64 bit hash: offset_basis is 14695981039346656037
These non-zero integers are the FNV-0 hashes of the following 32 octets:
chongo <Landon Curt Noll> /\../\
The FNV_prime is dependent on n, the size of the hash:
32 bit hash: FNV_prime is 16777619
64 bit hash: FNV_prime is 1099511628211
Part of the magic of FNV is the selection of the FNV_prime for a given sized unsigned integer.
Some primes do hash better than other primes for a given integer size.
The theory behind which primes are good FNV_prime's and which are not as good is beyond the scope of this web page */
[cpp]
si vous utilisez cette extension avec les types déjà pris en charge par SGI, vous pouvez améliorez tout ça en redéfinissant tres vite un hasher. pour les types entiers de base, un petit xor et quelques rotations de bits me paraissent les bienvenus. pour les string et par réduction pour les char *, j'utilise courrement ça (il en existe beaucoup d'autres)