Les fondamentaux des tables de hachage?

Je suis assez confus au sujet des concepts de base d’une table de hachage. Si je devais coder un hash, comment pourrais-je même commencer? Quelle est la différence entre une table de hachage et juste un tableau normal?

Fondamentalement, si quelqu’un répondait à cette question, je pense que toutes mes questions seraient répondues: si j’avais 100 numéros générés au hasard (sous forme de 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 …

Les réponses apscopes jusqu’ici 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 les comprendre.

Quelle est la différence entre une table de hachage et juste un tableau normal?

Une table de hachage et un tableau sont tous deux des structures qui vous permettent de stocker et de récupérer des données. Les deux permettent de spécifier un index et de récupérer une valeur associée. La différence, comme l’a noté Daniel Spiewak, est que les indices d’un tableau sont séquentiels , tandis 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 être un moyen très efficace de rechercher des éléments dans de grandes quantités de données, en particulier des données qui ne sont pas facilement consultables. (“Large” signifie ici ginormous , dans le sens où il faudrait beaucoup de temps pour effectuer une recherche séquentielle).

Si je devais coder un hash, comment pourrais-je même commencer?

Aucun problème. Le moyen le plus simple consiste à inventer une opération mathématique arbitraire que vous pouvez effectuer sur les données, qui renvoie un nombre N (généralement un entier). Ensuite, utilisez ce numéro comme index dans un tableau de “buckets” et stockez vos données dans le compartiment # N L’astuce consiste à sélectionner une opération qui tend à placer des valeurs dans des compartiments différents, de manière à ce que vous puissiez les retrouver plus tard.

Exemple: Un grand centre commercial conserve une firebase database sur les voitures et les parkings de ses clients, pour aider les clients à se rappeler où ils se sont garés. La firebase database stocke la make , la color , la license plate et l’ parking location . En sortant du magasin, un client trouve sa voiture en saisissant sa marque et sa couleur. La firebase database renvoie une liste (relativement courte) de plaques d’immasortingculation et de places de stationnement. Une parsing rapide localise la voiture du client.

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 ont été stockées dans un tableau, qui est essentiellement une liste, vous pouvez imaginer l’implémentation de la requête en analysant un tableau pour toutes les entrées correspondantes.

En revanche, 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 rest comme valeur de hachage.

Cette règle convertira chaque élément en un nombre compris entre 0 et 99, en sortingant essentiellement les données dans 100 compartiments. Chaque fois qu’un client a besoin de localiser une voiture, vous pouvez hacher la marque et la couleur pour trouver le seau sur 100 qui contient les informations. Vous avez immédiatement réduit la recherche d’un facteur 100!

Maintenant, montez en puissance sur des quantités énormes de données, par exemple une firebase database avec des millions d’entrées qui sont recherchées en fonction de dizaines de critères. Une “bonne” fonction de hachage dissortingbuera les données dans des compartiments d’une manière qui minimise toute recherche supplémentaire, économisant ainsi beaucoup de temps.

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 renvoyer le même hachage. Une fonction de hachage de chaîne très simple en Java pourrait ressembler à

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

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

La carte de hachage utilise maintenant cette valeur de hachage pour placer la valeur dans un tableau. Méthode Java simpliste:

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

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

Il est possible de hacher deux clés différentes avec la même valeur, ou deux hachages différents pour mapper le même index de tableau. Il existe de nombreuses techniques pour y faire face. Le plus simple est d’utiliser une liste chaînée (ou un arbre binary) 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(Ssortingng key) { int hash = ssortingngHash(key) % array.length; if(array[hash] != null) { for(Entry e : array[hash]) { if(e.key.equals(key)) return e.value; } } return null; } 

Les tables de hachage sont associatives . Ceci est une énorme différence avec les 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); } 

Remarquez comment vous obtenez un élément en dehors 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, puis de récupérer la valeur en fonction de la clé:

 Hashtable table = new Hashtable(); table.put("Daniel", 20); table.put("Chris", 18); table.put("Joseph", 16); 

Avec le tableau ci-dessus, nous pouvons faire 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, auquel Wikipedia s'adresse passablement .

“Je suis plus intéressé par la façon dont les tables de hachage recherchent la clé et comment la clé est générée.”

  1. Le hachage transforme un object clé en un nombre. C’est ce qu’on appelle le “hachage” – il crée un hachage de l’object. Voir Fonction de hachage . La sum des octets d’une chaîne, par exemple, est une technique de hachage standard. Vous calculez la sum modulo 2 32 pour garder le hachage à une taille gérable. Hash donne toujours la même réponse. Ceci est O (1).

  2. Le numéro vous donne un “slot” dans le HashTable. Étant donné un object clé arbitraire, la valeur de hachage calcule une valeur de hachage. La valeur de hachage vous donne alors la fente dans la table. Généralement mod( hash, table size ) . Ceci est O (1), aussi.

C’est la solution générale. Deux calculs numériques et vous êtes passé d’un object arbitraire comme clé à un object arbitraire comme valeur. Peu de choses peuvent être aussi rapides.

