Fonctions de hachage et leur utilisation

10.1 Introduction aux fonctions de hachage et aux tables de hachage

Rappelons-nous et approfondissons notre compréhension des fonctions de hachage et des tables. Une fonction de hachage est un algorithme qui convertit des données d'entrée de longueur arbitraire en une chaîne de longueur fixe. Les propriétés principales des fonctions de hachage :

• Déterminisme : les mêmes entrées donnent toujours le même résultat.
• Calcul rapide : le hachage doit être calculé assez rapidement.
• Irréversibilité (pour les fonctions de hachage cryptographiques) : il est impossible (ou extrêmement difficile) de retrouver les données d'origine à partir du hachage.
• Distribution uniforme : des changements mineurs dans les données d’entrée conduisent à des changements significatifs dans le hachage.

Pour simplifier, cette fonction pour des objets identiques est forcément la même, mais si la fonction de hachage de deux objets est identique, ces objets ne sont pas nécessairement égaux. En mathématiques, cela s'appelle une condition nécessaire mais non suffisante.

Une table de hachage est une structure de données qui utilise une fonction de hachage pour stocker et rechercher efficacement des informations. Elle est composée de :

• Un tableau de "paniers" pour stocker les données.
• Une fonction de hachage qui détermine dans quel panier placer les données.

Les tables de hachage assurent un accès rapide aux données, généralement avec une complexité de O(1) en moyenne.

Utilisation des fonctions de hachage dans la vie réelle

Exemple : Technologies Blockchain

Dans la blockchain, les fonctions de hachage sont utilisées pour créer des identifiants uniques pour les blocs et garantir l'intégrité des données. Chaque bloc contient le hachage du bloc précédent, ce qui crée une chaîne et rend le système résistant aux modifications.

import hashlib
import time

class Block:
    def __init__(self, data, previous_hash):
        self.timestamp = time.time()
        self.data = data
        self.previous_hash = previous_hash
        self.hash = self.calculate_hash()

    def calculate_hash(self):
        hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
        return hashlib.sha256(hash_string.encode()).hexdigest()

# Exemple d'utilisation
block1 = Block("Transaction 1", "0")
block2 = Block("Transaction 2", block1.hash)
print(f"Hash du bloc 1: {block1.hash}")
print(f"Hash du bloc 2: {block2.hash}")

Comparaison de performance

Considérons le problème de recherche de doublons dans un tableau. Comparons la solution avec et sans utilisation de table de hachage :

import time

def find_duplicates_with_hash(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

def find_duplicates_without_hash(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# Test de performance
arr = list(range(10000)) + list(range(5000))  # Tableau avec doublons

start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Temps d'exécution avec table de hachage : {end - start} secondes")

start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Temps d'exécution sans table de hachage : {end - start} secondes")

Lancez le programme et voyez à quel point l'utilisation de la table de hachage accélère la recherche de doublons. Surtout sur des tableaux de grande taille.

10.2 Exemples d'application de fonctions de hachage à des tâches réelles

1. Hachage des mots de passe

Les fonctions de hachage sont utilisées pour le stockage sécurisé des mots de passe. Au lieu de stocker les mots de passe en clair, les systèmes stockent leurs hachages. Lors de la saisie d'un mot de passe par l'utilisateur, le système hache le mot de passe saisi et le compare avec le hachage stocké dans la base de données.

Exemple d'implémentation :

import hashlib

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

# Exemple d'utilisation:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash du mot de passe: {hashed_password}")

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. Par exemple, pour vérifier qu'un fichier n'a pas été modifié ou corrompu lors de la transmission.

Exemple d'implémentation :

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()

# Exemple d'utilisation:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash du fichier: {file_hash}")

3. Moteurs de recherche et indexation

Les moteurs de recherche utilisent les fonctions de hachage pour créer des index et rechercher rapidement des informations. Chaque document est indexé par des mots-clés, et les fonctions de hachage aident à trouver rapidement les documents contenant les mots donnés.

Exemple d'implémentation :

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

# Exemple d'utilisation:
text = "This is an example text for indexing"
index = create_index(text)
print(f"Index: {index}")

10.3 Optimisation de la recherche avec des fonctions de hachage

1. Utilisation de tables de hachage pour rechercher des doublons

Les tables de hachage permettent de trouver rapidement des doublons dans un tableau en comparant les valeurs de hachage des éléments.

Exemple d'implémentation :

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Exemple d'utilisation:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Sortie: [2, 4]

2. Optimisation de la recherche de paires avec une somme donnée

Les tables de hachage permettent de trouver efficacement des paires de nombres dans un tableau dont la somme est égale à une valeur donnée.

Exemple d'implémentation :

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Exemple d'utilisation:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Sortie: [(4, 2), (3, 3), (8, -2)]

10.4 Exemples d'utilisation des fonctions de hachage dans divers algorithmes

1. Comptage des mots dans un texte

Utilisez une table de hachage pour compter le nombre d'occurrences de chaque mot dans un texte.

Exemple d'implémentation :

def count_words(text):
    word_count = {}
    words = text.split()

    for word in words:
        if word in word_count:
            word_count[word] += 1
        else:
            word_count[word] = 1

    return word_count

# Exemple d'utilisation:
text = "this is a test this is only a test"
print(count_words(text))  # Sortie: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}

2. Vérification de l'intersection de deux tableaux

Vérifiez si deux tableaux s'intersectent (s'ils ont au moins un élément en commun).

Exemple d'implémentation :

def has_intersection(arr1, arr2):
    set1 = set(arr1)
    for item in arr2:
        if item in set1:
            return True
    return False

# Exemple d'utilisation:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2))  # Sortie: True
print(has_intersection(arr1, arr3))  # Sortie: False

3. Vérification de l'unicité des éléments dans un tableau

Vérifiez si un tableau contient uniquement des éléments uniques.

Exemple d'implémentation :

def all_unique(arr):
    seen = set()
    for item in arr:
        if item in seen:
            return False
        seen.add(item)
    return True

# Exemple d'utilisation:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1))  # Sortie: True
print(all_unique(arr2))  # Sortie: False