13. Les tables de hachages

13.1. Rappels sur les dictionnaires (implémentation de référence de Python)

13.1.1. Création et ajout des valeurs

En Python les tables de hachage sont les dict (dictionnaires)

La création d’un dictionnaire peut se faire de la façon suivante.

d = dict()
d

{}

Pour compléter le dictionnaire, il suffit d’ajouter une clef (ici 'a') et sa valeur ('aa')

d['a'] = 'aa'
d

{'a': 'aa'}

Un dictionnaire peut /a priori/ contenir tout type de données.

d = {'robert':'bob'}
d["liste"] = [1,2,3]
d['1'] = 1
d['samuel'] = None
d[1] = 3
d

{'robert': 'bob', 'liste': [1, 2, 3], '1': 1, 'samuel': None, 1: 3}

Une autre façon d’initialiser un dictionnaire :

d = dict([("clef","valeur"),('clé','valeur')])

En particulier, un dictionnaire peut contenir un dictionnaire.

d['a'] = dict()
d['a']['ab'] = ['absent', 'absurde', 'absoudre']

13.1.2. Méthodes sur les dictionnaires

Écrire un dictionnaire avec les mots chat (cat), chien (dog), vache (cow), tigre (tiger) et licorne (unicorn) et leurs traduction en anglais

Show code cell content Hide code cell content

animaux = {'chat':'cat','chien':'dog','vache':'cow','tigre':'tiger','licorne':'unicorn'}

Si on veut rajouter un animal, il faut vérifier que celui-ci n’existe pas, avec le mot clef in :

'chat' in animaux.keys()

True

'souris' in animaux.keys()

False

Show code cell source Hide code cell source

def ajoute(mot_français, mot_anglais, dictionnaire):
    if mot_français not in dictionnaire.keys():
        dictionnaire[mot_français] = mot_anglais

ajoute('souris','mouse',animaux)

animaux

{'chat': 'cat',
 'chien': 'dog',
 'vache': 'cow',
 'tigre': 'tiger',
 'licorne': 'unicorn',
 'souris': 'mouse'}

On peut récupérer les clefs, les valeurs ou les deux.

animaux.keys()

dict_keys(['chat', 'chien', 'vache', 'tigre', 'licorne', 'souris'])

animaux.values()

dict_values(['cat', 'dog', 'cow', 'tiger', 'unicorn', 'mouse'])

animaux.items()

dict_items([('chat', 'cat'), ('chien', 'dog'), ('vache', 'cow'), ('tigre', 'tiger'), ('licorne', 'unicorn'), ('souris', 'mouse')])

13.2. Fonctionnement d’un dictionnaire

13.2.1. Principe de base

Pour obtenir un dictionnaire (une table de hachage), on a essentiellement besoin d’un tableau[1], ainsi que d’une méthode permettant de transformer la clef en un identifiant numérique.

La taille du tableau servant au stockage des clefs et des valeurs, celle-ci est déterminée au départ, essentiellement en fonction de la taille.

Example 13.1 (dictionnaire avec au plus 10 entrées)

On suppose, dans cet exemple, que les clefs sont des valeurs numériques, par exemple, des indicatifs téléphoniques par pays :

{
    33: 'France',
    32: 'Belgique',
}

from cours.structures import Tableau

class Dictionnaire:
    n = 10
    def __init__(self):
        self.tableau = Tableau(self.n)
        for i in range(self.n):
            self.tableau[i] = 0
    def inserer(self, clef, valeur):
        self.tableau[clef % self.n] = (clef, valeur)
    def obtenir(self, clef):
        sortie = self.tableau[clef % self.n]
        if sortie == 0:
            raise KeyError(f"{clef}")
        else:
            return sortie
    def __repr__(self):
        sortie = "{"
        for i in range(self.n):
            if self.tableau[i] != 0:
                sortie = sortie + f"{self.tableau[i][0]}: {self.tableau[i][1]}"
            if i != n - 1:
                sortie = sortie + ", "
        sortie = sortie + "}"
        return sortie

On peut donc utiliser cette implémentation de dictionnaire.

dictionnaire = Dictionnaire()
dictionnaire.inserer(32, 'Belgique')
dictionnaire

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/formatters.py:711, in PlainTextFormatter.__call__(self, obj)
    704 stream = StringIO()
    705 printer = pretty.RepresentationPrinter(stream, self.verbose,
    706     self.max_width, self.newline,
    707     max_seq_length=self.max_seq_length,
    708     singleton_pprinters=self.singleton_printers,
    709     type_pprinters=self.type_printers,
    710     deferred_pprinters=self.deferred_printers)
