Créer une Table de hachage avec deux tableaux
est-ce que quelqu'un sait comment faire ceci et à quoi ressemblerait le pseudo code?
comme nous savons tous qu'une table de hachage stocke la clé,les paires de valeurs et quand une clé est appelée, la fonction retournera la valeur associée à cette clé. Ce que je veux faire, c'est comprendre la structure sous-jacente à la création de cette fonction de cartographie. Par exemple, si nous vivions dans un monde où il n'y avait pas de fonctions prédéfinies à l'exception des tableaux, comment pourrions-nous répliquer les Hashmaps que nous avons aujourd'hui?
4 réponses
en fait, certaines Implantations Hashmap d'aujourd'hui sont en effet faites de tableaux comme vous le proposez. Permettez-moi d'esquisser comment cela fonctionne:
Fonction De Hachage Une fonction de hachage transforme vos clés en index pour le premier tableau (tableau K). Une fonction de hachage telle que MD5 ou une fonction plus simple, comprenant habituellement un opérateur modulo, peut être utilisée à cette fin.
Seaux Une implémentation HashMap basée sur un tableau simple pourrait utiliser des seaux pour gérer les collissions. Chaque élément ('bucket') dans le tableau K contient lui-même un tableau (tableau P) de paires. Lors de l'ajout ou de la requête d'un élément, la fonction de hachage vous indique le bon seau en K, qui contient votre tableau désiré P. vous itérez alors au-dessus des éléments en P jusqu'à ce que vous trouviez une clé correspondante, ou vous assignez un nouvel élément à la fin de P
Mappage des touches de seaux à l'aide de la table de Hachage Vous devez vous assurer que le nombre de seaux (i.e. la taille de K) est une puissance de 2, let's disons 2 ^ B. Pour trouver l'index de seau correct pour une certaine clé, calculer le Hash(clé), mais ne garder que les premiers bits B. C'est votre indice de fonte d'un entier.
changement d'échelle Calculer le hachage d'une clé et trouver le bon seau est très rapide. Mais une fois qu'un seau devient plus complet, vous devrez itérer de plus en plus d'éléments avant d'arriver à la bonne. Il est donc important d'avoir assez de seaux pour bien distribuer les objets, sinon votre Hashmap deviendra lent.
parce que vous ne savez généralement pas combien d'objets vous voulez stocker dans le Hashmap à l'avance, il est souhaitable de développer dynamiquement ou rétrécir la carte. Vous pouvez garder un compte du nombre d'objets stockés, et une fois qu'il passe un certain seuil, vous recréer la structure entière, mais cette fois avec une plus grande ou plus petite taille pour le tableau K. DE cette façon, certains des seaux en K qui étaient très pleins auront maintenant leurs éléments divisés en plusieurs seaux, de sorte que les performances seront meilleures.
Alternatives Vous pouvez également utiliser un tableau bidimensionnel au lieu d'un tableau de tableaux, ou vous pouvez échanger le tableau P pour une liste liée. En outre, au lieu de garder un nombre total d'objets stockés, vous pouvez simplement choisir de recréer (c'est-à-dire rééchelonner) le hashmap une fois que l'un des seaux contient plus qu'un certain nombre d'éléments configurés.
une variation de ce que vous demandez est décrite comme' tableau de hachage ' dans le table de hachage Wikipedia entry.
Code Pour des exemples de code, regardez ici.
J'espère que cela vous aidera.
Pourriez-vous être plus précis? T un tableau contenant les clés, l'autre les valeurs?
Si oui, voici un exemple en Java (mais il y a quelques spécificités de cette langue ici):
for (int i = 0; i < keysArray.length; i++) {
map.put(keysArray[i], valuesArray[i]);
}
bien sûr, vous aurez pour instancier votre map objet (si vous utilisez Java, je suggère d'utiliser un HashMap<Object, Object> au lieu d'un objet HashTable), et testez aussi vos tableaux pour éviter null objets et vérifiez s'ils ont la même taille.
Exemple D'Explication:
à la source ci-dessous, fondamentalement, il fait deux choses:
1. Représentation Cartographique
- (X numéro de la Liste) de listes
- X être 2 puissance N nombre de listes est mauvais. (2 puissance N)-1, ou (2 puissance N)+1, ou un nombre premier est bonne.
Exemple:
List myhashmap [hash_table_size];
// an array of (short) lists
// if its long lists, then there are more collisions
NOTE: tableau de tableaux, pas deux tableaux (je ne peux pas voir une possible générique hashmap, dans le bon sens avec seulement 2 tableaux)
si vous connaissez des algorithmes > théorie des graphes > liste de contiguïté, ceci regarde exactement les mêmes.
2. Fonction de hachage
et la fonction de hachage convertit la chaîne (input) en un nombre (valeur de hachage), qui est l'index d'un tableau
- initialiser la valeur de hachage du premier char (après la conversion int)
- pour chaque nouveau caractère, déplacement à gauche de 4 bits, puis ajouter le caractère (après conversion en int)
Exemple
int hash = input[0];
for (int i=1; i<input.length(); i++) {
hash = (hash << 4) + input[i]
}
hash = hash % list.size()
// list.size() here represents 1st dimension of (list of lists)
// that is 1st dimension size of our map representation from point #1
// which is hash_table_size
le Voir sur le premier lien:
int HTable::hash (char const * str) const
Source:
http://www.relisoft.com/book/lang/pointer/8hash.html
Comment fonctionne une table de hachage de travail?
mise à Jour
C'est la Meilleure source: http://algs4.cs.princeton.edu/34hash/
ce qui suit utiliseirb à titre d'illustration:
cities = ["LA", "SF", "NY"]
=> ["LA", "SF", "NY"]
items = ["Big Mac", "Hot Fudge Sundae"]
=> ["Big Mac", "Hot Fudge Sundae"]
price = {}
=> {}
price[[cities[0], items[1]]] = 1.29
=> 1.29
price
=> {["LA", "Hot Fudge Sundae"]=>1.29}
price[[cities[0], items[0]]] = 2.49
=> 2.49
price[[cities[1], items[0]]] = 2.99
=> 2.99
price
=> {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99}
price[["LA", "Big Mac"]]
=> 2.49