Un guide de la technique de pliage en Java

1. Introduction

Dans ce didacticiel, nous examinons les techniques de hachage utilisées dans diverses structures de données qui fournissent un accès en temps constant à leurs éléments.

Nous discutons plus en détail de la technique dite de pliage et donnons une brève introduction aux techniques de mi-carré et de binning.

2. Aperçu

Lorsque nous choisissons des structures de données pour stocker des objets, l'une des considérations est de savoir si nous devons y accéder rapidement.

L'utilitaire Java nous offre un grand nombre de structures de données pour stocker nos objets. Pour plus d'informations sur les structures de données, reportez-vous à notre page de compilation Java Collections qui contient des guides sur plusieurs d'entre elles.

Comme nous le savons, certaines de ces structures de données nous permettent de récupérer leurs éléments en temps constant, indépendamment du nombre d'éléments qu'elles contiennent.

Probablement, le plus simple est le tableau. En fait, nous accédons aux éléments du tableau par leur index. Le temps d'accès, bien entendu, ne dépend pas de la taille du tableau. En fait, derrière la scène, de nombreuses structures de données utilisent fortement des tableaux.

Le problème est que les index des tableaux doivent être numériques, alors que nous préférons souvent manipuler ces structures de données avec des objets.

Afin de résoudre ce problème, de nombreuses structures de données tentent d'attribuer une valeur numérique qui peut servir d'index de tableau aux objets. Nous appelons cette valeur une valeur de hachage ou simplement un hachage .

3. Hashing

Le hachage est une transformation d'un objet en une valeur numérique . Les fonctions qui effectuent ces transformations sont appelées des fonctions de hachage .

Par souci de simplicité, considérons les fonctions de hachage qui transforment les chaînes en index de tableau, c'est-à-dire en nombres entiers de la plage [0, N] avec un N fini .

Naturellement, une fonction de hachage est appliquée à une grande variété de chaînes . Par conséquent, ses propriétés «globales» deviennent importantes.

Malheureusement, il n'est pas possible qu'une fonction de hachage transforme toujours différentes chaînes en différents nombres .

Nous pouvons nous convaincre assez facilement que le nombre de chaînes est beaucoup plus grand que le nombre d'entiers dans n'importe quelle plage [0, N] . Par conséquent, il est inévitable qu'il existe une paire de chaînes non égales pour lesquelles une fonction de hachage produit des valeurs égales. Ce phénomène est appelé collision .

Nous n'allons pas plonger dans les détails d'ingénierie derrière les fonctions de hachage, mais il est clair qu'une bonne fonction de hachage devrait essayer de mapper uniformément les chaînes sur lesquelles elle est définie en nombres.

Une autre exigence évidente est qu'une bonne fonction de hachage doit être rapide. Si le calcul d'une valeur de hachage prend trop de temps, nous ne pouvons pas accéder rapidement aux éléments.

Dans ce tutoriel, nous considérons l'une des techniques qui tentent de rendre le mappage uniforme tout en le maintenant rapide.

4. Technique de pliage

Notre objectif est de trouver une fonction qui transforme les chaînes en index de tableau. Juste pour illustrer l'idée, supposons que nous voulons que ce tableau ait la capacité de 105 éléments et utilisons le langage Java string comme exemple.

4.1. La description

Commençons par convertir les caractères de la chaîne en nombres. ASCII est un bon candidat pour cette opération:

Maintenant, nous organisons les nombres que nous venons d'obtenir en groupes d'une certaine taille. Généralement, nous choisissons la valeur de la taille du groupe en fonction de la taille de notre tableau qui est de 105. Puisque les nombres, dans lesquels nous avons transformé les caractères, contiennent de deux à trois chiffres, sans perte de généralité, nous pouvons définir la taille du groupe sur deux:

L'étape suivante consiste à concaténer les nombres dans chaque groupe comme s'il s'agissait de chaînes et à trouver leur somme:

Nous devons maintenant franchir la dernière étape. Vérifions si le nombre 348933 peut servir d'indice de notre tableau de taille 105. Naturellement, il dépasse la valeur maximale autorisée 99999. Nous pouvons facilement surmonter ce problème en appliquant l'opérateur modulo afin de trouver le résultat final:

348933 % 10000 = 48933

4.2. Remarques finales

Nous voyons que l'algorithme n'inclut aucune opération chronophage et qu'il est donc assez rapide. Chaque caractère de la chaîne d'entrée contribue au résultat final. Ce fait contribue certainement à réduire les collisions, mais pas à les éviter complètement.

Par exemple, si nous voulions ignorer le pliage et appliquer l'opérateur modulo directement à la chaîne d'entrée transformée en ASCII (en ignorant le problème de débordement)

749711897321089711010311797103101 % 100000 = 3101

alors une telle fonction de hachage produirait la même valeur pour toutes les chaînes qui ont les mêmes deux derniers caractères que notre chaîne d'entrée: a ge , p age , lar ge, et ainsi de suite.

A partir de la description de l'algorithme, nous pouvons facilement voir qu'il n'est pas exempt des collisions. Par exemple, l'algorithme produit la même valeur de hachage pour le langage Java et langue Vaja chaînes .

5. Autres techniques

La technique de pliage est assez courante, mais pas la seule. Parfois, les techniques de binning ou mid-square peuvent également être utiles.

Nous illustrons leur idée en n'utilisant pas de chaînes, mais des nombres (supposons que nous ayons déjà en quelque sorte transformé les chaînes en nombres). Nous ne discuterons pas de leurs avantages et de leurs faiblesses, mais vous pouvez vous faire une opinion après avoir vu les algorithmes.

5.1. Technique de binning

Supposons que nous ayons 100 nombres entiers et que nous souhaitons que notre fonction de hachage les mappe dans un tableau de 10 éléments. Ensuite, nous pouvons simplement organiser ces 100 entiers en dix groupes de manière à ce que les dix premiers entiers se retrouvent dans le premier bac, les dix seconds entiers se retrouvent dans le second bac, etc.:

5.2. Technique Mid-Square

Cet algorithme a été proposé par John von Neumann et il nous permet de générer des nombres pseudo-aléatoires à partir d'un nombre donné.

Illustrons-le sur un exemple concret. Supposons que nous ayons un numéro à quatre chiffres 1111 . Selon l'algorithme, nous l'avons carré, obtenant ainsi 1234321 . Maintenant, nous extrayons quatre chiffres du milieu, par exemple 2343 . L'algorithme nous permet de répéter ce processus jusqu'à ce que nous soyons satisfaits du résultat.

6. Conclusion

Dans ce didacticiel, nous avons examiné plusieurs techniques de hachage. Nous avons décrit en détail la technique de pliage et donné une description éclair de la façon dont le binning et le mid-square peuvent être obtenus.

Comme toujours, nous pouvons trouver les extraits de code correspondants sur notre référentiel GitHub.