Implementación de diccionario de Python 3.6 usando tablas hash

Dictionary en Python es una colección de valores de datos, que se utiliza para almacenar valores de datos como un mapa que, a diferencia de otros tipos de datos que contienen solo un valor como elemento, Dictionary contiene un par clave: valor. El valor-clave se proporciona en el diccionario para hacerlo más optimizado. Cada par clave-valor en un Diccionario está separado por dos puntos:, mientras que cada clave está separada por una ‘coma’. Para saber más sobre los diccionarios haga clic aquí . 

Según una propuesta de Raymond Hettinger, la nueva función dict() tiene entre un 20 % y un 25 % menos de uso de memoria en comparación con Python v.3.5 o menos. Se basa en la semántica de preservación del orden propuesta por Raymond Hettinger. Esta implementación hace que los diccionarios sean más compactos y proporciona una iteración más rápida sobre ellos. 

El diseño de la memoria de los diccionarios en versiones anteriores era innecesariamente ineficiente. Se componía de una tabla dispersa de entradas de 24 bytes que almacenaban el valor hash, el puntero clave y el puntero de valor. El diseño de memoria de los diccionarios en la versión 3.5 y anteriores se implementó para almacenar en una sola tabla dispersa. 

Ejemplo: 

for the below dictionary:

d = {'banana':'yellow', 'grapes':'green', 'apple':'red'}

used to store as:

    entries = [['--', '--', '--'],
               [-5850766811922200084, 'grapes', 'green'],
               ['--', '--', '--'],
               ['--', '--', '--'],
               ['--', '--', '--'],
               [2247849978273412954, 'banana', 'yellow'],
               ['--', '--', '--'],
               [-2069363430498323624, 'apple', 'red']]

En cambio, en la nueva implementación de dict(), los datos ahora se organizan en una tabla densa referenciada por una tabla dispersa de índices de la siguiente manera: 

 indices  = [None, 1, None, None, None, 0, None, 2]
 entries = [[2247849978273412954, 'banana', 'yellow']
             [-5850766811922200084, 'grapes', 'green'],
             [-2069363430498323624, 'apple', 'red']]

Es importante notar que en la nueva implementación de dict() solo se ha cambiado el diseño de los datos y no se realizan cambios en los algoritmos de la tabla hash. No se han cambiado las estadísticas de colisión ni el orden de búsqueda de la tabla. 

Se cree que esta nueva implementación de dict() comprime significativamente los diccionarios para ahorrar memoria dependiendo del tamaño del diccionario. Los diccionarios pequeños obtienen el mayor beneficio de esto. 

Para una tabla dispersa de tamaño t con n entradas, los tamaños son: 

curr_size = 24 * t
new_size = 24 * n + sizeof(index) * t

En el ejemplo anterior banana/grapes/apple, el tamaño de la implementación anterior es de 192 bytes (ocho entradas de 24 bytes) y la implementación posterior tiene un tamaño de 90 bytes (tres entradas de 24 bytes y ocho índices de 1 byte). Eso muestra alrededor del 58% de compresión en el tamaño del diccionario. 

Además de ahorrar memoria, el nuevo diseño de memoria hace que la iteración sea más rápida. Ahora, funciones como Keys(), items() y valores pueden recorrer la tabla densa sin tener que omitir espacios vacíos, a diferencia de la implementación anterior. Otros beneficios de esta nueva implementación son una mejor utilización de la memoria caché, un cambio de tamaño más rápido y menos toques en la memoria.