Hash et dictionnaires

Limites des séquences

Les indices sont forcément des entier

Les séquences que sont les listes, tuples, chaînes et ranges sont pratiques pour stocker des données ordonnées qu'on retrouve par un indice c'est à dire un nombre entier. Cependant nous sommes embêtés si on souhaite stocker et retrouver des données non par un nombre entier mais par un autre type d'objet, par exemple des chaînes.

Certaines opérations sont lentes

Une autre limitation des séquences est leur performance faible pour certaines opérations.

L'accès à un élément par son indice, et éventuellement sa modification, se font en un temps fixe, on dit complexité O(1), ce qui est la meilleure performance possible.

En revanche toute opération qui nécessite la recherche d'un élément, par exemple avec l'opérateur in, la méthode index() des str, ou la méthode remove() des list, se fait en temps linéaire qui dépend de la taille n de la séquence, on dit complexité O(n). Pour trouver un élément en particulier dans une séquence il faut la parcourir en partant du début et chercher ainsi élément par élément jusqu'à ce qu'on le trouve. Dans le meilleur des cas l'élément cherché est le premier, ça sera très rapide. Dans le pire des cas l'élément cherché sera le dernier ou n'existera pas du tout dans la séquence, ainsi elle aura été parcourue en entier.

Dans une liste, la suppression d'un élément par son indice est aussi en complexité O(n) car il faut déplacer d'une "case" en mémoire vers le début de la liste tous les éléments suivants. (on dit "case" pour signifier la taille en mémoire de chaque position du tableau). L'insertion à un autre endroit qu'à la fin de la liste est aussi en complexité O(n), avec le pire cas quand on insère au premier indice (indice 0), car il faut déplacer tous les éléments suivants cette fois-ci d'une "case" mémoire vers la fin de la liste.

Les tables de hachage

Elles sont un type de données qui résout les deux problèmes listés plus haut. On les appelle aussi tables de hash ou tableaux associatifs. En anglais on les appelle map, hashmap, hash table ou encore associative arrays.

Contrairement aux séquences qui sont ordonnées par des indices qui commencent par zéro, une table de hachage n'est pas ordonnée. C'est une collection, un ensemble de valeurs ou bien de couples (clé, valeur).

Dans le concept, une table de hachage est un tableau associé à une fonction de hachage. Cette fonction fait la correspondance entre une valeur quelconque passée en entrée et une case du tableau en sortie. À chaque valeur différente qu'on lui passera correspondra idéalement une case unique du tableau. Et pour deux valeurs identiques, la fonction doit désigner toujours la même case du tableau. Dans ce tableau on pourra y stocker la valeur utilisée pour calculer son hash, mais aussi si on souhaite une valeur associée, dans ce cas on dit que la valeur qui sert à calculer le hash est une clé qui a une valeur associée dans la table de hachage.

Ce mécanisme permet de stocker et retrouver des valeurs stockées et potentiellement leur valeur associée:

• indexées et donc retrouvées non pas par un nombre, mais par une valeur arbritraire, ce qui en fait un mécanisme de stockage très polyvalent

• sans avoir à parcourir le tableau en entier, car la fonction de hachage nous donne directement la case qu'on cherche, ce qui est très rapide

La performance de la table de hachage va dépendre ainsi de la performance de la fonction pour calculer le hash de la valeur cherchée, donc en temps fixe O(1).

Il arrive que la fonction de hash, n'étant pas parfaite, donne en sortie la même case du tableau pour deux valeurs pourtant différentes en entrée. On appelle cette situation une collision et c'est un problème. Il est résolu en stockant dans le tableau non pas une seule valeur, ou un seul couple (clé, valeur), mais plusieurs. Ainsi en cas de collision, la recherche continue cette fois-ci au sein de la case du tableau en faisant une recherche séquentielle élément par élément (ou clé par clé s'il s'agit de couples stockés), comme dans une séquence. On retombe donc sur le même problème de performance vu avec les séquences. C'est pour ça qu'une table de hachage est conçue de façon à limiter au maximum les collisions.

Une table de hachage sait aussi gérer la taille de son tableau en fonction du nombre d'éléments qu'il contient de façon à maintenir les collisions potentielles au minimum tout en minimisant la taille du tableau afin de ne pas gaspiller de mémoire.

Les types de donnée hashables en Python

Un type de donnée est hashable si:

• ses objets ont la méthode spéciale __hash__() qui calcule la valeur de hash à partir de la valeur de l'objet en question

• l'objet est immutable

• sa valeur peut être comparée à celle d'autres objets avec l'opérateur ==, donc il doit avoir la méthode spéciale __eq__(). Des objets qui sont hashables doivent donner la même valeur de hash s'ils sont considérés égaux lors de leur comparaison (sans être forcément le même objet, voir valeur VS identité).

Les types built-in de Python qui sont immutables sont (quasiment) tous hashables. Les types mutables comme les listes et les dictionnaires sont non hashables. Les tuples (et tout autre conteneur immutable) sont un peu spéciaux: ils sont immutables donc hashables, mais attention, seulement s'ils ne contiennent que des objets de type eux aussi hashables. Donc le tuple (3, 2, "Toto") est un tuple hashable car le int 3, le int 2 et la str "toto" sont tous hashables (types built-in immutables). Par contre le tuple (["coucou", 2], True) n'est pas hashable car son premier élément est de type list (type built-in mutable).

Pourquoi les types mutables ne sont pas hashables? Car rappelez-vous qu'une valeur de hash est calculée à partir de la valeur de l'objet. Deux objets qui ne sont pas les mêmes, donc n'ayant pas la même identité obtenue par la fonction id(), peuvent avoir la même valeur, c'est à dire que la comparaison avec == entre ces deux objets donne True. Cette comparaison est faite grâce à leur méthode spéciale __eq__(). Et par conséquence deux objets de même valeur doivent donner la même valeur de hash, par leur fonction __hash__(). Hors si la valeur d'un objet change, sa valeur de hash doit aussi changer, dans une table de hash cela n'aurait aucun sens d'insérer une clé qui peut changer à tout moment, car on ne pourrait plus le retrouver ensuite si sa valeur de hash change par rapport au moment de son insertion, et il serait aussi stocké dans la mauvaise case du tableau s'il change après insertion.

Pour vos propres types de données (vos classes), les objets sont considérés hashables par défaut car ils se comparent tous comme non-égaux sauf avec eux-même, et ils dérivent leur valeur de hash à partir de leur identifiant. Cela a été fait ainsi pour que vous puissiez utiliser facilement des instances de vos propres classes comme clés des dictionnaires, sans trop vous soucier des détails. Cependant cela se complique dès qu'on veut redéfinir les méthodes __eq__() et/ou __hash__() de nos objets car elles doivent respecter les règles citées plus haut pour qu'un type de donnée soit hashable. La méthode __neq__() donne par défaut l'inverse de __eq__(), on ne la redéfinit donc pas en général.

En Python on utilise la fonction built-in hash(), qui prend n'importe quel objet hashable en paramètre, et retourne sa valeur de hash sous forme de int:

		>>> hash(5)
		5

		>>> hash("Bonjour")
		2689713187822685706

		>>> hash(("ceci", "est", "un", "tuple", "de", "str"))
		-7366719707112751249

		>>> hash([])
		TypeError: unhashable type: 'list'

		>>> hash(("tuple", "avec", "liste", []))
		TypeError: unhashable type: 'list'
	

La fonction hash() utilise la méthode spéciale __hash__() de l'objet, c'est équivalent:

		>>> a = 5
		>>> a.__hash__()
		5

		>>> "Bonjour".__hash__()
		2689713187822685706

		>>> hash(("ceci", "est", "un", "tuple", "de", "str"))
		-7366719707112751249

		>>> [].__hash__()
		TypeError: 'NoneType' object is not callable
	

Le type dict

Les dictionnaires sont parmi les types de base les plus utilisés en Python, avec les nombres, les chaînes, les listes et les tuples. Ils sont une implémentation de table de hachage, ils ont donc les avantages vus plus haut. L'insertion d'éléments, la recherche d'éléments, et la suppression d'éléments dans un dictionnaire sont indépendants de la taille du dictionnaire, ces opérations sont ainsi très rapides. Le nom exact de ce type de donnée est dict.

Les dict sont un type de donnée mutable, un dictionnaire peut donc être modifié directement sans avoir besoin de créer des copies en mémoire, ce qui est très efficace.

Un dict associe des valeurs à des clés. Les clés doivent être des objets de type hashable. Les valeurs peuvent être de n'importe quel type. Chaque clé est unique dans le dictionnaire, et à chaque clé correspond une seule valeur, qui elle peut ne pas être unique.

Bien qu'une table de hachage n'a pas de notion d'ordre de ses éléments, les éléments dans un dict en Python sont ordonnés par l'ordre d'insertion des clés, mais ce n'est en général pas une considération importante.

Création de dictionnaires

Avec des valeurs littérales

		# Un dict vide:
		d = {}

		# Un dict initialisé avec des clés et valeurs de différents types:
		d = {'a': 10, 'b': 20, 'c': 15, ('i', 'j'): 'Bonjour', 8: [0, 1, 2]}
	

