algorithm
Fonctions de hachage

Introduction aux fonctions de hachage

La fonction de hachage h() est une fonction arbitraire qui mappe les données x ∈ X de taille arbitraire à la valeur y ∈ Y de taille fixe: y = h(x) . Les bonnes fonctions de hachage suivent les restrictions suivantes:

• fonctions de hachage se comportent comme une distribution uniforme

• les fonctions de hachage sont déterministes. h(x) devrait toujours retourner la même valeur pour un x donné

• calcul rapide (a l'exécution O (1))

En général, la taille de la fonction de hachage est inférieure à la taille des données d'entrée: |y| < |x| . Les fonctions de hachage ne sont pas réversibles ou, en d'autres termes, elles peuvent être une collision: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X peut être un ensemble fini ou infini et Y un ensemble fini.

Les fonctions de hachage sont utilisées dans de nombreuses parties de l'informatique, par exemple dans le génie logiciel, la cryptographie, les bases de données, les réseaux, l'apprentissage automatique, etc. Il existe différents types de fonctions de hachage, avec des propriétés spécifiques au domaine différentes.

Le hachage est souvent une valeur entière. Il existe des méthodes spéciales de programmation des langages pour le calcul du hachage. Par exemple, dans C# GetHashCode() méthode pour tous les types renvoie la valeur Int32 (nombre entier 32 bits). En Java chaque classe fournit la hashCode() qui renvoie int . Chaque type de données possède des implémentations propres ou définies par l'utilisateur.

Méthodes de hachage

Il existe plusieurs approches pour déterminer la fonction de hachage. Sans perte de généralité, admettons que x ∈ X = {z ∈ ℤ: z ≥ 0} sont des nombres entiers positifs. Souvent, m est premier (pas trop près d'une puissance exacte de 2).

Table de hachage

Fonctions de hachage utilisées dans les tables de hachage pour calculer l'index dans un tableau de logements. La table de hachage est une structure de données pour l'implémentation de dictionnaires (structure clé-valeur). Les bonnes tables de hachage implémentées ont l'heure O (1) pour les opérations suivantes: insérer, rechercher et supprimer des données par clé. Plus d'une clé peut se connecter au même emplacement. Il existe deux manières de résoudre une collision:

1. Chaînage: la liste chaînée est utilisée pour stocker des éléments avec la même valeur de hachage dans l'emplacement.

2. Adressage ouvert: zéro ou un élément est stocké dans chaque emplacement

Les méthodes suivantes sont utilisées pour calculer les séquences de sonde requises pour l'adressage ouvert

Où i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) sont des fonctions de hachage auxiliaires, c1, c2 sont des constantes auxiliaires positives.

Exemples

Laisse x ∈ U{1, 1000}, h = x mod m . Le tableau suivant montre les valeurs de hachage en cas de non premier et premier. Le texte en gras indique les mêmes valeurs de hachage.

Liens

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction aux algorithmes.

• Vue d'ensemble des tables de hachage

• Wolfram MathWorld - Fonction de hachage

Codes de hachage pour les types courants en C #

Les codes de hachage produits par la méthode GetHashCode() pour les types C # intégrés et communs à partir de l'espace de noms System sont présentés ci-dessous.

Booléen

1 si la valeur est vraie, 0 sinon.

Byte , UInt16 , Int32 , UInt32 , Single

Valeur (si nécessaire converti en Int32).

SByte

((int)m_value ^ (int)m_value << 8);

Carboniser

(int)m_value ^ ((int)m_value << 16);

Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

Int64 , double

Xor entre les 32 bits inférieur et supérieur du numéro 64 bits

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

UInt64 , DateTime , TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

Décimal

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Objet

RuntimeHelpers.GetHashCode(this);

L'implémentation par défaut est utilisée pour l' index du bloc de synchronisation .

Chaîne

Le calcul du code de hachage dépend du type de plate-forme (Win32 ou Win64), caractéristique de l'utilisation du hachage de chaîne aléatoire, du mode Debug / Release. En cas de plateforme Win64:

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
    hash1 = ((hash1 << 5) + hash1) ^ c;
    c = s[1];
    if (c == 0)
        break;
    hash2 = ((hash2 << 5) + hash2) ^ c;
    s += 2;
}
return hash1 + (hash2 * 1566083941);

Type de valeur

Le premier champ non statique est chercher et obtenir son code de hachage. Si le type n'a pas de champs non statiques, le code de hachage du type renvoie. Le code de hachage d'un membre statique ne peut pas être pris, car si ce membre est du même type que le type d'origine, le calcul se termine dans une boucle infinie.

Nullable <T>

return hasValue ? value.GetHashCode() : 0;

Tableau

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++) 
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

Les références

• GitHub .Net Core CLR