Classification des fonctions de hachage

9

Sur Internet, je suis tombé sur cette question:

Classez les fonctions de hachage en fonction des différentes méthodes par lesquelles la valeur de clé est trouvée.

avec des réponses comme

  • Méthode directe
  • Méthode de soustraction
  • Méthode Modulo-Division
  • Méthode d'extraction des chiffres
  • Méthode du carré moyen
  • Méthode de pliage
  • Méthode pseudo-aléatoire

que je trouve étrange. Je pense que j'en sais beaucoup sur le hachage, mais c'est du charabia pour moi, quelqu'un pourrait-il expliquer?

maaartinus
la source

Réponses:

4

Ce sont des méthodes pour transformer un code de hachage en un index du tableau qui contient les valeurs. Disons que vous avez un code de hachage de 0x12345678. Un très grand nombre et il est peu probable que vous ayez un tableau de cette taille. Si vous le faites, vous pouvez simplement le faire

Value = array[0x12345678];

Et se fait (méthode directe).

Si vous ne le faites pas, vous avez un moyen de transformer cette valeur en une valeur qui correspond à la taille du tableau tout en évitant trop de collisions. Les termes utilisés sont probablement également connus sous d'autres noms, mais par exemple, vous pouvez simplement masquer les bits supérieurs du code de hachage

Value = array[hashcode & 0xffff];

Ou modifiez le hashcode par rapport à la taille du tableau

Value = array[hashcode % array.size()]; // modulo division

Etc

Modifier: ce lien peut vous aider

James
la source
Merci, c'est tout - le lien semble être la source de cette ***. Cela n'a toujours aucun sens car ils mélangent beaucoup de choses ensemble: 1. calculer le hashCode à partir d'une clé (par exemple, plier et ajouter), 2. améliorer (= étaler) le hachage (par exemple, carré), 3. mapper le hachage de l'index (par exemple, module, "&").
maaartinus