Migliora le tue abilità in Python: esame del dizionario

una tabella hash (mappa hash) è una struttura di dati che implementa un tipo di dati astratto di matrice associativa, una struttura che può mappare le chiavi ai valori.

Se ha l'odore di un pitone dict, si sente come un dicte sembra uno ... beh, deve essere un dict. Assolutamente! Oh, e setanche ...

Eh?

Dizionari e set in Python vengono implementati utilizzando una tabella hash. All'inizio può sembrare scoraggiante, ma mentre indaghiamo ulteriormente tutto dovrebbe essere chiaro.

Obbiettivo

In questo articolo, scopriremo come a dictè implementato in Python e costruiremo la nostra implementazione di uno (semplice). L'articolo è diviso in tre parti e la costruzione del nostro dizionario personalizzato avviene nelle prime due:

  1. Capire cosa sono le tabelle hash e come usarle
  2. Immergersi nel codice sorgente di Python per capire meglio come vengono implementati i dizionari
  3. Esplorare le differenze tra il dizionario e altre strutture di dati come elenchi e set

Cos'è una tabella hash?

Una tabella hash è una struttura progettata per archiviare un elenco di coppie chiave-valore, senza compromettere la velocità e l'efficienza della manipolazione e della ricerca nella struttura.

L'efficacia della tabella hash deriva dalla funzione hash, una funzione che calcola l'indice della coppia chiave-valore, nel senso che possiamo inserire, cercare e rimuovere rapidamente elementi poiché conosciamo il loro indice nell'array di memoria.

La complessità inizia quando due delle nostre chiavi hanno lo stesso valore. Questo scenario è chiamato collisione hash . Ci sono molti modi diversi per gestire una collisione, ma tratteremo solo il modo in cui Python. Non andremo troppo in profondità con la nostra spiegazione della tabella hash per il bene di mantenere questo articolo adatto ai principianti e incentrato su Python.

Assicuriamoci di aver pensato bene al concetto di tabelle hash prima di andare avanti. Inizieremo creando gli scheletri per il nostro molto (molto) semplice custom dictcomposto solo da metodi di inserimento e ricerca, usando alcuni dei metodi stupidi di Python. Avremo bisogno di inizializzare la tabella hash con un elenco di una dimensione specifica e abilitare l'abbonamento (segno []) per esso:

Ora, il nostro elenco di tabelle hash deve contenere strutture specifiche, ognuna contenente una chiave, un valore e un hash:

Esempio di base

Una piccola azienda con 10 dipendenti desidera tenere un registro contenente i giorni di malattia rimanenti dei propri dipendenti. Possiamo usare la seguente funzione hash, quindi tutto può stare nell'array di memoria:

length of the employee's name % TABLE_SIZE

Definiamo la nostra funzione hash nella classe Entry:

Ora possiamo inizializzare un array di 10 elementi nella nostra tabella:

Aspettare! Riflettiamoci. Molto probabilmente affronteremo alcune collisioni di hashish. Se abbiamo solo 10 elementi, sarà molto più difficile per noi trovare uno spazio aperto dopo una collisione. Decidiamo che il nostro tavolo avrà il doppio delle dimensioni: 20 elementi! Tornerà utile in futuro, lo prometto.

Per inserire velocemente ogni dipendente, seguiremo la logica:

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

Quindi il nostro metodo di inserimento sarà simile al seguente (ancora nessuna gestione delle collisioni hash):

Per la ricerca, fondamentalmente facciamo lo stesso:

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

Non abbiamo ancora finito!

Gestione delle collisioni Python

Python utilizza un metodo chiamato Open Addressing per la gestione delle collisioni. Ridimensiona anche le tabelle hash quando raggiunge una certa dimensione, ma non discuteremo di questo aspetto. Definizione di indirizzamento aperta da Wikipedia:

In un'altra strategia, chiamata indirizzamento aperto, tutti i record delle voci vengono memorizzati nell'array di bucket stesso. Quando è necessario inserire una nuova voce, i bucket vengono esaminati, iniziando dallo slot con hash e procedendo in una sequenza di sonda , fino a trovare uno slot non occupato. Durante la ricerca di una voce, i bucket vengono scansionati nella stessa sequenza, fino a quando non viene trovato il record di destinazione o uno slot di array inutilizzato, il che indica che non esiste una chiave di questo tipo nella tabella.

Esaminiamo il processo di recupero di un valore keyosservando il codice sorgente Python (scritto in C):

  1. Calcola hash di key
  2. Calcola l' indexelemento in base a hash & maskdove mask = HASH_TABLE_SIZE-1(in termini semplici, prendi N ultimi bit dai bit hash):
i = (size_t)hash & mask;

3. Se vuoto, restituisce DKIX_EMPTYche alla fine si traduce in KeyError:

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

4. Se non è vuoto, confronta chiavi e hash e imposta l' value_addrindirizzo all'indirizzo del valore effettivo, se uguale:

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

e:

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

5. Se non è uguale, usa bit differenti dell'hash (algoritmo spiegato qui) e vai di nuovo al passaggio 3:

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

Ecco un diagramma per illustrare l'intero processo:

Il processo di inserimento è abbastanza simile: se lo slot trovato è vuoto, la voce viene inserita, se non è vuota confrontiamo la chiave e l'hash - se uguale, sostituiamo il valore e in caso contrario continuiamo la nostra ricerca di trovare un nuovo punto con l' perturbalgoritmo.

Prendendo in prestito idee da Python

Possiamo prendere in prestito l'idea di Python di confrontare sia le chiavi che gli hash di ciascuna voce con il nostro oggetto di ingresso (sostituendo il metodo precedente):

La nostra tabella hash non ha ancora alcuna gestione delle collisioni: implementiamola! Come abbiamo visto in precedenza, Python lo fa confrontando le voci e quindi cambiando la maschera dei bit, ma lo faremo utilizzando un metodo chiamato sondaggio lineare (che è una forma di indirizzamento aperto, spiegato sopra):

Quando la funzione hash provoca una collisione mappando una nuova chiave a una cella della tabella hash che è già occupata da un'altra chiave, il sondaggio lineare cerca nella tabella la posizione libera successiva più vicina e vi inserisce la nuova chiave.

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