Tableau hash

Précédent ◈ Suivant

Points saillants du laboratoire:

Exercice en laboratoire:


Cliquez sur le petit ordinateur ci-dessus pour une description détaillée.
Pour cette excercise vous demandera de mettre en place un système de vérification de mot de passe pour authentifier un mot de passe de l'utilisateur.

1. Définition d'une table de hachage

Avant d'entrer dans la définition des tables de hachage, il est bon d'introduire pourquoi utiliser des tables de hachage.

Les tables de hachage sont bons pour faire une recherche rapide sur les choses.

Par exemple, si nous avons une gamme complète de données (par exemple 100 articles). Si nous savions que la position d'un élément spécifique est stocké dans un tableau, alors nous pourrions accéder rapidement. Par exemple, il nous arrive juste savoir que l'article que nous voulons est en position 3; Je peux appliquer:
MyItem = myarray [3];

Avec cela, nous ne devons pas chercher à travers chaque élément du tableau, nous accès juste position 3.

La question est, comment pouvons-nous savoir que la position 3 stocke les données qui nous intéresse?

C'est là hash est très pratique. Étant donné une clé, nous pouvons appliquer une fonction de hachage pour trouver un indice ou la position que nous voulons accéder.

1.1 Quelle est la fonction de hachage?

Il y a beaucoup de différentes fonctions de hachage. Certaines fonctions de hachage prendront une clé entière et la transformer en un index. Une commune est la méthode de division.

Apprenons par un exemple:

1.2 Méthode de division (une méthode de hachage pour les entiers)

Disons que vous avez eu les numéros suivants ou les clés que vous vouliez carte dans un tableau de 10 éléments:

123456
123467
123450

