¿Cómo Python dict almacena clave, valor cuando se produce la colisión?

¿Cómo almacena Python la clave dict, los valores cuando se produce una colisión en la tabla hash? ¿Cuál es el algoritmo hash utilizado para obtener el valor hash aquí?

Para el “normal” Python, esta gran reseña de Praveen Gollakota lo explica muy bien, aquí están los puntos importantes:

  • Los diccionarios de Python se implementan como tablas hash. Las tablas hash constan de ranuras y las claves se asignan a las ranuras mediante una función de hashing.
  • Las implementaciones de tablas de hash deben permitir colisiones de hash, es decir, incluso si dos claves tienen el mismo valor de hash, la implementación de la tabla debe tener una estrategia para insertar y recuperar los pares de clave y valor de forma inequívoca.
  • El dict de Python usa direccionamiento abierto para resolver las colisiones de hash (ver dictobject.c : 296-297).
  • En el direccionamiento abierto, las colisiones de hash se resuelven mediante sondeo (se explica a continuación).
  • La tabla hash es solo un bloque de memoria contiguo (como una matriz, por lo que puede hacer O(1) búsqueda O(1) por índice).
  • Cada ranura en la tabla hash puede almacenar una y solo una entrada. Esto es importante.
  • Cada entrada en la tabla en realidad es una combinación de los tres elementos – . Esto se implementa como una estructura en C (ver dictobject.h : 51-56).
  • Cuando se inicializa un nuevo dictado, comienza con 8 ranuras. (ver dictobject.h : 49)
  • Al agregar entradas a la tabla, comenzamos con alguna ranura, i que se basa en el hash de la clave. CPython usa inicial i = hash(key) & mask , donde mask = PyDictMINSIZE - 1 , pero eso no es realmente importante. Solo tenga en cuenta que la ranura inicial, i , que se comprueba depende del hash de la clave.
  • Si esa ranura está vacía, la entrada se agrega a la ranura (por entrada, quiero decir, ). Pero, ¿y si esa ranura está ocupada? 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 comparación) de la entrada en la ranura con la clave de la entrada actual que se insertará ( dictobject. c 337,344-345). Si ambos coinciden, 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, se inicia el sondeo.
  • Sondeo simplemente 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 (es decir, sondeo lineal). Pero por razones explicadas a la perfección en los comentarios (ver dictobject.c : 33-126), CPython usa sondeo aleatorio. En el sondeo aleatorio, la siguiente ranura se selecciona en un orden pseudoaleatorio. La entrada se agrega a la primera ranura vacía. Para esta discusión, el algoritmo real utilizado para elegir la siguiente ranura no es realmente importante (consulte dictobject.c : 33-126 para el algoritmo de sondeo). Lo que es importante es que las ranuras sondadas hasta que se encuentre la primera ranura vacía.
  • Lo mismo ocurre 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.
  • Para evitar ralentizar las búsquedas, el dictamen cambiará de tamaño cuando esté lleno a dos tercios (consulte dictobject.h : 64-65).

La versión corta: la especificación de Python no especifica una implementación de diccionario, pero CPython utiliza un mapa hash y maneja las colisiones con direccionamiento abierto.

Vea esta respuesta a una pregunta similar y también la página de Wikipedia sobre tablas hash .