¿Cómo se implementan los diccionarios incorporados de Python?

¿Alguien sabe cómo se implementa el tipo de diccionario incorporado para python? Tengo entendido que es una especie de tabla hash, pero no he podido encontrar ningún tipo de respuesta definitiva.

Aquí está todo sobre los dictados de Python que pude reunir (probablemente más de lo que a nadie le gustaría saber, pero la respuesta es exhaustiva).

• Los diccionarios de Python se implementan como tablas hash .
• Las tablas hash deben permitir colisiones hash, es decir, incluso si dos claves distintas tienen el mismo valor hash, la implementación de la tabla debe tener una estrategia para insertar y recuperar los pares clave y valor sin ambigüedades.
• Python dictusa direccionamiento abierto para resolver colisiones de hash (explicado a continuación) (ver dictobject.c: 296-297 ).
• La tabla hash de Python es solo un bloque contiguo de memoria (algo así como una matriz, por lo que puede hacer una O(1)búsqueda por índice).
• Cada ranura en la tabla puede almacenar una y solo una entrada. Esto es importante.
• Cada entrada en la tabla en realidad es una combinación de los tres valores: <hash, clave, valor> . Esto se implementa como una estructura C (ver dictobject.h: 51-56 ).

• La siguiente figura es una representación lógica de una tabla hash de Python. En la figura a continuación, 0, 1, ..., i, ...a la izquierda hay índices de las ranuras en la tabla hash (son solo para fines ilustrativos y, obviamente, no se almacenan junto con la tabla).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• Cuando se inicializa un nuevo dict comienza con 8 ranuras . (ver dictobject.h: 49 )

• Al agregar entradas a la tabla, comenzamos con un espacio i, que se basa en el hash de la clave. CPython utiliza inicialmente i = hash(key) & mask(donde mask = PyDictMINSIZE - 1, pero eso no es realmente importante). Solo tenga en cuenta que la ranura inicial i, que está marcada, depende del hash de la clave.
• Si esa ranura está vacía, la entrada se agrega a la ranura (por entrada, quiero decir, <hash|key|value>). ¿Pero qué pasa si ese espacio está ocupado? Lo más probable es que otra entrada tenga el mismo hash (¡colisión de hash!)
• Si la ranura está ocupada, CPython (e incluso PyPy) compara el hash Y la clave (por comparación quiero decir ==comparación no la iscomparación) de la entrada en la ranura con el hash y la clave de la entrada actual que se va a insertar ( dictobject.c : 337,344-345 ) respectivamente. Si ambos coinciden, entonces cree que la entrada ya existe, se da por vencida y pasa a la siguiente entrada que se insertará. Si el hash o la clave no coinciden, comienza a sondear .
• El sondeo solo significa que busca las ranuras por ranura para encontrar una ranura vacía. Técnicamente, podríamos ir uno por uno i+1, i+2, ...y usar el primero disponible (eso es sondeo lineal). Pero por razones explicadas maravillosamente en los comentarios (ver dictobject.c: 33-126 ), CPython usa sondeo aleatorio . En el sondeo aleatorio, el siguiente espacio se elige en un orden pseudoaleatorio. La entrada se agrega a la primera ranura vacía. Para esta discusión, el algoritmo real utilizado para elegir el siguiente espacio no es realmente importante (ver dictobject.c: 33-126 para el algoritmo de sondeo). Lo importante es que las ranuras se analicen hasta que se encuentre la primera ranura vacía.
• Lo mismo sucede con las búsquedas, solo comienza con la ranura inicial i (donde depende del hash de la clave). Si el hash y la clave no coinciden con la entrada en la ranura, comienza a sondear, hasta que encuentra una ranura con una coincidencia. Si todas las ranuras están agotadas, informa un error.
• Por cierto, dictse cambiará el tamaño si está dos tercios lleno. Esto evita ralentizar las búsquedas. (ver dictobject.h: 64-65 )

NOTA: Investigué sobre la implementación de Python Dict en respuesta a mi propia pregunta sobre cómo varias entradas en un dict pueden tener los mismos valores hash. Publiqué una versión ligeramente editada de la respuesta aquí porque toda la investigación también es muy relevante para esta pregunta.

¿Cómo se implementan los diccionarios incorporados de Python?

Aquí está el curso corto:

• Son tablas hash. (Consulte a continuación los detalles de la implementación de Python).
• Un nuevo diseño y algoritmo, a partir de Python 3.6, los hace
  • ordenado por inserción de clave, y
  • ocupa menos espacio,
  • prácticamente sin costo en rendimiento.
• Otra optimización ahorra espacio cuando los dictos comparten claves (en casos especiales).

El aspecto ordenado no es oficial a partir de Python 3.6 (para dar a otras implementaciones la oportunidad de mantenerse al día), pero oficial en Python 3.7 .

Los diccionarios de Python son tablas de hash

Durante mucho tiempo, funcionó exactamente así. Python preasignaría 8 filas vacías y usaría el hash para determinar dónde pegar el par clave-valor. Por ejemplo, si el hash para la clave terminó en 001, lo pegaría en el índice 1 (es decir, el segundo) (como en el ejemplo a continuación).

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Cada fila ocupa 24 bytes en una arquitectura de 64 bits, 12 en una de 32 bits. (Tenga en cuenta que los encabezados de columna son solo etiquetas para nuestros propósitos aquí; en realidad no existen en la memoria).

