Comment puis-je Hasher une chaîne sur un int en utilisant c++?
je dois écrire ma propre fonction de hachage. Si je voulais juste faire la fonction de hachage simple qui mappe chaque lettre dans la chaîne à une valeur numérique (i.e. a=1, b=2, c=3, ...), est-il une manière que je peux effectuer cette hachage sur une chaîne sans avoir à le convertir en un c-string pour regarder chaque char? Est-il un moyen plus efficace de hachage cordes?
9 réponses
Re la première question, bien sûr, E. g, something like:
int hash = 0;
int offset = 'a' - 1;
for(string::const_iterator it=s.begin(); it!=s.end(); ++it) {
hash = hash << 1 | (*it - offset);
}
en ce qui concerne le second, il y a beaucoup de meilleures façons de hacher les chaînes. E. g., voir ici pour un peu de C exemples (facilement traduisibles en C++ le long des lignes de l'extrait ci-dessus).
D'après mon expérience personnelle, je sais que cela fonctionne et produit de bonnes distributions. (Plagié de http://www.cse.yorku.ca/~oz/hash.html):
djb2
cet algorithme (k=33) a été rapporté pour la première fois par dan bernstein il y a de nombreuses années dans comp.lang.C. une autre version de cet algorithme (maintenant favorisée par bernstein) utilise xor: hash(i) = hash (i - 1) * 33 ^ str[i]; la magie du nombre 33 (pourquoi il fonctionne mieux que beaucoup d'autres constantes, prime ou pas) n'a jamais été expliquée de manière adéquate.
unsigned long hash(unsigned char *str) {
unsigned long hash = 5381;
int c;
while (c = *str++) {
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
}
return hash;
}
Vous pouvez examiner chaque char individuel à partir d'une chaîne std::en utilisant le [] opérateur. Cependant, vous pouvez regarder Boost::Fonctionnel/Hachage pour obtenir des conseils sur un meilleur système de hachage. Il existe également une liste de fonctions de hachage dans c situé ici.
int hash(const char *str)
{
int h = 0;
while (*str)
h = h << 1 ^ *str++;
return h;
}
si vous l'utilisez pour une table de hachage (ce que Stroustrup fait) alors vous pouvez retourner l'abs du hachage modulo un nombre premier. Ainsi, au lieu
return (h > 0 ? h : -h) % N_BUCKETS;
pour la dernière ligne.
C++11 est livré avec un standard de la fonction de hachage pour les chaînes.
https://en.cppreference.com/w/cpp/string/basic_string/hash
#include <string>
#include<functional> // hash
int main(){
std::string s = "Hello";
std::size_t hash = std::hash<std::string>{}(s);
}
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// a variation on dan bernstein's algorithm
// [http://www.cse.yorku.ca/~oz/hash.html]
template<typename Int>
struct hash {
hash() : acc(5381) { }
template<typename Ch>
void operator()(Ch ch) { acc = ((acc << 5) + acc) ^ ch; }
operator Int() const { return acc; }
Int acc;
};
int main(int argc, char* argv[])
{
string s("Hellp, world");
cout << hex << showbase
<< for_each(s.begin(), s.end(), hash<unsigned long long>()) << '\n';
return 0;
}
une Autre façon pour les petites chaînes de caractères:
int hash(const char* str) {
int hash = 0;
int c = 0;
while (c < std::strlen(str)) {
hash += (int)str[c] << (int)str[c+1];
c++;
}
return hash;
}
Vous pouvez utiliser les fonctions de membre operator [] ou de la classe string ou des itérateurs pour accéder au char individuel d'un objet string sans le convertir en un tableau de char de style c.
pour Hasher un objet string sur un entier, vous devrez accéder à chaque char individuel de l'objet string que vous pouvez faire comme:
for (i=0; i < str.length(); i++) {
// use str[i] or str.at(i) to access ith element.
}