--> 711 printer.pretty(obj)
    712 printer.flush()
    713 return stream.getvalue()

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/lib/pretty.py:419, in RepresentationPrinter.pretty(self, obj)
    408                         return meth(obj, self, cycle)
    409                 if (
    410                     cls is not object
    411                     # check if cls defines __repr__
   (...)
    417                     and callable(_safe_getattr(cls, "__repr__", None))
    418                 ):
--> 419                     return _repr_pprint(obj, self, cycle)
    421     return _default_pprint(obj, self, cycle)
    422 finally:

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/lib/pretty.py:787, in _repr_pprint(obj, p, cycle)
    785 """A pprint that just redirects to the normal repr function."""
    786 # Find newlines and replace them with p.break_()
--> 787 output = repr(obj)
    788 lines = output.splitlines()
    789 with p.group():

Cell In[16], line 22, in Dictionnaire.__repr__(self)
     20     if self.tableau[i] != 0:
     21         sortie = sortie + f"{self.tableau[i][0]}: {self.tableau[i][1]}"
---> 22     if i != n - 1:
     23         sortie = sortie + ", "
     24 sortie = sortie + "}"

NameError: name 'n' is not defined

On peut obtenir une clef particulière

dictionnaire.obtenir(32)

(32, 'Belgique')

et obtenir une erreur sur les clefs n’existant pas

dictionnaire.obtenir(33)

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[19], line 1
----> 1 dictionnaire.obtenir(33)

Cell In[16], line 14, in Dictionnaire.obtenir(self, clef)
     12 sortie = self.tableau[clef % self.n]
     13 if sortie == 0:
---> 14     raise KeyError(f"{clef}")
     15 else:
     16     return sortie

KeyError: '33'

Exercise 13.1

Compléter la classe Dictionnaire avec une méthode valeurs qui renvoie la totalité des couples clefs valeurs.

Ici, la fonction clef % n où \(n\) est la taille du tableau s’appelle une fonction de hachage (hash function en anglais).

Definition 13.1 (Fonction de hachage)

Une fonction de hachage est une fonction de \(K\), un espace fini de clef à images dans \(\[0, m\]\), un espace de nombres entiers (alvéoles). Une telle fonction doit posséder quelques propriétés :

• elle doit être rapide à calculer \(\mathcal{O}(1)\).

• elle doit être déterministe (toujours renvoyer le même résultat)

• elle doit «bien répartir» les images (alvéoles)

Si on ajoute une clef 42: 'Allemagne', que se passe-t-il ?

Show code cell content Hide code cell content

dictionnaire.inserer(42, 'Allemagne')
dictionnaire

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/formatters.py:711, in PlainTextFormatter.__call__(self, obj)
    704 stream = StringIO()
    705 printer = pretty.RepresentationPrinter(stream, self.verbose,
    706     self.max_width, self.newline,
    707     max_seq_length=self.max_seq_length,
    708     singleton_pprinters=self.singleton_printers,
    709     type_pprinters=self.type_printers,
    710     deferred_pprinters=self.deferred_printers)
--> 711 printer.pretty(obj)
    712 printer.flush()
    713 return stream.getvalue()

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/lib/pretty.py:419, in RepresentationPrinter.pretty(self, obj)
    408                         return meth(obj, self, cycle)
    409                 if (
    410                     cls is not object
    411                     # check if cls defines __repr__
   (...)
    417                     and callable(_safe_getattr(cls, "__repr__", None))
    418                 ):
--> 419                     return _repr_pprint(obj, self, cycle)
    421     return _default_pprint(obj, self, cycle)
    422 finally:

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/lib/pretty.py:787, in _repr_pprint(obj, p, cycle)
    785 """A pprint that just redirects to the normal repr function."""
    786 # Find newlines and replace them with p.break_()
--> 787 output = repr(obj)
    788 lines = output.splitlines()
    789 with p.group():

Cell In[16], line 22, in Dictionnaire.__repr__(self)
     20     if self.tableau[i] != 0:
     21         sortie = sortie + f"{self.tableau[i][0]}: {self.tableau[i][1]}"
---> 22     if i != n - 1:
     23         sortie = sortie + ", "
     24 sortie = sortie + "}"

NameError: name 'n' is not defined

13.2.2. Problème des collisions

Le phénomène précédent s’appelle collision de clef et est inévitable. Pour s’en convaincre, le cardinal (taille de l’ensemble) des clefs étant très grand devant le cardinal des alvéoles, il est évident que les fonctions de hachages ne peuvent pas être injectives[2], et donc avoir deux antécédents distincts qui fournissent la même image. On peut éventuellement raffiner la fonction de hachage[3] pour limiter ce phénomène.

Paradoxe des anniversaires

