J'essaie juste de comprendre quand vous auriez besoin d'utiliser un hachage et quand il pourrait être préférable d'utiliser un tableau. Quel genre d'objet du monde réel un hachage représenterait, disons, dans le cas des chaînes?Qu'est-ce qu'un exemple réel de quelque chose que vous représenteriez avec un hachage?
je crois parfois un hachage est appelée un « dictionnaire », et je pense que c'est un bon exemple en lui-même. Si vous voulez rechercher la définition d'un mot, il est agréable de faire quelque chose comme:
definition['pernicious']
Au lieu d'essayer de comprendre l'indice numérique exact que la définition serait conservé à.
Cette réponse suppose que par « hachage », vous êtes essentiellement référence juste un tableau associatif.
Lorsque vous devez associer une variable à une autre. Il n'y a pas de "limite de type" à ce qui peut être une clé/valeur dans un hachage.
Je pense que vous regardez les choses dans la mauvaise direction. Ce n'est pas l'objet qui détermine si vous devez utiliser un hachage mais la façon dont vous y accédez. Une utilisation courante d'un hachage est lors de l'utilisation d'une table de recherche. Si vos objets sont des chaînes et que vous voulez vérifier si elles existent dans un Dictionary, les chercher (en supposant que le hachage fonctionne correctement) par O (1). Avec le tri, le temps serait plutôt O (logn), ce qui peut ne pas être acceptable.
Ainsi, hash sont idéales pour une utilisation avec des dictionnaires (hashmaps), fixe (hashsets), etc.
Ils sont également un moyen utile de représenter un objet sans stocker l'objet lui-même (pour les mots de passe).
Chaque fois que vous avez des données qui est bien desservie par une carte 1 à 1.
Par exemple, les notes dans une classe:
"John Smith" => "B +"
"Jacob Jenkens" => "C"
etc
L'annuaire téléphonique - clé = nom, valeur = numéro de téléphone.
Je pense aussi du vieux monde (Livre Encyclopédies books réels). Chaque article est "haché" dans un seul livre (chat va dans le volume "C").
Les hachettes ont de nombreuses utilisations. Mis à part les utilisations cryptographiques, ils sont couramment utilisés pour des recherches rapides d'informations. Pour obtenir des recherches similaires à l'aide d'un tableau, vous devez garder le tableau trié et ensuite utiliser une recherche binaire. Avec un hachage, vous obtenez la recherche rapide sans avoir à trier. C'est la raison pour laquelle la plupart des langages de script implémentent le hachage sous un nom ou un autre (dictionnaires, etc.).
En général hash sont utilisés pour trouver des choses rapidement - une carte de hachage peut être utilisé pour assosiate une chose avec une autre rapide, un ensemble de hachage seulement stocker des choses « rapide ».Veuillez également tenir compte de la complexité et du coût de la fonction de hachage pour déterminer s'il est préférable d'utiliser un conteneur de hachage ou un conteneur inférieur normal - la taille supplémentaire de la valeur de hachage et le temps nécessaire pour calculer un hachage "parfait". le temps nécessaire pour faire une comparaison 1: 1 à la fin dans le cas d'un conflit de fonction de hachage peut en fait être beaucoup plus élevé que de passer par une structure arborescente avec une complexité logarithmique en utilisant les opérateurs moins alors.
J'utilise un souvent pour un « dictionnaire » des paramètres de mon application.
Réglage | Valeur
je les charger à partir du fichier de base de données ou config, dans Hashtable pour mon application.
Fonctionne bien, et est simple.
Un exemple pourrait être le code postal associé à une région, une ville ou une adresse postale.
Un bon exemple est un cache avec beaucoup de d'éléments en elle. Vous avez un identificateur par lequel vous voulez rechercher la valeur a (par exemple, une URL, et vous voulez trouver la page Web correspondante mise en cache). Vous souhaitez que ces recherches soient aussi rapides que possible et que vous ne souhaitiez pas effectuer de recherche dans toutes les pages stockées chaque fois qu'une URL est demandée. Une table de hachage est une excellente structure de données pour un problème comme celui-ci.
Un exemple du monde réel que je viens d'écrire est quand j'ajoutais le peuple montant dépensé pour les repas lors du dépôt des rapports de dépenses.
Je devais obtenir un total quotidien sans aucune idée du nombre d'articles qui existeraient un jour donné et je n'avais aucune idée de la fourchette de dates pour le rapport de dépenses. Il existe des restrictions sur combien une personne peut en charges avec de nombreuses variables (quelle ville, week-end, etc ...)
La table de hachage est l'outil parfait pour gérer cela. La clé était la date à laquelle la valeur était le montant du reçu (converti en USD). Les reçus peuvent entrer dans n'importe quel ordre, je continue à obtenir la valeur pour cette date et à y ajouter jusqu'à ce que le travail soit terminé. L'affichage était facile aussi.
(code php)
$david = new stdclass();
$david->name = "david";
$david->age = 12;
$david->id = 1;
$david->title = "manager";
$joe = new stdclass();
$joe->name = "joe";
$joe->age = 17;
$joe->id = 2;
$joe->title = "employee";
// option 1: lets put users by index
$users[] = $david;
$users[] = $joe;
// option 2: lets put users by title
$users[$david->title] = $david;
$users[$joe->title] = $joe;
maintenant la question: qui est le gestionnaire? répondre:
$users["manager"]
C'est ce que j'allais dire! Tu m'as battu dessus –
Vraiment, le but du hash est de faire regarder l'objet plus vite. Si cet objet hashé est associé à un autre objet, c'est génial (et probablement la situation la plus courante). Mais ce n'est pas nécessaire: Considérez hash_set en C++ (http://www.sgi.com/tech/stl/hash_set.html) – Brian
Je ne pense pas que ce soit un vrai exemple du monde réel. Un humain regardant à travers un dictionnaire utilisera une recherche d'interpolation. Les dictionnaires physiques n'ont pas un moyen O (1) de trouver un mot. –