Si el hash terminó igual que el hash de una clave preexistente, esto es una colisión, y luego pegaría el par clave-valor en una ubicación diferente.

Después de almacenar 5 valores clave, al agregar otro par clave-valor, la probabilidad de colisiones hash es demasiado grande, por lo que el diccionario duplica su tamaño. En un proceso de 64 bits, antes del cambio de tamaño, tenemos 72 bytes vacíos, y después, estamos desperdiciando 240 bytes debido a las 10 filas vacías.

Esto ocupa mucho espacio, pero el tiempo de búsqueda es bastante constante. El algoritmo de comparación de claves es calcular el hash, ir a la ubicación esperada, comparar la identificación de la clave; si son el mismo objeto, son iguales. Si no, entonces comparar los valores hash, si son no lo mismo, no son iguales. De lo contrario, finalmente comparamos las claves para la igualdad y, si son iguales, devolvemos el valor. La comparación final para la igualdad puede ser bastante lenta, pero las comprobaciones anteriores generalmente reducen la comparación final, lo que hace que las búsquedas sean muy rápidas.

Las colisiones ralentizan las cosas, y un atacante podría usar teóricamente colisiones hash para realizar un ataque de denegación de servicio, por lo que aleatorizamos la inicialización de la función hash de modo que calcule diferentes hash para cada nuevo proceso de Python.

El espacio desaprovechado descrito anteriormente nos ha llevado a modificar la implementación de los diccionarios, con una nueva y emocionante característica que los diccionarios ahora están ordenados por inserción.

Las nuevas tablas de hash compactas

Comenzamos, en cambio, preasignando una matriz para el índice de la inserción.

Como nuestro primer par clave-valor va en la segunda ranura, indexamos así:

[null, 0, null, null, null, null, null, null]

Y nuestra tabla solo se llena por orden de inserción:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

Entonces, cuando buscamos una clave, usamos el hash para verificar la posición que esperamos (en este caso, vamos directamente al índice 1 de la matriz), luego vamos a ese índice en la tabla hash (por ejemplo, índice 0 ), compruebe que las claves son iguales (utilizando el mismo algoritmo descrito anteriormente) y, de ser así, devuelva el valor.

Mantenemos un tiempo de búsqueda constante, con pérdidas de velocidad menores en algunos casos y ganancias en otros, con las ventajas de que ahorramos bastante espacio sobre la implementación preexistente y conservamos el orden de inserción. El único espacio desperdiciado son los bytes nulos en la matriz de índice.

Raymond Hettinger introdujo esto en python-dev en diciembre de 2012. Finalmente entró en CPython en Python 3.6 . Ordenar por inserción se consideró un detalle de implementación para 3.6 para permitir que otras implementaciones de Python tengan la oportunidad de ponerse al día.

Claves compartidas

Otra optimización para ahorrar espacio es una implementación que comparte claves. Por lo tanto, en lugar de tener diccionarios redundantes que ocupan todo ese espacio, tenemos diccionarios que reutilizan las claves compartidas y los hashes de las claves. Puedes pensarlo así:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

Para una máquina de 64 bits, esto podría ahorrar hasta 16 bytes por clave por diccionario adicional.

Claves compartidas para objetos personalizados y alternativas

Estos dictos de clave compartida están destinados a ser utilizados para objetos personalizados ' __dict__. Para obtener este comportamiento, creo que debe terminar de llenar su __dict__antes de crear una instancia de su próximo objeto ( consulte PEP 412 ). Esto significa que debe asignar todos sus atributos en __init__o __new__, de lo contrario, es posible que no obtenga sus ahorros de espacio.

Sin embargo, si conoce todos sus atributos en el momento en que __init__se ejecuta, también podría proporcionar __slots__su objeto y garantizar que __dict__no se crea en absoluto (si no está disponible en los padres), o incluso permitir __dict__pero garantizar que sus atributos previstos sean almacenado en ranuras de todos modos. Para más información __slots__, mira mi respuesta aquí .

Ver también:

• PEP 509 - Agregue una versión privada para dictar
• PEP 468 : preservar el orden de **kwargsuna función.
• PEP 520 - Preservar orden de definición de atributo de clase
• PyCon 2010: The Might Dictionary - Brandon Rhodes
• PyCon 2017: el diccionario aún más poderoso - Brandon Rhodes
• PyCon 2017: Modern Python Dictionaries Una confluencia de una docena de grandes ideas - Raymond Hettinger
• dictobject.c - Implementación real dict de CPython en C.

Los diccionarios de Python usan direccionamiento abierto ( referencia dentro del código hermoso )

¡NÓTESE BIEN! El direccionamiento abierto , también conocido como hashing cerrado , no debe confundirse, como se señaló en Wikipedia, con su hashing abierto opuesto .

El direccionamiento abierto significa que el dict usa ranuras de matriz, y cuando la posición primaria de un objeto se toma en la dict, se busca el lugar del objeto en un índice diferente en la misma matriz, usando un esquema de "perturbación", donde el valor hash del objeto juega un papel importante. .