Les bases des tables de hachage?
https://stackoverflow.com/questions/282712
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis assez confus quant aux concepts de base d'une table de hachage. Si je devais coder un hachage, comment pourrais-je même commencer? Quelle est la différence entre une table de hachage et juste un tableau normal?
En gros, si quelqu'un répondait à cette question, je pense qu'il serait répondu à toutes mes questions: Si j'avais 100 nombres générés aléatoirement (en tant que clés), comment pourrais-je implémenter une table de hachage et pourquoi cela serait-il avantageux par rapport à un tableau?
Psuedo-code ou Java serait apprécié comme outil d’apprentissage ...
La solution
Jusqu'à présent, les réponses ont permis de définir des tables de hachage et d'expliquer certaines théories, mais je pense qu'un exemple peut vous aider à mieux vous sentir.
Quelle est la différence entre une table de hachage et juste un tableau normal?
Une table de hachage et un tableau sont deux structures qui vous permettent de stocker et de récupérer des données. Les deux vous permettent de spécifier un index et de récupérer une valeur qui lui est associée. La différence, comme l'a noté Daniel Spiewak, est que les indices d'un tableau sont séquentiels , alors que ceux d'une table de hachage sont basés sur la valeur des données qui leur sont associées.
Pourquoi utiliser une table de hachage?
Une table de hachage peut constituer un moyen très efficace de rechercher des éléments dans de grandes quantités de données, en particulier des données difficiles à interroger. ("Large" désigne ici ginormous , dans le sens où il il faudrait beaucoup de temps pour effectuer une recherche séquentielle).
Si je devais coder un hachage, comment pourrais-je même commencer?
Pas de problème. Le moyen le plus simple consiste à inventer une opération mathématique arbitraire que vous pouvez effectuer sur les données et qui renvoie un nombre N (généralement un entier). Utilisez ensuite ce nombre comme index dans un tableau de "compartiments". et stockez vos données dans le seau # N . L'astuce consiste à sélectionner une opération qui tend à placer les valeurs dans différents compartiments de manière à ce que vous puissiez facilement les retrouver plus tard.
Exemple: Un grand centre commercial conserve une base de données sur les voitures et les emplacements de stationnement de ses clients, afin d'aider les clients à se souvenir de l'endroit où ils se sont garés. La base de données stocke make , couleur , plaque d'immatriculation et emplacement de stationnement . En quittant le magasin, un client trouve sa voiture en entrant sa marque et sa couleur. La base de données renvoie une liste (relativement courte) de plaques d'immatriculation et d'espaces de stationnement. Un balayage rapide localise la voiture de l'acheteur.
Vous pouvez implémenter cela avec une requête SQL:
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
Si les données étaient stockées dans un tableau, qui est essentiellement une liste, vous pouvez implémenter la requête en balayant un tableau pour toutes les entrées correspondantes.
D'autre part, imaginez une règle de hachage:
Ajoutez les codes de caractères ASCII de toutes les lettres de la marque et de la couleur, divisez par 100 et utilisez le reste comme valeur de hachage.
Cette règle convertira chaque élément en un nombre compris entre 0 et 99, ce qui consiste essentiellement à trier les données dans 100 compartiments. Chaque fois qu'un client doit localiser une voiture, vous pouvez modifier la marque et la couleur pour trouver le un seau sur 100 contenant les informations. Vous avez immédiatement réduit le nombre de recherches d'un facteur 100!
Adaptez maintenant l'exemple à d'énormes quantités de données, par exemple une base de données contenant des millions d'entrées qui est recherchée sur la base de dizaines de critères. Un "bien" La fonction de hachage distribuera les données dans des compartiments de manière à minimiser les recherches supplémentaires et à économiser un temps considérable.
Autres conseils
Tout d'abord, vous devez comprendre ce qu'est une fonction de hachage. 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 hash. Une fonction de hachage de 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 à l'adresse http://www.azillionmonkeys.com/qed/. hash.html
La carte de hachage utilise cette valeur de hachage pour la placer dans un tableau. Méthode java simpliste:
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;
}
}
array[hash].add(new Entry<String, Object>(key, val));
}
(Cette carte applique des clés uniques. Toutes les cartes ne le font pas.)
Il est possible que deux clés différentes soient hachées à la même valeur ou que deux hachages différents soient mappés au même index de tableau. Il existe de nombreuses techniques pour y remédier. Le plus simple consiste à utiliser une liste chaînée (ou une arborescence binaire) pour chaque index de tableau. Si la fonction de hachage est suffisante, vous n’aurez jamais besoin d’une recherche linéaire.
Maintenant, cherchez 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;
}
tables de hachage sont associatives . C'est une différence énorme par rapport aux tableaux, qui ne sont que des structures de données linéaires. Avec un tableau, vous pouvez faire quelque chose comme ceci:
int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
Notez comment vous obtenez un élément du tableau en spécifiant un décalage de mémoire exact ( i ). Cela contraste avec les hashtables, qui vous permettent de stocker des paires clé / valeur, récupérant ensuite la valeur en fonction de la clé:
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
Avec le tableau ci-dessus, nous pouvons effectuer l'appel suivant:
int n = table.get("Chris");
... et soyez assuré que n sera évalué à 18 .
Je pense que cela répondra probablement à la plupart de vos questions. L'implémentation d'une table de hachage est un sujet assez intéressant, un que Wikipedia adresse passablement bien .
"Je suis plus intéressé par la façon dont les tables de hachage recherchent la clé et sa génération."
-
Le hachage transforme un objet clé en un nombre. Ceci s'appelle "hachage". - il fait un hash de l'objet. Voir la Fonction de hachage . La somme des octets d'une chaîne, par exemple, est une technique de hachage standard. Vous calculez la somme modulo 2 32 pour conserver le hachage à une taille gérable. Hash donne toujours la même réponse. C’est O (1).
-
Le numéro vous donne un "emplacement". dans la table de hachage. Étant donné un objet clé arbitraire, la valeur de hachage calcule une valeur de hachage. La valeur de hachage vous donne alors l'emplacement dans la table. Généralement
mod (hachage, taille de la table). C’est également O (1).
C'est la solution générale. Deux calculs numériques et vous passez d'un objet arbitraire en tant que clé à un objet arbitraire en tant que valeur. Peu de choses peuvent être aussi rapides.
La transformation d'objet en valeur de hachage se produit de l'une des manières courantes.
-
S'il s'agit d'une "primitive" objet de 4 octets, la valeur native de l'objet est un nombre.
-
L'adresse de l'objet est de 4 octets. L'adresse de l'objet peut être utilisée comme valeur de hachage.
-
Un fonction de hachage simple (MD5, SHA1, peu importe) accumule les octets de l'objet pour créer un nombre de 4 octets. Les hachages avancés ne sont pas de simples sommes d'octets, une simple somme ne reflète pas assez tous les bits d'entrée originaux.
L'emplacement dans la table de hachage est mod (nombre, taille de la table).
Si cet emplacement a la valeur souhaitée, vous avez terminé. Si ce n'est pas la valeur souhaitée, vous devez chercher ailleurs. Il existe plusieurs algorithmes de sondage populaires pour rechercher une place libre dans le tableau. Linear est une simple recherche du prochain espace libre. Quadratic est un saut non linéaire recherchant un emplacement libre. Un générateur de nombres aléatoires (avec une graine fixe) peut être utilisé pour générer une série de sondes qui répartiront les données de manière uniforme mais arbitraire.
Les algorithmes de sondage ne sont pas O (1). Si la table est suffisamment grande, les chances de collision sont faibles et les sondes importent peu. Si la table est trop petite, il y a collision et interrogation. À ce stade, il devient une question de "réglage et de mise au point" pour équilibrer le sondage et la taille de la table pour optimiser les performances. Habituellement, nous agrandissons simplement la table.
Voir Table de hachage .
Quelque chose que je n'ai pas vu spécifiquement noté pour l'instant:
L’intérêt d’utiliser une table de hachage sur un tableau est la performance.
Une itération dans un tableau prend généralement entre 0 (1) et O (x), où x est le nombre d'éléments du tableau. Cependant, le temps nécessaire pour trouver votre élément sera extrêmement variable , surtout si nous parlons de centaines de milliers d’articles dans le tableau.
Une table de hachage correctement pondérée a généralement un temps d'accès presque constant légèrement supérieur à O (1), quel que soit le nombre d'éléments contenus dans la table de hachage.
Vous ne voudriez pas utiliser une table de hachage pour 100 nombres générés aléatoirement.
Une bonne façon de penser aux tables de hachage est de penser aux paires de valeurs. Utilisons les étudiants et disons que tout le monde a un numéro d'identification d'étudiant. Dans votre programme, vous stockez des informations sur les étudiants (noms, numéros de téléphone, factures, etc.). Vous souhaitez rechercher toutes les informations sur un élève en utilisant uniquement les informations de base (nom ou identifiant de l'étudiant, par exemple).
Disons que vous avez 10 000 étudiants. Si vous les stockez tous dans un tableau, vous devez parcourir l'ensemble du tableau en comparant l'ID d'étudiant de chaque entrée avec celui que vous recherchez.
Si, à la place, vous utilisez "hash" (voir ci-dessous) leur numéro d'identification d'étudiant à une position dans le tableau, alors il vous suffit de rechercher les numéros d'étudiant qui ont le même hachage. Beaucoup moins de travail pour trouver ce que vous vouliez.
Dans cet exemple, supposons que les identifiants d’étudiants ne soient que des nombres à 6 chiffres. Notre fonction de hachage pourrait n'utiliser que les 3 derniers chiffres du numéro en tant que "clé de hachage". Ainsi, 232145 est haché dans l’emplacement de tableau 145. Vous avez donc uniquement besoin d’un tableau de 999 éléments (chaque élément étant une liste d’étudiants).
Cela devrait être un bon début pour vous. Bien sûr, vous devriez lire un livre de texte ou wikipedia pour ce genre d’informations. Mais je suppose que vous avez déjà fait cela et que vous en avez marre de lire.
En bref, voici comment fonctionne une table de hachage.
Imaginez que vous avez une bibliothèque remplie de livres. Si vous stockiez les livres dans un tableau, vous placeriez chaque livre sur une étagère, puis, lorsque quelqu'un vous demanderait de trouver un livre, vous parcoureriez toutes les étagères - assez lentement. Si quelqu'un disait "livre # 12345", vous pourriez le trouver assez facilement, cependant.
Disons plutôt que si le titre du livre commence par «A», il se place dans la rangée 1. Si la deuxième lettre est «B», il se trouve dans la rangée 1, rack 2. Si la troisième lettre est «C» ', il va dans la rangée 1, le rack 2, la tablette 3 ... et ainsi de suite jusqu'à ce que vous identifiiez la position du livre. Ensuite, en fonction du titre du livre, vous pouvez savoir exactement où il devrait être.
Maintenant, il existe certains problèmes dans le simpliste "hachage". algorithme que j'ai décrit - certaines étagères vont être surchargées, d'autres vides, certains livres seront affectés au même emplacement. Les véritables fonctions de hachage sont donc soigneusement construites pour éviter de tels problèmes.
Mais c’est l’idée de base.
Je vais répondre à cette partie sur la différence entre une table de hachage et un tableau ... mais comme je n'ai jamais implémenté d'algorithme de hachage d'importation, je laisserai cela à quelqu'un de plus informé:)
Un tableau est juste une liste ordonnée d'objets. L'objet lui-même n'a pas d'importance. Ce qui est important, c'est que si vous voulez lister les objets dans l'ordre d'insertion, c'est toujours le même (ce qui signifie que le premier élément always a un index de 0).
En ce qui concerne une table de hachage, elle est indexée par clés, et non par ordre ... Je pense qu'une recherche de base sur les algorithmes de hachage vous donnera beaucoup plus d'informations que je ne le peux ... Wikipédia en a une très correcte ... détermine " seau " que les clés entrent dans pour une récupération rapide sur des objets arbitraires utilisés comme clés.
En ce qui concerne les avantages: Si l’ordre d’insertion est important, un tableau ou une sorte de liste ordonnée est nécessaire. Si la recherche rapide par clé arbitraire (associée à différentes fonctions de hachage) est importante, alors une table de hachage est logique.
[Ceci est la réponse à un commentaire fait par moi.yahoo.com/a ci-dessus]
Cela dépend de votre fonction de hachage. Supposons que votre fonction de hachage hache un mot selon la longueur de votre mot, la clé pour chris sera 5. De même, la clé pour yahoo sera également 5. Maintenant, les deux valeurs (chris et yahoo) seront inférieures à 5 (c'est-à-dire dans un "seau" clé par 5). De cette façon, vous n'avez pas à créer un tableau égal à la taille de vos données.
Je pense que la question a maintenant reçu une réponse claire et de nombreuses façons différentes.
Je voudrais juste ajouter une autre perspective (qui peut également dérouter un nouveau lecteur)
Au niveau de moindre abstraction, les tableaux ne sont que des blocs de mémoire contigus. Étant donné l'adresse de départ ( startAddress ), la taille ( sizeOfElement ) et le index d'un seul élément, l'adresse de l'élément est calculée comme suit:
elementAddress = startAddress + sizeOfElement * index
Il est intéressant de noter ici que les tableaux peuvent être abstraits / visualisés sous forme de tables de hachage avec index comme clé et la fonction ci-dessus comme fonction de hachage qui calcule l'emplacement d'une valeur dans O (1)
La table de hachage est une structure de données créée pour une recherche rapide.
Les tables de hachage ne sont pas efficaces lorsque le nombre d'entrées est très petit.
Quelques exemples:
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class HashtableDemo {
public static void main(String args[]) {
// Creating Hashtable for example
Hashtable companies = new Hashtable();
// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map
companies.put("Google", "United States");
companies.put("Nokia", "Finland");
companies.put("Sony", "Japan");
// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable
companies.get("Google");
// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable
System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));
// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value
System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));
// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values
Enumeration enumeration = companies.elements();
while (enumeration.hasMoreElements()) {
System.out.println("hashtable values: "+enumeration.nextElement());
}
// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java
System.out.println("Is companies hashtable empty: "+companies.isEmpty());
// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java
System.out.println("Size of hashtable in Java: " + companies.size());
// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java
Set hashtableKeys = companies.keySet();
// you can also get enumeration of all keys by using method keys()
Enumeration hashtableKeysEnum = companies.keys();
// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection
Enumeration hashtableValuesEnum = companies.elements();
Collection hashtableValues = companies.values();
// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.
companies.clear();
}
}
Sortie:
Does hashtable contains Google as key: true
Does hashtable contains Japan as value: true
hashtable values: Finland
hashtable values: United States
hashtable values: Japan
Is companies hashtable empty: false
Size of hashtable in Java: 3