Parmi 23 personnes, la probabilité que deux d’entre-elles aient leur anniversaire le même jour est inférieur à 0,5. En effet, cette probabilité est de \(\frac{m!}{(m-n)!}×\frac1{m^n}\)

On considère les clefs suivantes, avec \(n = 11\) :

d = {16: 'Rubis', 18: 'Jade', 6: 'Topaze', 29: 'Opale', 50: 'Perle',
13: 'Saphir', 27: 'Agate', 31: 'Grenat', 28: 'Onyx'}

Calculons les différentes alvéoles, liées aux clefs :

for clef in d.keys():
    print(clef % 11, end=", ")

5, 7, 6, 7, 6, 2, 5, 9, 6, 

On a donc la présence de quelques collisions.

Parmi les idées présentes, on peut en distinguer deux.

• Le tableau contient des listes chaînées et l’alvéole permet de savoir quel bucket contient la liste chaînée qui doit être parcourue pour trouver la clef.

Exercise 13.2 (Mise en œuvre de la liste chaînée)

Modifier la classe Dictionnaire proposée ci-dessus pour mettre en œuvre cette idée. En particulier, il faudra répondre aux points suivants :

• la méthode inserer doit ajouter le couple (clef,valeur) à la suite de la liste chaînée

• la méthode obtenir doit parcourir la liste chaînée stockée dans l’alvéole correspondant à la clef. On pourra utiliser l’implémentation de liste du cours.

Le tableau doit contenir les listes suivantes :

0 -> None
1 -> None
2 -> (13,Saphir)
3 -> None
4 -> None
5 -> (16, Rubis) -> (27, Agate) -> None
6 -> (6, Topaze) -> (50, Perle) -> (28, Onyx) -> None
7 -> (18, Jade) -> (29, Opale) -> None
8 -> None
9 -> (31, Grenat)
10 -> None

Il existe une autre méthode dite par coalescence qui consiste à stocker, en plus de la clef et de la valeur, un pointeur vers _suivant. Cette valeur est initialisée à une valeur inexistante (-1 ou None) et lorsqu’une collision survient, on modifie cette valeur vers la valeur suivante libre.

Example 13.2 (exemple de coalescence)

On insère (16,Rubis), (18,Jade) et (6, Topaze) (on omet dans cette représentation les alvéoles vides, qui contiennent initialement (None,None,-1)):

5 -> (16, Rubis, -1)
6 -> (6, Topaze, -1)
7 -> (18, Jade, -1)

La liste des emplacements vides est [10,9,8,4,3,2,1,0]

À l’étape suivante, on obtient alors, après insertion de (29, Opale), (50, Perle) et (13, Saphir).

2 -> (13, Saphir, -1)
5 -> (16, Rubis, -1)
6 -> (6, Topaze, 9)
7 -> (18, Jade, 10)
9 -> (50, Perle)
10 -> (29, Opale)

Dans le cas de la coalescence, on obtient in fine une liste chaînée «par l’exétérieur», contrairement aux listes chaînées «à l’intérieur» dans le cas du chaînage simple.

Cette méthode est assez facile à mettre en œuvre, mais présente des inconvénients comme une limite au nombre de clefs (la taille de la table) et comme la table dépend de l’ordre de toutes les clefs, la suppression s’avère assez coûteuse.

Il existe d’autres méthodes de résolution des collisions, mais qui seront évoquées dans l’enseignement supérieur, de même que les fonctions de hachage.

Exercise 13.3

On considère un tableau de hachage dont la fonction de hash est x mod 257. Donner les valeurs des emplacements de

• 1

• 34

• 236

• 2678

Exercise 13.4

On considère un tableau de hachage dont la fonction de hash est x mod 257. On suppose que les collisions sont gérées par chaînage interne. Donner une représentation après l’insertion de

• 2547

• 1548

• 1478

• 450

• 263

• 520

Exercise 13.5

Reprendre l’exercice précédent, en insérant les valeurs dans l’ordre croissant.

Exercise 13.6

On considère un tableau de hachage dont la fonction de hash est x mod 257. On suppose que les collisions sont gérées par chaînage externe (coalescence). Donner une représentation après l’insertion de

• 2547

• 1548

• 1478

• 450

• 263

• 520

Exercise 13.7

Reprendre l’exercice précédent, en insérant les valeurs dans l’ordre croissant.

13.3. Vers les fonctions de hachage sur des objets génériques

Cette partie peut-être lue plus tard dans votre formation

En Python, on peut créer un hash, avec la fonction hash qui utilise la méthode __hash__ de la classe de l’objet.

hash('toto')

3878152655148788289

Le principe de cette fonction de hash est de fournir un condensat qui soit tel que

• deux objets différents ont des condensats différents

• le hash soit rapide à calculer

hash('toto') == hash('tot')

False

