Notion de fonction de hachage

5.1 Définition de la fonction de hachage et son utilisation

La fonction de hachage est une fonction qui prend des données d'entrée (ou une clé) et renvoie une taille de bits fixe, généralement appelée hachage ou valeur de hachage. L'objectif principal d'une fonction de hachage est de distribuer efficacement les données dans une table de hachage pour garantir un accès rapide aux éléments.

Utilisation :

• Tables de hachage : Utilisées pour implémenter des tableaux associatifs (dictionnaires en Python), assurant un accès rapide aux données par clé.
• Contrôle de l'intégrité des données : Les fonctions de hachage sont utilisées pour vérifier l'intégrité des fichiers et des données (par exemple, les algorithmes MD5, SHA-1, SHA-256).
• Cryptographie : Les fonctions de hachage sont utilisées dans les algorithmes cryptographiques pour le chiffrement et la création de signatures numériques.
• Moteurs de recherche : Utilisées pour l'indexation des données et la recherche rapide d'informations.
• Gestion du cache : Utilisées pour organiser les caches afin de retrouver rapidement les données.

Exemple d'utilisation d'une fonction de hachage en Python :

# Exemple d'utilisation d'une fonction de hachage en Python pour une table de hachage (dictionnaire)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Obtenir la valeur de hachage de la clé
key = "banana"
hash_value = hash(key)

print(f"Valeur de hachage pour la clé '{key}': {hash_value}")

5.2 Analogies de la vie réelle

Avec une fonction de hachage, vous pouvez diviser un grand groupe d'objets en groupes à peu près égaux. De plus, si vous continuez à ajouter de nouveaux objets, ils continueront à se répartir uniformément entre les groupes.

Supposons que vous ayez 1000 personnes et que vous deviez les répartir en 30 groupes. Voici comment cela peut être fait.

Méthode 1. Par la première lettre du nom.

Le premier groupe comprend tous ceux dont le nom commence par un "A", le deuxième groupe comprend tous ceux dont le nom commence par un "B", et ainsi de suite. La règle "Votre groupe est la première lettre de votre nom" est une fonction de hachage. Mais avec une telle fonction de hachage, nous risquons d'avoir beaucoup de personnes dans le groupe "A" et peu dans "Z".

Méthode 2. Par date de naissance.

Né le premier de n'importe quel mois — premier groupe, le deuxième — deuxième groupe, etc. Il y aura 31 groupes. Dans le 31e groupe, il y aura environ deux fois moins de monde que dans les autres, mais les gens dans ces groupes sont beaucoup plus uniformément répartis que dans le premier cas.

Méthode 3. Numéro de téléphone

La solution idéale est d'obtenir un nombre qui soit, d'une part, aussi aléatoire que possible (pour que ces nombres soient uniformément répartis), et d'autre part, qu'il soit toujours rapidement calculé et identique.

Prenons les 4 derniers chiffres du numéro de téléphone — ce qui donnera 10 000 options. Ensuite, on divise ce nombre par 30. Ainsi, nous aurons 30 restes possibles : 0, 1, 2, ..., 29. Ce seront les numéros de nos groupes.

Utile ! D'ailleurs, presque toutes les fonctions de hachage utilisent le reste de la division entière — c'est très simple et permet de réguler le nombre de groupes dans lesquels répartir les éléments.

5.3 Principales propriétés d'une fonction de hachage

Principales propriétés d'une bonne fonction de hachage :

Déterminisme : La même fonction de hachage doit toujours renvoyer la même valeur de hachage pour une entrée identique.

Exemple :

key = "example"
assert hash(key) == hash(key)

Attention ! L'opérateur assert vérifie que ce qui se trouve à sa droite est une expression True. Si l'expression n'est pas False, une exception sera lancée.

Uniformité : Une bonne fonction de hachage doit distribuer les valeurs uniformément sur toute la gamme des valeurs de hachage possibles pour éviter les collisions.

Exemple de la vie d'un développeur Python : Dans un dictionnaire (classe dict) Python, la fonction de hachage hash() distribue les clés de manière uniforme.

Efficacité du calcul : Une fonction de hachage doit être rapide et efficace pour ne pas ralentir les opérations d'insertion et de recherche.

