Qu'est-seau “entrées” dans le contexte d'une table de hachage?

Un seau est tout simplement un accès simple et rapide de l'emplacement (comme un tableau d'index) qui est le résultat de la fonction de hachage.

L'idée avec le hachage est à son tour un complexe de la valeur d'entrée en une valeur différente qui peut être utilisé pour rapidement extraire ou de stocker des données.

Envisager la suite de fonction de hachage pour le mappage des noms de personnes dans la rue des adresses.

D'abord prendre de l'écrit en minuscule initiales du prénom et du nom, et de les transformer à la fois en valeurs numériques (de 0 à 25, à partir de 'a' à 'z'). Multiplier la première par 26 et ajouter le second, et cela vous donne une valeur de 0 à 675 (26 * 26 valeurs distinctes, ou un seau Id).

Ce seau ID est ensuite utilisé pour stocker ou récupérer les informations. Maintenant vous pouvez avoir une parfaite hachage (où chaque déductibles de la valeur d'entrée des cartes pour un distinctes seau ID) ainsi qu'un tableau simple suffira pour les seaux. En d'autres termes, vous maintenir un réseau de 676 rue des adresses et utiliser le seau ID pour trouver celui que vous voulez:

+-------------------+
| George Washington | -> hash(GW)
+-------------------+      |
                           +-> GwBucket[George's address]
+-------------------+
|  Abraham Lincoln  | -> hash(AL)
+-------------------+      |
                           +-> AlBucket[Abe's address]

Ou vous pouvez avoir un imparfaite de hachage (comme celui où John Smith et Jane Seymour allait se retrouver avec le même seau ID).

Dans ce cas, vous avez besoin de plus en plus complexes, la sauvegarde de la structure de données qu'un simple tableau, afin de maintenir un collection d'adresses. Cela pourrait être aussi simple que d'une liste liée, ou aussi complexe qu'encore un autre hash:

+------------+       +--------------+
| John Smith |       | Jane Seymour |
+------------+       +--------------+
      |                     |
      V                     V
   hash(JS)              hash(JS)
      |                     |
      +-----> JsBucket <----+
                 \/
+-----------------------------------+
| "John Smith   -> [John's address] |
| "Jane Seymour -> [Jane's address] |
+-----------------------------------+

Alors, ainsi que le hachage initial de recherche, un niveau supplémentaire de la recherche doit être effectuée dans le seau lui-même, à trouver l'information spécifique.

OriginalL'auteur paxdiablo

Je pense que Seau est une structure d'au moins contenir la valeur de hachage, ce qui fonctionne comme les index, (les valeurs de hachage sont générés par les fonctions de hachage), mais la structure elle-même peut contenir des entrées (données) ou non.

illustration:

[valeur de hachage][points de données réelles] ---> [données réelles]

|<------------seau structure------>|

[valeur de hachage][données réelles]

|-----seau structure--->|

C'est la [valeur de hachage] une partie des œuvres que l'index.

---

J'ai trouvé ces photos de hash_table Wikipédia sont assez simple.

Les photos ci-dessous indique que les entrées (données) peuvent être stockées dans des seaux ou il peut être stocké avec sa propre structure de données, tandis que le seau tout simplement des points de données.

OriginalL'auteur Rick