Améliorez vos compétences Python: examen du dictionnaire

une table de hachage (table de hachage) est une structure de données qui implémente un type de données abstrait tableau associatif, une structure qui peut mapper des clés à des valeurs.

Si ça sent comme un Python dict, ça ressemble à un dict, et ça ressemble à un… eh bien, ça doit être un dict. Absolument! Oh, et setaussi ...

Hein?

Les dictionnaires et ensembles en Python sont implémentés à l'aide d'une table de hachage. Cela peut sembler intimidant au début, mais au fur et à mesure que nous approfondissons nos recherches, tout doit être clair.

Objectif

Tout au long de cet article, nous découvrirons comment a dictest implémenté en Python, et nous créerons notre propre implémentation (simple). L'article est divisé en trois parties et la création de notre dictionnaire personnalisé a lieu dans les deux premières:

  1. Comprendre ce que sont les tables de hachage et comment les utiliser
  2. Se plonger dans le code source de Python pour mieux comprendre comment les dictionnaires sont implémentés
  3. Explorer les différences entre le dictionnaire et d'autres structures de données telles que les listes et les ensembles

Qu'est-ce qu'une table de hachage?

Une table de hachage est une structure conçue pour stocker une liste de paires clé-valeur, sans compromettre la vitesse et l'efficacité de la manipulation et de la recherche de la structure.

L'efficacité de la table de hachage est dérivée de la fonction de hachage - une fonction qui calcule l'index de la paire clé-valeur - ce qui signifie que nous pouvons rapidement insérer, rechercher et supprimer des éléments puisque nous connaissons leur index dans le tableau mémoire.

La complexité commence lorsque deux de nos clés hachent la même valeur. Ce scénario est appelé une collision de hachage . Il existe de nombreuses façons différentes de gérer une collision, mais nous ne couvrirons que la voie de Python. Nous n'irons pas trop loin dans l'explication de notre table de hachage dans le but de garder cet article convivial pour les débutants et axé sur Python.

Assurons-nous de bien comprendre le concept des tables de hachage avant de passer à autre chose. Nous commencerons par créer les squelettes de notre custom très (très) simple dictcomposé uniquement de méthodes d'insertion et de recherche, en utilisant certaines des méthodes dunder de Python. Nous devrons initialiser la table de hachage avec une liste d'une taille spécifique et activer l'abonnement (signe []) pour cela:

Maintenant, notre liste de tables de hachage doit contenir des structures spécifiques, chacune contenant une clé, une valeur et un hachage:

Exemple de base

Une petite entreprise de 10 employés souhaite conserver des registres contenant les jours de maladie restants de ses employés. Nous pouvons utiliser la fonction de hachage suivante, afin que tout puisse tenir dans le tableau mémoire:

length of the employee's name % TABLE_SIZE

Définissons notre fonction de hachage dans la classe Entry:

Nous pouvons maintenant initialiser un tableau de 10 éléments dans notre table:

Attendez! Pensons-y. Nous allons très probablement aborder certaines collisions de hachage. Si nous n'avons que 10 éléments, il nous sera beaucoup plus difficile de trouver un espace ouvert après une collision. Décidons que notre table aura le double de la taille - 20 éléments! Cela sera utile à l'avenir, je le promets.

Pour insérer rapidement chaque employé, nous suivrons la logique:

