C++

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

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [STL] SGI et leur extension hash_* : coup de gueule et solutions

Taz

bisounours-codeur

Code :

#ifndef __SGI_STL_HASH_FUN_H
#define __SGI_STL_HASH_FUN_H
#include <stddef.h>
__STL_BEGIN_NAMESPACE
template <class _Key> struct hash { };
inline size_t __stl_hash_string(const char* __s)
{
unsigned long __h = 0;
for ( ; *__s; ++__s)
__h = 5*__h + *__s;
return size_t(__h);
}
__STL_TEMPLATE_NULL struct hash<char*>
{
size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
__STL_TEMPLATE_NULL struct hash<const char*>
{
size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
__STL_TEMPLATE_NULL struct hash<char> {
size_t operator()(char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned char> {
size_t operator()(unsigned char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<signed char> {
size_t operator()(unsigned char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
size_t operator()(short __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
size_t operator()(unsigned short __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
size_t operator()(int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
size_t operator()(unsigned int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
size_t operator()(long __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
size_t operator()(unsigned long __x) const { return __x; }
};
__STL_END_NAMESPACE
#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 :

/* 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 */
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)^str[i++]);
return hash;
}

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

Code :

struct Hachoire
{
unsigned operator()(const MonType &rhs) const
{
// faites vos opérations ici
return valeur_de_hachage;
}
};

il ne vous reste plus qu'a vous en servir

Code :

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

Publicité

Joel F

Real men use unique_ptr

Mon dieux ....
et je me demandais pourquoi mes mprog aves hash_ ca merdait ....
Arf les nuls.

Merci ++Taz

LeGreg

++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

FORUM HardWare.fr

Programmation

C++

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

Sujets relatifs
p'tit coup de main pour debuguer un code?	[Perl] Hash et cgi
tester l'extension d'un fichier	Hash d'un string
[STL] class string et comparaison non case-sensitive	[STL] list, push_back et ses joyeux amis... Je comprends pas tout
[C/C++] fonction sort() avec STL	Solutions pour gérer les langues dans une app?
Comment afficher en 1 coup un bloc de pixels à l'écran?	tit coup de main sur ANT svp
Plus de sujets relatifs à : [STL] SGI et leur extension hash_* : coup de gueule et solutions

Page générée en 0.083 secondes