Conception d'une table de hachage

Vous avez besoin d'un tableau de listes, ou des "compartiments" pour vos valeurs. Ensuite, vous utilisez une fonction de hachage pour déterminer l'élément de tableau de regarder dans, et enfin faire une recherche linéaire dans les éléments de la liste.

Vous avez constante recherche de la matrice de localisation, et de la recherche linéaire des valeurs de hachage dans la petite liste.

OriginalL'auteur Winger

Utiliser un tableau => O(1)

Donc, si vous voulez utiliser une fonction de hachage pour activer votre clé à un numéro, puis utiliser ce numéro comme un index dans un tableau pour récupérer la valeur.

OriginalL'auteur fxtentacle

Une table de hachage fournit un moyen d'insérer et d'extraire des données de manière efficace (généralement en constante/O(1)). Pour cela, nous utilisons un très grand tableau pour enregistrer la cible des valeurs et une fonction de hachage qui généralement les cartes de la cible de valeurs, dans des valeurs de hachage qui n'est rien d'autre que de la validité des indices dans ce grand tableau. Une fonction de hachage parfaite hache une des valeurs stockées dans une clé unique (ou l'index dans le tableau) est connu comme un parfait fonction de hachage. Mais, dans la pratique de stocker ces valeurs pour lesquelles il n'existe aucun moyen d'obtenir unique des valeurs de hachage (indices dans le tableau), nous avons l'habitude d'utiliser une fonction de hachage qui peut correspondre chaque valeur d'indice particulier de sorte que la collision peut être maintenu à un minimum. Ici collision signifie que deux ou plusieurs éléments à être stockées dans la table de hachage carte de la même valeur de hachage.

Maintenant les questions originales, qui est:
"La conception d'une table de Hachage, Vous pouvez utiliser n'importe quelle structure de données, vous pouvez vous souhaitez. Je voudrais voir comment mettre en œuvre le O(1) pour le temps". Enfin, il a dit qu'Il est plus comme la simulation d'une table de Hachage via une autre structure de Données."

Recherche est possible dans exactement O(1) fois, dans des cas, on peut concevoir une fonction de hachage parfait. Les données sous-jacentes de la structure est encore un tableau. Mais cela dépend du stockage de valeurs, si l'on peut concevoir une fonction de hachage parfait ou pas. Par exemple, considérons les chaînes à l'alphabet anglais. Depuis, il n'existe pas de fonction de hachage qui peut correspondre chaque anglais valide mot de un unique int (32 bits) (ou long long int 64 bits), donc il y aura toujours certaines collisions. Pour faire face en cas de collision, nous pouvons utiliser des chaînage de méthode de collision de la manipulation dans laquelle chaque table de hachage fente stocke un pointeur vers la liste liée, qui stocke en fait tous les éléments de hachage à cette machine à sous particulière ou d'un index. Par exemple, considérons une fonction de hachage qui considère chaque alphabet anglais de la chaîne comme un certain nombre sur la base de 26 (parce qu'il y a 26 caractères dans l'alphabet anglais), Ce qui peut être codé comme:

unsigned int hash(const std::string& word)
{
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);
    unsigned int key=0;
    for(int i=0;i<word.length();++i)
    {
         key = (key<<4) + (key<<3)+(key<<2) + word[i];
         key = key% tableSize;
    }
    return key;
}

Où taille_table est bien choisi le premier numéro vient de de plus que le nombre total de dictionnaire anglais mots destinés à être stockés dans la table de hachage.

Voici les résultats avec un dictionnaire de taille 144554, et le tableau de taille = 144563:

[Articles de la cartographie à la même cellule --> Nombre de slots dans la table de hachage ] =======>

[ 0  -->   53278 ]
[1 --> 52962 ]
[2 --> 26833 ]
[3 --> 8653  ]
[4 --> 2313 ]
[5 --> 437 ]
[6  --> 78 ]
[7  -->  9 ]

Dans ce cas de rechercher les éléments qui ont été associées à des cellules contenant un seul élément, la recherche sera O(1), mais dans ce cas elle correspond à une cellule qui a plus de 1 éléments, alors que nous avons à parcourir cette liste, qui peut contenir de 2 à 7 nœuds et alors nous serons en mesure de trouver cet élément. Donc ce n'est pas constant dans ce cas.

De sorte qu'il dépend de la disponibilité de la fonction de hachage parfait seulement, si nous la recherche peut être effectuée en O(1) contrainte. Sinon, il ne sera pas exactement O(1) mais très proche de lui.

OriginalL'auteur js2016