Mejore sus habilidades en Python: Examinando el diccionario

una tabla hash (mapa hash) es una estructura de datos que implementa un tipo de datos abstracto de matriz asociativa, una estructura que puede asignar claves a valores.

Si huele a Python dict, se siente como un dicty se parece a uno ... bueno, debe ser un dict. ¡Absolutamente! Oh, y settambién ...

¿Eh?

Los diccionarios y conjuntos en Python se implementan mediante una tabla hash. Puede parecer abrumador al principio, pero a medida que investiguemos más, todo debería quedar claro.

Objetivo

A lo largo de este artículo, descubriremos cómo dictse implementa a en Python y crearemos nuestra propia implementación de (una simple). El artículo se divide en tres partes y la construcción de nuestro diccionario personalizado se lleva a cabo en las dos primeras:

  1. Comprender qué son las tablas hash y cómo usarlas
  2. Profundizar en el código fuente de Python para comprender mejor cómo se implementan los diccionarios
  3. Explorar las diferencias entre el diccionario y otras estructuras de datos como listas y conjuntos

¿Qué es una tabla hash?

Una tabla hash es una estructura que está diseñada para almacenar una lista de pares clave-valor, sin comprometer la velocidad y la eficiencia de manipular y buscar la estructura.

La efectividad de la tabla hash se deriva de la función hash , una función que calcula el índice del par clave-valor, lo que significa que podemos insertar, buscar y eliminar elementos rápidamente ya que conocemos su índice en la matriz de memoria.

La complejidad comienza cuando dos de nuestras claves tienen el mismo valor. Este escenario se llama colisión hash . Hay muchas formas diferentes de manejar una colisión, pero solo cubriremos la forma de Python. No profundizaremos demasiado en la explicación de nuestra tabla hash con el fin de mantener este artículo para principiantes y centrado en Python.

Asegurémonos de comprender el concepto de tablas hash antes de continuar. Comenzaremos creando los esqueletos para nuestra muy (muy) simple personalización que dictconsiste solo en métodos de inserción y búsqueda, utilizando algunos de los métodos más dunder de Python. Necesitaremos inicializar la tabla hash con una lista de un tamaño específico y habilitar la suscripción (signo []) para ella:

Ahora, nuestra lista de tablas hash debe contener estructuras específicas, cada una con una clave, un valor y un hash:

Ejemplo básico

Una pequeña empresa con 10 empleados desea mantener registros que contengan los días restantes por enfermedad de sus empleados. Podemos usar la siguiente función hash, para que todo pueda caber en la matriz de memoria:

length of the employee's name % TABLE_SIZE

Definamos nuestra función hash en la clase Entry:

Ahora podemos inicializar una matriz de 10 elementos en nuestra tabla:

¡Espere! Pensémoslo bien. Lo más probable es que abordemos algunas colisiones de hash. Si solo tenemos 10 elementos, será mucho más difícil para nosotros encontrar un espacio abierto después de una colisión. Decidamos que nuestra mesa tendrá el doble de tamaño: ¡20 elementos! Será útil en el futuro, lo prometo.

Para insertar rápidamente a cada empleado, seguiremos la lógica:

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

Entonces, nuestro método de inserción se verá así (sin manejo de colisión hash todavía):

Para la búsqueda, básicamente hacemos lo mismo:

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

¡Aún no hemos terminado!

Manejo de colisiones de Python

Python usa un método llamado Open Addressing para manejar colisiones. También cambia el tamaño de las tablas hash cuando alcanza cierto tamaño, pero no discutiremos ese aspecto. Definición de direccionamiento abierto de Wikipedia:

En otra estrategia, llamada direccionamiento abierto, todos los registros de entrada se almacenan en la propia matriz de cubos. Cuando se debe insertar una nueva entrada, se examinan los cubos, comenzando con la ranura con hash y siguiendo una secuencia de sondeo , hasta que se encuentra una ranura desocupada. Al buscar una entrada, los depósitos se escanean en la misma secuencia, hasta que se encuentra el registro de destino o se encuentra una ranura de matriz no utilizada, lo que indica que no existe tal clave en la tabla.

Examinemos el proceso de recuperación de un valor key, mirando el código fuente de Python (escrito en C):

  1. Calcular hash de key
  2. Calcule el valor indexdel elemento por hash & maskdónde mask = HASH_TABLE_SIZE-1(en términos simples, tome los últimos N bits de los bits hash):
i = (size_t)hash & mask;

3. Si está vacío, devuelva lo DKIX_EMPTYque se traduce finalmente en KeyError:

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

4. Si no está vacío, compare las claves y value_addrlos valores hash y configure la dirección con el valor real de la dirección si es igual:

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

y:

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

5. Si no es igual, use diferentes bits del hash (el algoritmo se explica aquí) y vaya al paso 3 nuevamente:

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

Aquí hay un diagrama para ilustrar todo el proceso:

El proceso de inserción es bastante similar: si la ranura encontrada está vacía, la entrada se está insertando, si no está vacía, comparamos la clave y el hash; si es igual, reemplazamos el valor, y si no, continuamos nuestra búsqueda de encontrar un nuevo lugar con el perturbalgoritmo.

Tomando prestadas ideas de Python

Podemos tomar prestada la idea de Python de comparar tanto las claves como los hash de cada entrada con nuestro objeto de entrada (reemplazando el método anterior):

Nuestra tabla hash todavía no tiene ningún manejo de colisiones, ¡implementemos uno! Como vimos anteriormente, Python lo hace comparando entradas y luego cambiando la máscara de los bits, pero lo haremos usando un método llamado sondeo lineal (que es una forma de direccionamiento abierto, explicado anteriormente):

Cuando la función hash provoca una colisión al asignar una nueva clave a una celda de la tabla hash que ya está ocupada por otra clave, el sondeo lineal busca en la tabla la siguiente ubicación libre más cercana e inserta la nueva clave allí.

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