Tables de hachage

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Définition

Stocke un ensemble d’éléments

Paires clé-valeur

  lasagna: 14.75
  moussaka: 21.15
  sushi: 16.05

Presque tous langages programmation ont table hachage :
- tables et cartes hachage, dictionnaires, tables associatives
- Python : dictionnaires

Structure

Chaque position : slot/bucket

Représentation schématique d’une table de hachage vide.

Fonctions de hachage

Représentation schématique d’une table de hachage vide. Le prix des lasagnes a été inséré à la cinquième position.

Fonctions de hachage

Représentation schématique d’une table de hachage avec les mots « Fonction de hachage » au milieu d’une flèche qui associe le mot « Lasagne » à la valeur en cinquième position.

Chaque fois fonction de hachage appliquée
- doit renvoyer même valeur pour même entrée

Recherches

Représentation schématique d’une table de hachage avec certaines valeurs.

Trouver « lasagne »
- hash("lasagna") -> 5

Recherches

Représentation schématique d’une table de hachage avec quelques valeurs. La valeur à la cinquième position est en vert.

Trouver « lasagne »
- hash("lasagna") -> 5
- renvoie 14,75
$O(1)$

Collisions

Hachage peut renvoyer même sortie pour entrées différentes
hash("moussaka") -> 1

Représentation schématique d’une table de hachage avec quelques valeurs. La valeur à la première position est colorée en jaune.

insérer : moussaka -> 21,15
Collision !
- doit être résolu
- plusieurs techniques

Dictionnaire Python

Dictionnaire vide

my_empty_dictionary = {}

Dictionnaire avec éléments

my_menu = {
    'lasagna': 14.75,
    'moussaka': 21.15,
    'sushi': 16.05
}

Dictionnaire Python - get

print(my_menu['sushi'])

16.05

print(my_menu['paella'])

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'paella'

print(my_menu.get('paella'))

None

Dictionnaire Python - éléments, clés et valeurs

Obtenir éléments

print(my_menu.items())

dict_items([('lasanga', 14.75), 
            ('moussaka', 21.15),
            ('sushi', 16.05)])

Obtenir clés

print(my_menu.keys())

dict_keys(['lasanga', 'moussaka', 'sushi'])

Obtenir valeurs

print(my_menu.values())

dict_values([14.75, 21.15, 16.05])

Dictionnaire Python - insérer

my_menu['samosas'] = 13

print(my_menu.items())

dict_items([('lasanga', 14.75), ('moussaka', 21.15), ('sushi', 16.05), ('samosas', 13)])

Dictionnaire Python - modifier

print(my_menu.get('sushi'))

16.05

my_menu['sushi'] = 20

print(my_menu.get('sushi'))

Dictionnaire Python - supprimer

Supprime complètement dictionnaire

del my_menu

Supprime paire clé-valeur

del my_menu["sushi"]

Vide un dictionnaire

my_menu.clear()

Dictionnaire Python - itérer

for key, value in my_menu.items():
  print(f"
key: {key}")
  print(f"value: {value}")


key: lasagna

value: 14.75
key: moussaka

value: 21.15
key: sushi
value: 16.05

Dictionnaire Python - itérer

for dish in my_menu:
  print(dish)

lasagna
moussaka
sushi

for prices in my_menu.values():
  print(prices)

14.75
21.15
16.05

Dictionnaire Python - dictionnaires imbriqués

Dictionnaire imbriqué

my_menu = {
  'sushi' : {
    'price' : 19.25,
    'best_served' : 'cold'
  },
  'paella' : {
    'price' : 15,
    'best_served' : 'hot'
  }
}

Passons à la pratique !

Structures de données et algorithmes en Python