La transformation de l’object en valeur de hachage se produit de l’une des manières suivantes.

  1. S’il s’agit d’un object “primitif” de 4 octets, la valeur native de l’object est un nombre.

  2. L’adresse de l’object est de 4 octets, l’adresse de l’object peut alors être utilisée comme valeur de hachage.

  3. Une simple fonction de hachage (MD5, SHA1, peu importe) accumule les octets de l’object pour créer un nombre à 4 octets. Les hachages avancés ne sont pas des sums simples d’octets, une simple sum ne reflète pas assez tous les bits d’entrée d’origine.

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 un emplacement libre dans le tableau. Linear est une simple recherche du prochain spot gratuit. Quadratic est un saut non linéaire qui cherche 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 diffuseront les données de manière uniforme mais arbitraire.

Les algorithmes de sondage ne sont pas O (1). Si la table est assez grande, les probabilités de collision sont faibles et les sondes ne comptent pas. Si la table est trop petite, des collisions se produisent et des sondages se produisent. À ce stade, il devient “syntonisé et ajusté” pour équilibrer le sondage et la taille de la table pour optimiser les performances. Habituellement, nous ne faisons que grossir la table.

Voir la table de hachage .

Quelque chose que je n’ai pas vu spécifiquement noté encore:

L’utilisation d’une table de hachage sur un tableau a pour but la performance.

Itérer via un tableau prend généralement entre O (1) et O (x), x étant le nombre d’éléments du tableau. Cependant, le temps de trouver votre article sera extrêmement variable , surtout si vous parlez de centaines de milliers d’éléments dans le tableau.

Une table de hachage correctement pondérée a généralement un temps d’access presque constant juste au-dessus de O (1), quel que soit le nombre d’éléments 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 à des 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 numéro d’é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, au lieu de cela, vous “hachez” (voir ci-dessous) leur numéro d’étudiant à un emplacement du tableau, alors vous devez uniquement rechercher les numéros d’élève qui ont le même hash. Beaucoup moins de travail pour trouver ce que vous vouliez.

Dans cet exemple, supposons que les identifiants d’étudiants ne sont que des numéros à 6 chiffres. Notre fonction de hachage pourrait utiliser uniquement les 3 derniers chiffres du nombre comme “clé de hachage”. Ainsi, 232145 est haché à l’emplacement du tableau 145. Vous n’avez donc besoin que d’un tableau de 999 éléments (chaque élément étant une liste d’étudiants).

Cela devrait être un bon début pour vous. Vous devriez bien sûr lire un manuel ou un wikipedia pour ce type d’information. Mais je suppose que vous l’avez déjà fait et que vous en avez assez de lire.

Voici comment fonctionne une table de hachage.

Imaginez que vous ayez une bibliothèque remplie de livres. Si vous stockiez les livres dans un tableau, vous metsortingez chaque livre sur une étagère, puis, quand quelqu’un vous demande de trouver un livre, vous regardez à travers toutes les étagères – assez lentement. Si quelqu’un disait “book # 12345”, vous pourriez le trouver assez facilement.

Disons que vous dites plutôt que si le titre du livre commence par «A», il se trouve dans la rangée 1. Si la deuxième lettre est «B», elle se trouve dans la rangée 1, rack 2. Si la troisième lettre est «C», va dans la rangée 1, rack 2, tablette 3 … et ainsi de suite jusqu’à ce que vous identifiez la position du livre. Ensuite, en fonction du titre du livre, vous pouvez savoir exactement où il doit se trouver.

Maintenant, il y a quelques problèmes dans l’algorithme simpliste de hachage que j’ai décrit – certaines étagères vont être surchargées tandis que d’autres restnt vides, certains livres seront assignés au même emplacement. essayez d’éviter de tels problèmes.

Mais c’est l’idée de base.

Je vais répondre à cette question à propos de la différence entre une table de hachage et un tableau … mais comme je n’ai jamais implémenté d’algorithme de hachage avant l’importation, je laisserai cela à quelqu’un de plus compétent 🙂

Un tableau est juste une liste ordonnée d’objects. L’object lui-même n’a pas vraiment d’importance … ce qui est important, c’est que si vous voulez lister les objects par ordre d’insertion, c’est toujours le même (ce qui signifie que le premier élément a toujours un index de 0).

En ce qui concerne une table de hachage, indexée par des clés, pas d’ordre … Je pense qu’une recherche de base sur les algorithmes de hachage vous donnera beaucoup plus de perspicacité que moi … Wikipedia a une très bonne définition … “que les clés vont pour une récupération rapide sur des objects 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 (indexée par diverses fonctions de hachage) est importante, alors une table de hachage a du sens.

[Ceci est la réponse à un commentaire fait par me.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.-à-d. dans un «seau» indexé par 5). De cette façon, vous n’avez pas à créer un tableau égal à la taille de vos données.

La question, je crois, est résolue de manière très claire et à bien des égards.

Je voudrais juste append un autre sharepoint vue (ce qui peut aussi perturber un nouveau lecteur)

À un 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 l’ index d’un seul élément, l’adresse de l’élément est calculée comme suit:

 elementAddress = startAddress + sizeOfElement * index 

La chose intéressante à noter ici est que les tableaux peuvent être abstraits / visualisés en tant que tables de hachage avec index tant que clé et la fonction ci-dessus en tant que 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.

référence

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(Ssortingng 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 resortingeve 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