Pour appliquer le procédé de division, on pourrait diviser le nombre de 10 (ou le nombre maximum d'éléments dans le tableau) et en utilisant le reste (modulo) comme un index. Ce qui suit résulterait:

123456 10% = 6 (le reste est 6 lors de la division par 10)
123467 10% = 7 (le reste est de 7)
123450 10% = 0 (le reste est égal à 0)

Ces chiffres devraient être insérés dans la matrice en des positions 6, 7 et 0, respectivement. Il pourrait ressembler à ceci:

La chose importante avec la méthode de division est que les clés sont des nombres entiers.

1.3 Qu'est-ce qui se passe quand les touches ne sont pas des entiers?

Vous devez appliquer une autre fonction de hachage pour les transformer en entiers. En effet, vous obtenez deux fonctions de hachage dans un:
  1. fonction pour obtenir un nombre entier
  2. fonction d'appliquer une méthode de hachage ci-dessus pour obtenir de l'indice à un tableau

Que veut-on dire que les clés ne sont pas des entiers? Eh bien, disons que les clés sont les noms des personnes. Tel que:

Sarah Jones
Tony Balognie
Tom Katz

L'objectif est de taper dans un de ces noms et obtenir un indice à un tableau afin d'accéder à cette information. Comment faisons-nous cela?
La fonction de hachage doit faire deux choses:
  1. Convertir les noms en nombres entiers
      Par exemple, nous avons une fonction qui transforme une chaîne en un entier. Les résultats seront les suivants:
      Sarah Jones -> 1038
      Tony Balognie -> 1259
      Tom Katz -> 746
  2. Appliquer une méthode de hachage pour obtenir un indice
      Nous pouvons maintenant appliquer la méthode de division pour obtenir un index pour un tableau de 10 éléments
      Sarah Jones -> 1038% 10 -> 8
      Tony Balognie -> 1259% 10 -> 9
      Tom Katz -> 746% 10 -> 6

1.4 Que cela ressemblerait dans le tableau?

Le tableau est connu comme une table de hachage. Il stocke la clé (utilisée pour trouver l'indice) ainsi que les valeurs associées. Dans l'exemple ci-dessus, nous pourrions avoir une table de hachage qui avait l'air quelque chose comme ceci:

Encore une fois, l'idée est que nous allons insérer des éléments dans la table de hachage à l'aide de la clé et l'application de la fonction de hachage (s) pour obtenir l'indice.

Un problème se produit lorsque deux touches donnent le même indice. Par exemple, supposons que nous voulions inclure:
John Smith -> 948% 10 -> 8

Nous avons une collision parce que Sarah Jones est déjà stocké à l'index du tableau 8.

Nous avons besoin d'une méthode pour résoudre ce problème. La résolution est dans la façon dont vous créez votre table de hachage. Il deux grandes approches données dans le livre:
  1. linéaire Sonder
  2. chaînage
L'approche utilisée dans ce laboratoire est appelé chaînage.

Les détails sont laissés en tant que matériau de classe, mais reconnaître que vous avez enchaînant une série de listes chaînées. Toutes les données de la « même lien », ont entrer en collision des valeurs d'index.

Considérons un schéma de l'exemple ci-dessus. Rappelez-vous, il y a eu une collision avec Sarah Jones et John Smith. Notez que John Smith est « enchaînée » ou « liée » après Sarah Jones.

1.5 Applications d'une table de hachage

Les tables de hachage sont bonnes dans les situations où vous avez d'énormes quantités de données à partir desquelles vous souhaitez rechercher rapidement et récupérer des informations. Quelques implémentations typiques de la table de hachage serait dans les situations suivantes:
  • Pour son dossier de permis de conduire. Avec une table de hachage, vous pouvez obtenir rapidement des informations sur le pilote (ie. Nom, adresse, âge) étant donné le numéro de licence.

  • Pour les tables de symboles du compilateur. Le compilateur utilise une table de symboles pour garder la trace des symboles définis par l'utilisateur dans un programme C ++. Cela permet au compilateur de rechercher rapidement les attributs associés à des symboles (par exemple, les noms de variables)

  • Pour les moteurs de recherche sur Internet. Pour plus d'informations, cliquez ici

  • Pour les bases de données de l'annuaire téléphonique. Vous pouvez utiliser une table de hachage implementatation pour rechercher rapidement le numéro de téléphone de John Smith.

  • Pour les catalogues de bibliothèques électroniques. les mises en œuvre de la table de hachage permettent une recherche rapide parmi les millions de documents stockés dans la bibliothèque.

  • Pour la mise en œuvre des mots de passe pour les systèmes avec plusieurs utilisateurs. Les tables de hachage permettent une récupération rapide du mot de passe qui correspond à un nom d'utilisateur donné.

    • 1.6 opérations typiques d'une table de hachage

    Les fonctions associées à notre mise en œuvre de la table de hachage sont les suivantes:
  • bool isEmpty ()
    Renvoie true si la table de hachage est vide. Dans le cas contraire, retourne false

  • bool isFull ()
    Renvoie true si la table de hachage est pleine. Dans le cas contraire, retourne false

  • void insert (const DT newDataItem)
    Les inserts newDataItem dans la liste appropriée dans la table de hachage. L'emplacement (index) dans la table de hachage est déterminée par la touche et la fonction de hachage.

  • supprimer bool (KF searchkey)
    Recherche dans la table de hachage pour l'élément de données avec la clé searchkey. Si l'élément de données se trouve, puis supprime l'élément de données et renvoie true. Dans le cas contraire, retourne false.

  • bool récupérer (KF searchkey, DT DataItem)
    Recherche dans la table de hachage pour l'élément de données avec la clé searchkey. Si l'élément de données se trouve, puis copie le poste de données à DataItem et renvoie true. Dans le cas contraire, retourne false.

  • void clear ()
    Supprime tous les éléments de données dans la table de hachage.

  • showStructure vide ()
    Sorties les éléments de données dans une table de hachage. Si la table de hachage est vide, sorties, « vide table de hachage ». Ceci est destiné à des fins d'essais / de débogage.

    2. Application: Recherche des mots de passe

    La section suivante présente un algorithme d'authentification du mot de passe d'un utilisateur. Plus tard, dans l'exercice de laboratoire, vous recevrez le code squelette et demandé d'ajouter des lignes pour le faire fonctionner.

    Une utilisation possible pour une table de hachage est de stocker les noms d'utilisateur de connexion de l'utilisateur de l'ordinateur et les mots de passe.

    Il y a deux étapes importantes à ce programme:
    1. Le programme se charge des ensembles nom d'utilisateur / mot de passe du fichier password.dat et les insérer dans la table de hachage jusqu'à la fin du fichier est atteinte sur password.dat. Le fichier password.dat ressemblera à quelque chose comme ça avec un nom d'utilisateur / mot de passe défini par ligne:
  • Le programme présentera ensuite une invite de connexion, un nom d'utilisateur de lire, présente une invite de mot de passe, et après avoir recherché le mot de passe le nom d'utilisateur dans la table de hachage, imprimera soit « authentification réussie » ou « échec d'authentification ». La sortie pourrait ressembler à ceci:
    • Étape 2 est répété jusqu'à ce que la fin des données d'entrée (EOF) soit atteinte sur le flux d'entrée de la console (CIN). Le caractère EOF sur le PC est le caractère CTRL Z.

    Remplissons dans certains détails:

    3. Exercice Lab

    • Obtenez les fichiers:
    • Extrait tous les fichiers au WORKAREA. Ouvrez le WORKAREA et double-cliquez sur exercise.sln. Cela permettra d'ouvrir le projet. Il y a six fichiers utilisés dans ce programme:
      • hashtbl.cpp et hashtble.h - contiennent la mise en œuvre de la classe Hashtable
      • listlnk.cpp et listlnk.h - contiennent la mise en œuvre de la classe de listes chaînées
      • login.cpp - le programme principal. Celui-ci contient la structure de mot de passe, qui est inséré dans la table de hachage.
      • password.dat - contient tous les utilisateurs et les mots de passe correspondants.
    Les étapes comprennent:
  • Essayez d'exécuter ce programme. Vous devriez trouver qu'il vous demandera « Connexion » et « Mot de passe: » (tapez des mots au hasard à ces invites). Vous remarquerez qu'il vous demande cycles continuely autour de cette information.
    Pour arrêter le programme de course, à la « Login: » invite, tapez CTRL et z (en même temps), puis sur la touche Entrée.

  • Ajouter une ligne pour insérer des mots de passe dans la table. Astuce: notez que le nom de la table de hachage des mots de passe est et que vous souhaitez insérer une structure de mot de passe appelé tempPass dans la table de hachage.

  • Ajouter une ligne pour imprimer la table de hachage. Astuce: la table de hachage des mots de passe est et il y a une fonction membre appelée showStructure.

  • Ajouter des lignes à comparer le vrai mot de passe pour le mot de passe d'entrée et impression « Échec d'authentification » ou « authentification réussie ». Remarque: comparer le mot de passe d'entrée (pass) pour le mot de passe à l'intérieur de l'objet tempPass (qui a été récupéré).

  • Construire et exécuter votre programme. Vous devriez obtenir des résultats comme les suivants:
  • Vous pouvez maintenant vouloir jouer avec un certain nombre de choses et de voir ce qui se passe:
    • Modifiez la ligne suivante de sorte que vous avez 8 éléments dans votre table de hachage (au lieu de 10): Qu'est-ce qui arrive à la table de hachage? Pourquoi?
    • Modifiez le fichier password.dat. Ce fichier a été ajouté au projet (sous la rubrique « Fichiers de ressources » dans l'Explorateur de solutions). Double-cliquez dessus pour l'ouvrir.

    Plan d'essai pour le programme de simulation « Connexion »

    Articles Liés

    • Précédent ◈ Suivant