¿Cómo se implementan los diccionarios integrados de Python?
¿Alguien sabe cómo se implementa el tipo de diccionario integrado para Python? Tengo entendido que se trata de una especie de tabla hash, pero no he podido encontrar ningún tipo de respuesta definitiva.
Editar:
Esta respuesta es para versiones de Python anteriores a la 3.6. Para Python 3.6 y posteriores, consulte la respuesta de Rusia-debe-eliminar-putin a continuación.
Original:
Aquí está todo lo que pude reunir sobre los dictados de Python (probablemente más de lo que a nadie le gustaría saber; pero la respuesta es completa).
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 hash (que se explican a continuación) (consulte 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 realizar una
O(1)búsqueda por índice).Cada espacio de la tabla puede almacenar una y sólo una entrada. Esto es importante.
Cada entrada de la tabla es en realidad una combinación de los tres valores: <hash, clave, valor> . Esto se implementa como una estructura C (consulte dictobject.h:51-56 ).
La siguiente figura es una representación lógica de una tabla hash de Python. En la siguiente figura,
0, 1, ..., i, ...a la izquierda están los í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 espacios . (ver dictobject.h:49 )
Al agregar entradas a la tabla, comenzamos con alguna ranura,
ique se basa en el hash de la clave. CPython usa inicialmentei = hash(key) & mask(dóndemask = PyDictMINSIZE - 1, pero eso no es realmente importante). Solo tenga en cuenta que la ranura inicialique se marca depende del hash de la clave.Si ese espacio está vacío, la entrada se agrega al espacio (por entrada, quiero decir
<hash|key|value>). ¿Pero qué pasa si ese espacio está ocupado? Lo más probable es que se deba a que otra entrada tiene el mismo hash (¡colisión de hash!)Si la ranura está ocupada, CPython (e incluso PyPy) compara el hash Y la clave (por comparar me refiero
==a comparación, no aiscomparación) de la entrada en la ranura con el hash y la clave de la entrada actual que se insertará ( dictobject.c :337,344-345 ) respectivamente. Si ambos coinciden, entonces piensa que la entrada ya existe, se da por vencido y pasa a la siguiente entrada que se insertará. Si el hash o la clave no coinciden, comienza a sondear .Sondear simplemente significa que busca ranura 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 (es decir, sondeo lineal). Pero por razones explicadas maravillosamente en los comentarios (ver dictobject.c:33-126 ), CPython usa sondeo aleatorio . En el sondeo aleatorio, la siguiente ranura se elige en un orden pseudoaleatorio. La entrada se agrega al primer espacio vacío. Para esta discusión, el algoritmo real utilizado para elegir la siguiente ranura no es realmente importante (consulte dictobject.c:33-126 para conocer el algoritmo de sondeo). Lo importante es sondear las ranuras hasta encontrar la primera ranura vacía.Lo mismo sucede con las búsquedas, simplemente comienza con la ranura inicial i (donde i 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 que coincida. Si se agotan todas las ranuras, informa un error.
Por cierto,
dictse cambiará de tamaño si está lleno en dos tercios. 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 integrados 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 llave, y
- ocupa menos espacio,
- prácticamente sin costo en rendimiento.
- Otra optimización ahorra espacio cuando los dictados 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 es oficial en Python 3.7 .
Los diccionarios de Python son tablas hash
Durante mucho tiempo funcionó exactamente así. Python preasignará 8 filas vacías y usará el hash para determinar dónde colocar el par clave-valor. Por ejemplo, si el hash de la clave termina en 001, lo colocará en el índice 1 (es decir, 2º) (como en el ejemplo siguiente).
<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 las columnas son solo etiquetas para nuestros propósitos aquí; en realidad no existen en la memoria).
Si el hash termina igual que el hash de una clave preexistente, esto es una colisión y luego colocarí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 tamaño del diccionario se duplica. 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 requiere mucho espacio, pero el tiempo de búsqueda es bastante constante. El algoritmo de comparación de claves consiste en 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 es así, compare los valores hash; si no son iguales, no son iguales. De lo contrario, finalmente comparamos las claves para determinar la igualdad y, si son iguales, devolvemos el valor. La comparación final de igualdad puede ser bastante lenta, pero las comprobaciones anteriores suelen acortar la comparación final, lo que hace que las búsquedas sean muy rápidas.
Las colisiones ralentizan las cosas y, en teoría, un atacante podría usar colisiones de 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 hashes para cada nuevo proceso de Python.
El espacio desperdiciado descrito anteriormente nos ha llevado a modificar la implementación de los diccionarios, con una nueva característica interesante: los diccionarios ahora se ordenan por inserción.
Las nuevas tablas hash compactas
En cambio, comenzamos preasignando una matriz para el índice de inserción.
Dado que nuestro primer par clave-valor va en el segundo espacio, indexamos así:
[null, 0, null, null, null, null, null, null]
Y nuestra tabla simplemente se completa 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 ), verifique que las claves sean iguales (usando el mismo algoritmo descrito anteriormente) y, de ser así, devuelva el valor.
Mantenemos un tiempo de búsqueda constante, con pérdidas menores de velocidad en algunos casos y ganancias en otros, con la ventaja de que ahorramos bastante espacio con respecto a 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 llegó a CPython en Python 3.6 . El orden por inserción se consideró un detalle de implementación para 3.6 para permitir que otras implementaciones de Python tuvieran la oportunidad de ponerse al día.
Claves compartidas
Otra optimización para ahorrar espacio es una implementación que comparte claves. Así, 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 pensar en ello 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 dictados de clave compartida están pensados para usarse con objetos personalizados __dict__. Para obtener este comportamiento, creo que debes terminar de completar __dict__antes de crear una instancia de tu próximo objeto ( ver PEP 412 ). Esto significa que debe asignar todos sus atributos en o __init__; __new__de lo contrario, es posible que no ahorre espacio.
Sin embargo, si conoce todos sus atributos en el momento de su __init__ejecución, también puede proporcionar __slots__su objeto y garantizar que __dict__no se cree 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 obtener más información __slots__, consulte mi respuesta aquí .
Ver también:
- PEP 509 : agregar una versión privada para dictar
- PEP 468 - Preservar el orden de
**kwargsen una función. - PEP 520 - Preservación del orden de definición de atributos de clase
- PyCon 2010: Diccionario Might - Brandon Rhodes
- PyCon 2017: El diccionario aún más poderoso - Brandon Rhodes
- PyCon 2017: Diccionarios modernos de Python Una confluencia de una docena de grandes ideas - Raymond Hettinger
- dictobject.c : implementación real de dict de CPython en C.
Los diccionarios de Python utilizan direccionamiento abierto ( referencia dentro del código Beautiful )
¡NÓTESE BIEN! El direccionamiento abierto , también conocido como hash cerrado , como se indica en Wikipedia, no debe confundirse con su opuesto hash abierto.
El direccionamiento abierto significa que el dict utiliza ranuras de matriz, y cuando se toma la posición principal de un objeto en el dict, el lugar del objeto se busca en un índice diferente en la misma matriz, utilizando un esquema de "perturbación", donde el valor hash del objeto juega un papel importante. .
Python dict mantiene dos índices ahora. Uno es una matriz escasa. Esto es lo que hace cuando se inserta el primer elemento en dict:
- insertar valor clave
- dict encuentra hash de clave
- dict asigna hash a un índice
- en la matriz dispersa, se ubica este índice y se ingresa el número cero (la primera vez que ingresa).
La segunda matriz es una matriz densa. Esto es lo que pasa allí: - En índice cero, ingrese el valor.
Así, la segunda matriz es compacta y eficiente en memoria.
Para inserciones posteriores, se incrementa el índice de inserción de la segunda matriz. De esta manera se ahorra memoria y se mantiene el orden de inserción.
Pueden ocurrir colusiones de hash al insertar un índice en la primera matriz dispersa. Esto se soluciona mediante un sondeo pseudoaleatorio, es decir, algo que busca más adelante dentro de la matriz en busca de espacios vacíos de una manera predecible pero pseudoaleatoria.
La segunda matriz es siempre compacta.
