[STL] SGI et leur extension hash_* : coup de gueule et solutions

SGI et leur extension hash_* : coup de gueule et solutions [STL] - C++ - Programmation

Marsh Posté le 15-06-2003 à 01:43:54    

Code :
  1. #ifndef __SGI_STL_HASH_FUN_H
  2. #define __SGI_STL_HASH_FUN_H
  4. #include <stddef.h>
  6. __STL_BEGIN_NAMESPACE
  8. template <class _Key> struct hash { };
  10. inline size_t __stl_hash_string(const char* __s)
  11. {
  12.   unsigned long __h = 0;
  13.   for ( ; *__s; ++__s)
  14.     __h = 5*__h + *__s;
  15.  
  16.   return size_t(__h);
  17. }
  19. __STL_TEMPLATE_NULL struct hash<char*>
  20. {
  21.   size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
  22. };
  24. __STL_TEMPLATE_NULL struct hash<const char*>
  25. {
  26.   size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
  27. };
  29. __STL_TEMPLATE_NULL struct hash<char> {
  30.   size_t operator()(char __x) const { return __x; }
  31. };
  32. __STL_TEMPLATE_NULL struct hash<unsigned char> {
  33.   size_t operator()(unsigned char __x) const { return __x; }
  34. };
  35. __STL_TEMPLATE_NULL struct hash<signed char> {
  36.   size_t operator()(unsigned char __x) const { return __x; }
  37. };
  38. __STL_TEMPLATE_NULL struct hash<short> {
  39.   size_t operator()(short __x) const { return __x; }
  40. };
  41. __STL_TEMPLATE_NULL struct hash<unsigned short> {
  42.   size_t operator()(unsigned short __x) const { return __x; }
  43. };
  44. __STL_TEMPLATE_NULL struct hash<int> {
  45.   size_t operator()(int __x) const { return __x; }
  46. };
  47. __STL_TEMPLATE_NULL struct hash<unsigned int> {
  48.   size_t operator()(unsigned int __x) const { return __x; }
  49. };
  50. __STL_TEMPLATE_NULL struct hash<long> {
  51.   size_t operator()(long __x) const { return __x; }
  52. };
  53. __STL_TEMPLATE_NULL struct hash<unsigned long> {
  54.   size_t operator()(unsigned long __x) const { return __x; }
  55. };
  57. __STL_END_NAMESPACE
  59. #endif /* __SGI_STL_HASH_FUN_H */


 
 
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 :
  1. /* FNV hash algorithm
  3. The core of the FNV hash algorithm is as follows:
  7. hash = offset_basis
  9. for each octet_of_data to be hashed
  11. hash = hash * FNV_prime
  13. hash = hash xor octet_of_data
  15. return hash
  19. NOTES:
  21. hash in an unsigned integer.
  23. The multiplication is performed modulo 2n where n is the bit length of hash.  
  25. The xor is performed on the low order octet (8 bits) of hash.  
  29. The FNV-0 is the historic FNV algorithm. It has an offset_basis of 0.
  31. Use of the historic FNV-0 hash is not recommended. Use FNV-1 with its non-zero offset_basis instead.
  33. The FNV-0 hashes all buffers that contain only 0 octets to a hash value of 0.
  35. The FNV-1 does not suffer from this minor problem. The only difference between FNV-0 and FNV-1offset_basis.
  41. The offset_basis for FNV-1 is dependent on n, the size of the hash:  
  43. 32 bit hash: offset_basis is 2166136261
  45. 64 bit hash: offset_basis is 14695981039346656037  
  47. These non-zero integers are the FNV-0 hashes of the following 32 octets:  
  49. chongo <Landon Curt Noll> /\../\
  51. The FNV_prime is dependent on n, the size of the hash:  
  53. 32 bit hash: FNV_prime is 16777619
  55. 64 bit hash: FNV_prime is 1099511628211  
  57. Part of the magic of FNV is the selection of the FNV_prime for a given sized unsigned integer.
  59. Some primes do hash better than other primes for a given integer size.
  61. The theory behind which primes are good FNV_prime's and which are not as good is beyond the scope of this web page */
  67. unsigned FNV_hashkey(const string &str)
  68. {
  69.   unsigned hash=2166136261u;
  70.   const string::size_type str_size(str.size());
  72.   for(string::size_type i=0; i<str_size; hash=(hash*16777619u)^str[i++]);
  74.   return hash;
  75. }


 
 
comment faire un objet-fonction propre servant de "hachoire" pour les objets de type MonType?
 

Code :
  1. struct Hachoire
  2. {
  3.   unsigned operator()(const MonType &rhs) const
  4.   {
  5.     // faites vos opérations ici
  6.     return valeur_de_hachage;
  7.   }
  8. };


 
il ne vous reste plus qu'a vous en servir
 

Code :
  1. hash_map< MonType, MonAutreType, Hachoire> mappa;


 
j'espere que ça vous as intéressé  :)


Message édité par Taz le 15-06-2003 à 11:50:40
Reply

Marsh Posté le 15-06-2003 à 01:43:54   

Reply

Marsh Posté le 15-06-2003 à 08:17:49    

Mon dieux ....
et je me demandais pourquoi mes mprog aves hash_ ca merdait ....
Arf les nuls.
 
Merci ++Taz :D

Reply

Marsh Posté le 15-06-2003 à 08:37:33    

++Taz a écrit :

[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)
 
unsigned FNV_hashkey(const string &str)
{
  unsigned hash=2166136261u;
  const string::size_type str_size(str.size());
 
  for(string::size_type i=0; i<str_size; hash=(hash*16777619u)^ch[i++]);
 
  return hash;
}


 
Eh ! tu es sur que ta paire
d'entier ne fait pas l'objet d'un brevet ?
 
Je ne voudrais pas aller en prison a cause de ca :sweat:
 
LeGreg

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed