Tables de hachage

Introduction

Nous allons comparer les temps d'accès aux éléments d'une liste et d'un dictionnaire

Voici un code Python pour observer la différence d'accès à des éléments dans un tableau et dans un ensemble, avec des tailles croissantes : 10 000, 100 000, 1 000 000 et 10 000 000.

Python

import time
import random

# Tailles des structures de données
taille_tableaux = [10_000, 100_000, 1_000_000, 10_000_000]

# Complétez le code ci-dessous
for taille in taille_tableaux:
    # Générer une liste et un ensemble contenant les mêmes éléments
    elements = list(range(taille))
    random.shuffle(elements)
    tableau = elements.copy()
    ensemble = set(elements)

    # Sélectionner un élément au hasard à rechercher
    element_recherche = random.choice(elements)

    # Mesurer le temps d'accès pour le tableau
    debut_tableau = time.time()
    est_present_tableau = element_recherche in tableau
    fin_tableau = time.time()

    # Mesurer le temps d'accès pour l'ensemble
    debut_ensemble = time.time()
    est_present_ensemble = element_recherche in ensemble
    fin_ensemble = time.time()

    # Afficher les résultats
    print(f"Taille : {taille}")
    print(f"  Temps d'accès tableau : {fin_tableau - debut_tableau:.10f} secondes")
    print(f"  Temps d'accès ensemble : {fin_ensemble - debut_ensemble:.10f} secondes")

Explications

1. Listes : Les listes (ou tableaux en Python) sont des structures ordonnées. Leur temps d'accès est linéaire en moyenne pour rechercher un élément.
2. Ensembles : Les ensembles utilisent des tables de hachage, ce qui permet un temps d'accès constant en moyenne.

En exécutant ce code, vous devriez observer que l'accès à un élément dans un ensemble est bien plus rapide que dans une liste, surtout lorsque la taille des données augmente.

Questions

1. Testez ce code avec d'autres tailles ou types de données si nécessaire.
2. Modifiez le code pour inclure plusieurs mesures et calculer une moyenne afin de réduire les variations dues au hasard.

Tables de hachage

Soient \( K \) et \( E \) deux ensembles, les éléments de \( K \) étant appelés clefs.

Une table d’association (ou dictionnaire) \( m \) de \( K \) vers \( E \) est une partie de \( K \times E \) telle que, pour toute clef \( k \in K \), il existe au plus un \( e \in E \) tel que le couple \( (k, e) \) soit dans \( m \).

Une implémentation simple d’une telle table d’association peut naturellement être effectuée à l’aide d’une liste d’association formée de couples de \( K \times E \).

Les tables de hachage (hash tables en anglais) sont une implémentation souvent plus efficace d’une telle structure de données. L’idée est la suivante :

• Pour chaque clef \( k \), on calcule un entier de hachage \( h_w(k) \) compris entre \( 0 \) et \( w - 1 \) (où \( w \) est appelé la largeur de la table).
• On utilise ensuite un tableau de \( w \) listes pour stocker les enregistrements : la liste numéro \( i \) contenant les couples \( (k, e) \) de la table d’association tels que \( h_w(k) = i \).

Hachage : Cas particuliers

Entiers naturels

Pour le cas où les clefs sont des entiers, le hachage par division de largeur \( w \) consiste à hacher la clef entière \( k \) en calculant le reste de la division de \( k \) par \( w \), soit :

\( h(k) = k \mod w \)

Cette valeur appartient bien à l’intervalle \( \{0, \dots, w - 1\} \).

Chaînes de caractères

Dans le cas où les clefs sont des chaînes de caractères, on peut se ramener au cas des entiers en utilisant le code ASCII des caractères.

Le code ASCII d’un caractère est un entier compris entre \( 0 \) et \( 255 \), identifiant le caractère de manière unique.

Une chaîne \( s = s_0 \dots s_{n-1} \) peut alors être vue comme la représentation en base \( 256 \) de l’entier :

\( \sum_{k=0}^{n-1} \text{code}(s_k) \times 256^k \)

où \( \text{code}(s_k) \) représente le code ASCII du caractère \( s_k \).

Sommes de contrôle

Une somme de contrôle (checksum en anglais) est une courte séquence de données numériques calculée à partir d'un bloc de données plus important (par exemple un fichier ou un message) permettant de vérifier, avec une très haute probabilité, que l'intégrité de ce bloc a été préservée lors d'une opération de copie, stockage ou transmission.

Exemple : Checksum sur 1 octet de de 'Hello'

Lettre	H	e	l	l	o
ASCII	72	101	108	108	111
Hexa	48	65	6C	6C	6F

Or (48 + 65 + 6C + 6C + 6F ) mod 256 = F4

F4 est donc la somme de contrôle sur un octet de 'Hello'.

Questions

1. Calculer la somme de contrôle sur un octet de 'Bonjour'

2. Ecrire une fonction Python qui calcule la somme de contrôle sur 1 octet d'une chaîne de caractère en ASCII ?