array[length of the employee's name % 20] = employee_remaining_sick_days

Notre méthode d'insertion ressemblera donc à ce qui suit (pas encore de gestion des collisions de hachage):

Pour la recherche, nous faisons essentiellement la même chose:

array[length of the employee's first name % 20] 

Nous n'avons pas encore fini!

Gestion des collisions Python

Python utilise une méthode appelée Open Addressing pour gérer les collisions. Il redimensionne également les tables de hachage lorsqu'il atteint une certaine taille, mais nous ne discuterons pas de cet aspect. Définition de l'adressage ouvert de Wikipedia:

Dans une autre stratégie, appelée adressage ouvert, tous les enregistrements d'entrée sont stockés dans le tableau de compartiment lui-même. Lorsqu'une nouvelle entrée doit être insérée, les compartiments sont examinés, en commençant par l'emplacement haché vers et en suivant une séquence de sonde , jusqu'à ce qu'un emplacement inoccupé soit trouvé. Lors de la recherche d'une entrée, les compartiments sont analysés dans la même séquence, jusqu'à ce que l'enregistrement cible soit trouvé, ou qu'un emplacement de tableau inutilisé soit trouvé, ce qui indique qu'il n'y a pas de clé de ce type dans la table.

Examinons le processus de récupération d'une valeur par key, en regardant le code source Python (écrit en C):

  1. Calculer le hachage de key
  2. Calculez le indexde l'élément par hash & maskmask = HASH_TABLE_SIZE-1(en termes simples - prenez N derniers bits des bits de hachage):
i = (size_t)hash & mask;

3. Si vide, retour DKIX_EMPTYqui se traduit finalement par un KeyError:

if (ix == DKIX_EMPTY) { *value_addr = NULL; return ix;}

4. S'il n'est pas vide, comparez les clés et les hachages et définissez l' value_addradresse sur l'adresse de valeur réelle si égale:

if (ep->me_key == key) { *value_addr = ep->me_value; return ix;}

et:

if (dk == mp->ma_keys && ep->me_key == startkey) { if (cmp > 0) { *value_addr = ep->me_value; return ix; }}

5. Si ce n'est pas égal, utilisez différents bits du hachage (algorithme expliqué ici) et passez à nouveau à l'étape 3:

perturb >>= PERTURB_SHIFT;i = (i*5 + perturb + 1) & mask;

Voici un diagramme pour illustrer l'ensemble du processus:

Le processus d'insertion est assez similaire - si l'emplacement trouvé est vide, l'entrée est insérée, si elle n'est pas vide, nous comparons la clé et le hachage - si égal, nous remplaçons la valeur, et sinon nous continuons notre quête de recherche un nouveau spot avec l' perturbalgorithme.

Emprunter des idées à Python

Nous pouvons emprunter l'idée de Python de comparer les clés et les hachages de chaque entrée à notre objet d'entrée (en remplaçant la méthode précédente):

Notre table de hachage n'a toujours pas de gestion des collisions - implémentons-en une! Comme nous l'avons vu précédemment, Python le fait en comparant les entrées puis en changeant le masque des bits, mais nous le ferons en utilisant une méthode appelée sonde linéaire (qui est une forme d'adressage ouvert, expliquée ci-dessus):

Lorsque la fonction de hachage provoque une collision en mappant une nouvelle clé à une cellule de la table de hachage qui est déjà occupée par une autre clé, le sondage linéaire recherche dans la table l'emplacement libre suivant le plus proche et y insère la nouvelle clé.

So what we’re going to do is to move forward until we find an open space. If you recall, we implemented our table with double the size (20 elements and not 10) — This is where it comes handy. When we move forward, our search of an open space will be much quicker because there’s more room!

But we have a problem. What if someone evil tries to insert the 11th element? We need to raise an error (we won’t be dealing with table resizing in this article). We can keep a counter of filled entries in our table:

Now let’s implement the same in our searching method:

The full code can be found here.

Now the company can safely store sick days for each employee:

Python Set

Going back to the beginning of the article, set and dict in Python are implemented very similarly, with set using only key and hash inside each record, as can be seen in the source code:

typedef struct { PyObject *key; Py_hash_t hash; /* Cached hash code of the key */} setentry;

As opposed to dict, that holds a value:

typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key; PyObject *me_value; /* This field is only meaningful for combined tables */} PyDictKeyEntry;

Performance and Order

Time comparison

I think it’s now clear that a dict is much much faster than a list (and takes way more memory space), in terms of searching, inserting (at a specific place) and deleting. Let's validate that assumption with some code (I am running the code on a 2017 MacBook Pro):

And the following is the test code (once for the dict and once for the list, replacing d):

The results are, well, pretty much what we expected..

dict: 0.015382766723632812 seconds

list:55.5544171333313 seconds

Order depends on insertion order

The order of the dict depends on the history of insertion. If we insert an entry with a specific hash, and afterwards an entry with the same hash, the second entry is going to end up in a different place then if we were to insert it first.

Before you go…

Thanks for reading! You can follow me on Medium for more of these articles, or on GitHub for discovering some cool repos :)

If you enjoyed this article, please hold down the clap button ? to help others find it. The longer you hold it, the more claps you give!

And do not hesitate to share your thoughts in the comments below, or correct me if I got something wrong.

Additional resources

  1. Hash Crash: The Basics of Hash Tables
  2. The Mighty Dictionary
  3. Introduction to Algorithms