Table de hachage [Spécialité NSI - Année 2026

Table de hachage

Définition : Fonction de hachage

Une fonction de hachage est une fonction qui prend une entrée (ou « clé ») et retourne un nombre fixe de caractères, appelé hash.

Les fonctions de hachage sont conçues de manière à ce que chaque clé unique produise un hash unique, bien que dans la pratique, deux clés différentes peuvent produire le même hash, ce qu’on appelle une collision de hachage.

Dans le cas des dictionnaires, la fonction de hachage doit renvoyer un nombre entier positif.

Les dictionnaires utilisent un tableau (appelé table de hachage) de taille finie pour stocker les paires clé-valeur. La clé est hachée à l’aide d’une fonction de hachage, et le résultat est utilisé comme index pour stocker la valeur correspondante dans la table. Si le hash est plus grand que la taille du tableau, on calcule son modulo à la taille du tableau pour se ramener à une valeur bornée.

Lorsqu’on cherche une valeur dans le dictionnaire, on utilise la fonction de hachage pour hacher la clé et trouver l’index de la valeur.

Méthode : Exemple de fonctions

def simple_hash(s):
    """Cette fonction prend une chaîne de caractères et retourne un nombre qui représente cette chaîne."""
    return sum(ord(char) for char in s)

def simple_hash(s):
    """Cette fonction prend une chaîne de caractères et retourne un nombre qui représente cette chaîne."""
    return sum(ord(char) for char in s)

Dans cette fonction, ord(char) retourne la valeur ASCII du caractère, et sum() additionne ces valeurs pour tous les caractères de la chaîne.

C’est une fonction de hachage très basique qui n’est pas idéale pour une utilisation réelle car elle peut facilement conduire à des collisions (deux anagrammes produisent le même hash). Cependant, elle sert à illustrer le concept.

def djb2(s):
    """Cette fonction prend une chaîne de caractères et retourne un nombre qui représente cette chaîne."""
    hash = 5381
    for x in s.encode():
        hash = ((hash << 5) + hash) + x
    return hash & 0xFFFFFFFF_FFFFFFFF  # Retourne un hash de 64 bits

def djb2(s):
    """Cette fonction prend une chaîne de caractères et retourne un nombre qui représente cette chaîne."""
    hash = 5381
    for x in s.encode():
        hash = ((hash << 5) + hash) + x
    return hash & 0xFFFFFFFF_FFFFFFFF  # Retourne un hash de 64 bits

Cette fonction est une implémentation simple de l’algorithme de hachage DJB2, qui est un algorithme de hachage couramment utilisé pour les chaînes de caractères.

Dans cette fonction, nous commençons par un nombre initial (5381), puis pour chaque caractère dans la chaîne, nous décalons le hash actuel de 5 bits vers la gauche (ce qui est équivalent à le multiplier par 32), ajoutons le hash actuel, puis ajoutons la valeur ASCII du caractère. Le résultat est un nombre qui est relativement unique pour chaque chaîne de caractères unique.

Comme toutes les fonctions de hachage, il est possible que deux chaînes différentes produisent le même hash (une collision). Cependant, l’algorithme DJB2 est conçu de manière à minimiser la probabilité de telles collisions.

Exemple : Exemple (très) simple

On souhaite ajouter les couples suivants en utilisant la fonction de hachage len() dans un tableau de taille 5 :

("NSI", "Frayssinet")
("Histoire & Geographie", "Joliveau")
("Anglais","Paccard")
("Sport", "Froment")

Questions :

Représenter le dictionnaire contenant ces clés/valeurs
Que se passe-t-il si on souhaite ajouter ("Mathématiques", "Hamoumou") ?
Que se passe-t-il si on souhaite rechercher la valeur ayant pour clé "SNT" ?