Por Alberto Fernández Valiente
Estructura de datos que almacena asociaciones entre pares clave-valor, sin repeticiones de claves. Permite realizar operaciones de inserción, eliminación y consulta de valores pasando como párametro su clave. Respecto a otras estructuras de datos, estas operaciones tienen O(1).
Una tabla con columnas clave y valor, donde la clave tiene que ser de tipo inmutable. En Python, el tamaño inicial de la tabla es 8 filas.
| Indice | Hash | Clave | Valor |
|---|---|---|---|
| 000 | |||
| 001 | |||
| 010 | |||
| 011 | ...10101011 | b | 2 |
| 100 | ...10001100 | c | 3 |
| 101 | ...11000101 | a | 1 |
| 110 | |||
| 111 |
En el 29c3 de 2011 se presentó un ataque contra los algoritmos de hash en varias plataformas web. Inicialmente se añade una semilla aleatoria, pero en Python 3.4 se reemplaza el algoritmo porque seguía siendo inseguro.
Para detectar una colisión hay que comprobar que las claves son distintas. La comparación directa puede ser muy costosa, así que utilizamos salidas anticipadas.
def check(a, b):
if a is b: return True
if a.hash == b.hash: return False
return a == b
En Python 3.3 se modificó el comportamiento de los diccionarios para optimizar el funcionamiento de las clases. Se separan las claves de los valores y así el diccionario de atributos solo guarda una copia de los mismos. Para aprovecharlo debemos inicializar todos los atributos dentro del __init__ de la clase.
| Indice | Hash | Clave | Objeto 1 | Objeto 2 |
|---|---|---|---|---|
| 000 | ||||
| 001 | ||||
| 010 | ||||
| 011 | ...10101011 | b | 2 | 5 |
| 100 | ...10001100 | c | 3 | 6 |
| 101 | ...11000101 | a | 1 | 4 |
| 110 | ||||
| 111 |
Dentro del núcleo de Python se realizan muchas búsquedas sobre diccionarios que son repetidas constantemente aunque éstos no hayan sido modificados.
En Python 3.6 se ha añadido un número privado de versión que solo se actualiza cuando es modificado. Esto permite realizar optimizaciones en tiempo de ejecución si éste no ha cambiado.
La idea surgió en 2012 y no fue implementada en PyPy hasta 2015. En Junio de 2016 Inada Naoki abre la issue 27350, en Septiembre durante un sprint de los desarrolladores Core deciden añadirlo a la versión 3.6.
Se añade un array de índices y se sustituye la tabla por una lista de elementos que crece cuando se añaden pares clave-valor. Esto permite que las claves queden ordenadas según su inserción.
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 2 | 3 | 1 | 0 | 0 |
| Indice | Hash | Clave | Valor |
|---|---|---|---|
| 1 | ...11000101 | a | 1 |
| 2 | ...10101011 | b | 2 |
| 3 | ...10001100 | c | 3 |