Exemple de la vie d'un développeur Python : Les fonctions de hachage standard en Python sont implémentées pour fonctionner avec des clés de différents types, comme les chaînes et les nombres.

Minimisation des collisions : Une collision se produit lorsque deux clés différentes ont la même valeur de hachage. Une bonne fonction de hachage doit minimiser la probabilité de collisions.

Exemple de la vie d'un développeur Python : L'algorithme SHA-256 minimise la probabilité de collisions lors du hachage des données.

Distribution des hachages : Pour de grands volumes de données, une fonction de hachage doit assurer une distribution uniforme des valeurs de hachage sur toute la table de hachage.

Exemple de la vie d'un développeur Python : Les fonctions de hachage standard en Python gèrent bien la distribution des clés dans les tables de hachage.

5.4 Exemples de fonctions de hachage et leur implémentation

Les fonctions de hachage prennent en entrée des données de taille arbitraire et renvoient une valeur de hachage de taille fixe. Examinons quelques exemples de fonctions de hachage et leur implémentation.

Exemple 1 : Fonction de hachage simple pour les chaînes

L'une des fonctions de hachage les plus simples pour les chaînes peut être implémentée en utilisant la somme des codes des caractères de la chaîne :

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Supposons que notre table ait une taille de 1000

# Exemple d'utilisation :
key = "example"
print(f"Valeur de hachage pour la clé '{key}': {simple_hash(key)}")

Exemple 2 : Fonction de hachage pour les chaînes utilisant le hachage polynomial

Le hachage polynomial est une technique plus complexe, mais efficace :

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Exemple d'utilisation :
key = "example"
print(f"Valeur de hachage pour la clé '{key}': {polynomial_hash(key)}")

Exemple 3 : Fonction de hachage intégrée en Python

Python fournit une fonction intégrée hash() pour obtenir la valeur de hachage de différents types de données :

key = "example"
print(f"Valeur de hachage pour la clé '{key}': {hash(key)}")

Exemple 4 : Fonction de hachage cryptographique (SHA-256)

Les fonctions de hachage cryptographiques, telles que SHA-256, sont utilisées pour assurer la sécurité des données :

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Exemple d'utilisation :
key = "example"
print(f"Valeur de hachage pour la clé '{key}': {sha256_hash(key)}")

5.5 Introduction au hachage et son application

Le hachage est le processus de transformation de données d'entrée de taille arbitraire en une valeur de hachage de taille fixe en utilisant une fonction de hachage. Le hachage est largement utilisé en sciences informatiques et en programmation pour l'optimisation et la sécurité.

Principales applications du hachage :

1. Tables de hachage (dictionnaires) : Les tables de hachage utilisent des fonctions de hachage pour organiser et accéder rapidement aux données.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Valeur de hachage pour la clé '{key}': {hash_value}")

2. Contrôle de l'intégrité des données : Les fonctions de hachage sont utilisées pour vérifier l'intégrité des fichiers et des données.

Exemple : Vérification de l'intégrité d'un fichier à l'aide de SHA-256 :

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

file_hash = get_file_hash('example.txt')
print(f"Hachage SHA-256 du fichier : {file_hash}")

3. Cryptographie et sécurité : Les fonctions de hachage sont utilisées pour créer des primitives cryptographiques telles que les signatures numériques et les hachages de mots de passe.

Exemple : Hachage de mot de passe à l'aide de SHA-256 :

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

password = "securepassword"
hashed_password = hash_password(password)
print(f"Hachage du mot de passe : {hashed_password}")

4. Moteurs de recherche et indexation : Le hachage est utilisé pour créer des index et rechercher rapidement des données.

Exemple : Création d'un index pour la recherche de texte :

def create_index(text):
    index = {}
    for word in text.split():
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

text = "This is an example text for indexing"
index = create_index(text)
print(f"Indice : {index}")

5. Gestion du cache : Le hachage est utilisé pour organiser les caches afin de retrouver rapidement les données.

Exemple : Cache simple utilisant une fonction de hachage :

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Ajouter et récupérer des données du cache
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Affiche : test_value