Comment travaille-t-il dans la programmation? Comment je pense qu'un hash est quelque chose qui me permet de pouvoir utiliser une valeur unique pour récupérer certaines données. Comme si nous avons un tableau et que je commence à mettre des choses dans le tableau, si j'ai une autre variable qui garde la trace de quel article est dans la fente 0,1,2 ... Puis j'ai cette capacité instantanée à trouver un élément. Est ce hachage?
Quel est le but d'un hash?
Quand faut-il mettre en œuvre un hachage? Qu'est-ce qu'un hasch similaire à en termes de structure de données?
Ce que je pense savoir sur les hachages, c'est que cela nous permet de récupérer l'article dans O (1). Est-ce correct?
3 Réponses :
Un hachage est comme le prénom d'une personne - c'est une mauvaise façon de se souvenir d'une personne, même si cela n'a pas besoin d'être unique. Si vous avez besoin de trouver des informations sur quelqu'un, vous pouvez simplement les regarder par leur nom, et vous n'avez besoin que d'autres contrôles si deux personnes ou plus ont le même nom.
C'est le pouvoir de hachage, et tout comme le souvenir des gens est beaucoup plus facile par nom que par numéro de sécurité sociale, la recherche d'un objet par son code de hachage est beaucoup plus facile que de comparer réellement l'objet à tout déjà dans votre collection.
Maintenant, dans cet exemple, si vous cherchez une personne dans un répertoire par nom, vous les trouveriez probablement dans O (journal N), car les noms sont triés par ordre alphabétique et parce que vous devez faire une recherche binaire. Si, toutefois, vous avez plutôt "haché" 100 personnes nées dans les années 1900 par leurs années de naissance, alors vous auriez seulement besoin d'au plus 4 comparaisons de la hacttable / répertoire (un par chiffre) pour trouver un an par hash, qui est temps constant. Ensuite, si deux personnes naissent la même année, vous pouvez utiliser d'autres informations pour trouver la personne dont vous avez besoin et en moyenne, si votre table n'est pas trop complète (par exemple, si vous avez au plus 50 personnes pendant 100 années différentes de naissance), vos recherches seront constantes.
(Si votre table devient plus que, disons, 50% complète, vous pouvez toujours doubler sa taille, afin de conserver le nombre de collisions à basse et donc de garder vos recherches rapidement.)
Plus d'informations:
Si vous avez déjà entendu parler de MD5 ou SHA-1 SHA-2 HASHES Pour les fichiers, ils sont comme les "empreintes digitales" du fichier. Bien qu'il soit possible d'avoir deux fichiers avec le même hachage, cela est fait si peu probable que, à des fins pratiques, c'est impossible; Par conséquent, si vous avez le hachage de deux fichiers, vous pouvez comparer les fichiers par leurs empreintes digitales plutôt que par leurs données, ce qui est extrêmement plus rapide.
Une carte de hachage / dictionnaire est une structure de données de clé / valeur qui stocke des objets dans des godets en fonction de la valeur d'une fonction de hachage. Ces clés doivent être uniques mais les valeurs de la fonction de hachage (parfois appelées hashcodes) ne sont pas nécessairement uniques.
Comme si nous avons un tableau et que je commence à mettre des crêtes dans la matrice, si j'ai une autre variable qui garde la trace de quel article est dans la fente 0,1,2 ... Puis j'ai cette capacité instantanée à trouver un Objet. Est ce hachage?
non. Une fonction de hachage est une fonction déterministe qui donne toujours la même valeur pour un objet. Le code de hachage ne change pas en fonction de l'endroit où l'objet est stocké.
Ce que je pense savoir sur les hachages, c'est que cela nous permet de récupérer l'article dans O (1). Est-ce correct?
presque. Un dictionnaire a O (1) complexité pour les recherches si il n'y a pas trop de collisions de code de hachage. Toutefois, si la fonction de hachage est médiocre et que chaque objet a la même valeur de hachage, un dictionnaire pourrait plutôt avoir une performance O (n).
Notez également que les clés ne doivent pas nécessairement être des cordes ou des caractères. Principalement, ils sont, mais ils peuvent aussi être des pointeurs (en plus le fait qu'une chaîne est un pointeur), des structures ou d'autres types de données.
A hachage le rend vite à la recherche au lieu de itération sur un tableau ou un arbre. Il permet une recherche utile o (1) fois avec peu d'utilisation de la mémoire.
Prenez soin de vous: Il y a des algorithmes de hachage et il existe des hashtables, qui sont des structures de données utilisant un algorithme de hachage (spécifiquement, d'une manière d'implémenter une carte de carte / associative). Vous voulez dire ce dernier, mais dire «hachage» qui fait généralement référence à un algorithme de hachage ou à la sortie d'un algorithme de hachage.