Quand la valeur littérale d'un dict est trop longue, on peut l'écrire de façon à avoir une clé et sa valeur par ligne, comme ceci:

		# Ecriture plus lisible d'un dictionnaire
		d = {
			'a': 10,
			'b': 20,
			'c': 15,
			('i', 'j'): 'Bonjour',
			8: [0, 1, 2]
		}
	

On peut ajouter une virgule après le dernier élément, ce n'est pas considéré comme une erreur de syntaxe:

		d = {
			'a': 10,
			'b': 20, # virgule à la fin n'est pas une erreur de syntaxe
		}
	

Avec le constructeur dict()

		# Un dict vide:
		d = dict()
		d == {}


		# Donne les clé et valeurs de départ grâce à des paramètres nommés,
		# mais dans ce cas les clés sont forcément des str:
		d = dict(un=1, deux=2)
		d == {'un': 1, 'deux': 2}


		# Donne les clés et valeurs de départ dans un iterable de couples,
		# par exemple ici une liste de tuples qui contiennent clé et valeur:
		d = dict([
			('un', 1),
			('deux', 2)
		])
		d == {'un': 1, 'deux': 2}


		# On peut aussi rajouter des arguments nommés à l'appel du constructeur
		# pour ajouter initialement des couples non présents dans l'itérable:
		d = dict(
			[('un',1), ('deux',2)],
			trois=3,
			quatre=4
		)
		d == {'un': 1, 'deux': 2, 'trois': 3, 'quatre': 4}


		# Copie (superficielle) à partir d'un autre dict:
		d1 = {'un': 1, 'deux': 2}
		d2 = dict(d1)
		d2 == {'un': 1, 'deux': 2}


		# Copie (superficielle) à partir d'un autre dict
		# avec en plus ajout d'élements initiaux grâce à des arguments nommés:
		d2 = dict(
			d1,
			trois=3,
			quatre=4
		)
		d2 == {'un': 1, 'deux': 2, 'trois': 3, 'quatre': 4}
	

Ajouter, retrouver et modifier des valeurs

Pour ajouter une nouvelle clé et sa valeur dans un dict existant, on utilise l'indexation et l'affectation:

		d = {}
		d['un'] = 1
		d['deux'] = 2
		d == {'un': 1, 'deux': 2}
	

Pour retrouver la valeur associée à une clé dans un dict, on utilise l'indexation:

		d = {'un': 1, 'deux': 2}
		d['un'] == 1
	

Pour modifier la valeur associée à une clé existante, on utilise encore l'indexation et l'affectation:

		d = {'un': 1, 'deux': 2}
		d['un'] = 10
		d['un'] == 10
	

Suppression des clés / valeurs

Supprimer une clé et sa valeur asssociée se fait avec l'instruction del

		d = {'a': 5}
		del d['a']
		print(d) # Affiche {}
	

Tenter d’accéder à, ou de supprimer une clé inexistante provoque une erreur de type KeyError

		d = {'a': 5}
		try:
			print(d['b'])
		except:
			print("Cette clé n'existe pas") # Ce message sera affiché
	

Test d'existence d'une clé

L’opérateur booléen in peut être utilisé pour savoir si une clé est présente dans un dict:

		d = {'a': 5, 'b': 15}
		'a' in d # Vaut True
		'c' in d # Vaut False
	

Boucles sur les dict

Les dict ont plusieurs méthodes qui nous retournent des iterable afin de les parcourir.

Boucler sur un dict directement nous retourne les clés une par une:

		d = {'a': 'bonjour', 'b': 'à', 'c': 'vous'}

		for clé in d:
			print(clé, d[clé])
	

C'est équivalent à utiliser la méthode keys():

		for clé in d.keys():
			print(clé, d[clé])
	

Plus efficace (en terme d'écriture de code et de performance) si on veut obtenir chaque clé et sa valeur associée, on peut boucler sur un dict avec la méthode items():

		# Remarquez les deux variables de la boucle for
		for clé, valeur in d.items():
			print(clé, valeur)
	

Si on ne veut que les valeurs on utilise la méthode values():

		for valeur in d.values():
			print(valeur)
	

Vider un dict

Pour supprimer tous les éléments d’un dict, on peut appeler sa méthode clear()

		monDict.clear()
	

Longueur d'un dict

On peut avoir la longueur d'un dictionnaire avec la fonction len() (comme pour les listes):

		d = {'a': 'bonjour', 'b': 'à', 'c': 'vous'}

		len(d) # retourne 3