C++ HashTable Implémentation d'objets

Question

int hazmat::hashStr(char const * const str) 
{ 
    int count = 0; 
    for (unsigned i = 0; i < strlen(str); i++) 
    { 
     count += str[i]; // get the ascii sum. 
    } 
    return count % maxSize; 
} 

Answer 1

Vous comprenez mal comment fonctionnent les tables de hachage. Vous devez allouer un tableau de longueur fixe (dans le cas le plus simple), puis chaque entrée doit avoir une liste chaînée pour pouvoir résoudre les doublons. Autrement dit, deux chaînes peuvent aboutir à la même valeur de hachage et vous devrez parcourir la liste chaînée et comparer les clés. Et oui, comme l'autre affiche l'a dit, ajouter des caractères est une approche terrible. Pensez-y - "abc" et "cba" donneront la même valeur de hachage.

Answer 2

La somme ASCII n'est pas une bonne fonction de hachage. Voici quelques-unes des explications:

http://www.cse.yorku.ca/~oz/hash.html

Answer 3

Je ne sais pas quel est votre objectif avec cette question. Si votre objectif est de trouver une bonne table de hachage C++, utilisez std :: tr1 :: unordered_map si votre compilateur le supporte, sinon par exemple Google sparse-hash.

Si votre objectif est d'en savoir plus sur les tables de hachage, lisez la suite.

En réponse à this SO question, je mis en place une table de hachage très simple en Java dans my answer:

D'abord, vous devez comprendre une quelle fonction de hachage est. Une fonction de hachage est une fonction qui prend une clé (par exemple, une chaîne de longueur arbitraire) et renvoie un nombre aussi unique que possible. La même clé doit toujours retourner le même hachage. Une fonction de hachage chaîne très simple en Java pourrait ressembler

public int stringHash(String s) { 
    int h = s.length(); 
    for(char c : s.toCharArray()) { 
     h ^= c; 
    } 
    return h; 
} 

Vous pouvez étudier une bonne fonction de hachage à http://www.azillionmonkeys.com/qed/hash.html

Maintenant, la carte de hachage utilise cette valeur de hachage pour placer la valeur dans un tableau. méthode Simplistic java:

public void put(String key, Object val) { 
    int hash = stringHash(s) % array.length; 
    if(array[hash] == null) { 
     array[hash] = new LinkedList<Entry<String, Object> >(); 
    } 
    for(Entry e : array[hash]) { 
     if(e.key.equals(key)){ 
      e.value = val; 
      return; 
     } 
    } 
    e.add(new Entry<String, Object>(key, val)); 
} 

(Cette carte applique des clés uniques Toutes les cartes ne..)

Il est possible pour deux clés différentes de hachage à la même valeur, ou deux différents hachages pour cartographier la même indice de tableau. Il existe de nombreuses techniques pour gérer cela. Le plus simple est d'utiliser une liste chaînée (ou un arbre binaire) pour chaque index de tableau. Si la fonction de hachage est suffisante, vous n'aurez jamais besoin d'une recherche linéaire.

Maintenant, pour rechercher une clé:

public Object get(String key) { 
    int hash = stringHash(key) % array.length; 
    if(array[hash] != null) { 
     for(Entry e : array[hash]) { 
      if(e.key.equals(key)) 
       return e.value; 
     } 
    } 

    return null; 
}