On peut s’en rendre compte en comparant les temps d’exécution.

def compare_chaine(chaine1, chaine2):
    for position in range(len(chaine1)):
        if chaine1[position] != chaine2[position]:
            return False
    return True

%timeit compare_chaine(s1,s2)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[27], line 1
----> 1 get_ipython().run_line_magic('timeit', 'compare_chaine(s1,s2)')

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/interactiveshell.py:2480, in InteractiveShell.run_line_magic(self, magic_name, line, _stack_depth)
   2478     kwargs['local_ns'] = self.get_local_scope(stack_depth)
   2479 with self.builtin_trap:
-> 2480     result = fn(*args, **kwargs)
   2482 # The code below prevents the output from being displayed
   2483 # when using magics with decorator @output_can_be_silenced
   2484 # when the last Python token in the expression is a ';'.
   2485 if getattr(fn, magic.MAGIC_OUTPUT_CAN_BE_SILENCED, False):

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/magics/execution.py:1185, in ExecutionMagics.timeit(self, line, cell, local_ns)
   1183 for index in range(0, 10):
   1184     number = 10 ** index
-> 1185     time_number = timer.timeit(number)
   1186     if time_number >= 0.2:
   1187         break

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/magics/execution.py:173, in Timer.timeit(self, number)
    171 gc.disable()
    172 try:
--> 173     timing = self.inner(it, self.timer)
    174 finally:
    175     if gcold:

File <magic-timeit>:1, in inner(_it, _timer)

NameError: name 's1' is not defined

def compare_hash(chaine1, chaine2):
    if hash(chaine1) != hash(chaine2):
        return False
    else:
        return True

%timeit compare_hash(s1, s2)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[29], line 1
----> 1 get_ipython().run_line_magic('timeit', 'compare_hash(s1, s2)')

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/interactiveshell.py:2480, in InteractiveShell.run_line_magic(self, magic_name, line, _stack_depth)
   2478     kwargs['local_ns'] = self.get_local_scope(stack_depth)
   2479 with self.builtin_trap:
-> 2480     result = fn(*args, **kwargs)
   2482 # The code below prevents the output from being displayed
   2483 # when using magics with decorator @output_can_be_silenced
   2484 # when the last Python token in the expression is a ';'.
   2485 if getattr(fn, magic.MAGIC_OUTPUT_CAN_BE_SILENCED, False):

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/magics/execution.py:1185, in ExecutionMagics.timeit(self, line, cell, local_ns)
   1183 for index in range(0, 10):
   1184     number = 10 ** index
-> 1185     time_number = timer.timeit(number)
   1186     if time_number >= 0.2:
   1187         break

File /builds/lamadone/informatique/terminale-nsi/.venv/lib/python3.11/site-packages/IPython/core/magics/execution.py:173, in Timer.timeit(self, number)
    171 gc.disable()
    172 try:
--> 173     timing = self.inner(it, self.timer)
    174 finally:
    175     if gcold:

File <magic-timeit>:1, in inner(_it, _timer)

NameError: name 's1' is not defined

On imagine le cas suivant : on dispose d’un dictionnaire dont les clefs sont des chaines de caractères ASCII (8 bits). Écrire une fonction str_to_int, qui a une chaine de caractères associe un entier.

On appelle cette méthode de factorisation, la méthode de Horner, qui donne permet de calculer le polynôme suivant

\(P = a_0 X^d + a_1 X^{d-1} + \dots + a_{d-1} X + a_d\)

\(P = (a_0 X^{d-1} + a_1 X^{d-2} + \dots + a_{d-1}) X + a_d\)

\(P = ((a_0 X^{d-2} + a_1 X^{d-3} + \dots + a_{d-2})X + a_{d-1}) X + a_d\)

def chaine_en_entier(chaine: str) -> int:

Show code cell content Hide code cell content

def chaine_en_entier(chaine: str) -> int:
    n = 0
    for lettre in chaine:
        n = n * 256 + ord(lettre)
    return n

chaine_en_entier('toto')

1953461359

On aimerait que “toto”, “toot”, “oott”, “ttoo” renvoient le même résultat

chaine_en_entier('toot')

1953460084

chaine_en_entier('toot') % 255

199

chaine_en_entier('toto') % 255

199

---

[1]

un tableau possède la propriété d’avoir un accès direct en \(\mathcal{O}(n)\) pour les insertions et les modifications.

[2]

une fonction \(f\colon E \to F\) est dite injective lorsque, \(\forall (x, y) \in E^2,\ f(x) = f(y) \implies x = y\), autrement dit, si deux images sont identiques, c’est que les antécédents le sont aussi.

[3]

une possibilité est de prendre un nombre premier comme module de division. On peut aussi consulter ce cours de licence d’informatique.