¿Por qué Python usa la tabla hash para implementar dict, pero no Red-Black Tree? [cerrado]

¿Por qué Python usa la tabla hash para implementar dict, pero no Red-Black Tree?

Cual es la clave ¿Actuación?

Esta es una respuesta general, no específica de Python.

Comparación de complejidad algorítmica

       | Hash Table  |   Red-Black Tree    |
-------+-------------+---------------------+
Space  | O(n) : O(n) | O(n)     : O(n)     |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch  | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
       | avg  :worst | average  : worst    |

El problema con las tablas hash es que los hash pueden colisionar. Existen varios mecanismos para resolver colisiones, por ejemplo, direccionamiento abierto o encadenamiento separado. El peor de los casos es que todas las claves tienen el mismo código hash, en cuyo caso una tabla hash se degradará en una lista vinculada.

En todos los demás casos, una tabla hash es una gran estructura de datos que es fácil de implementar y ofrece un buen rendimiento. Una desventaja es que las implementaciones que pueden hacer crecer rápidamente la tabla y redistribuir sus entradas probablemente desperdiciarán casi tanta memoria como la que realmente se está utilizando.

Los árboles RB se autoequilibran y no cambian su complejidad algorítmica en el peor de los casos. Sin embargo, son más difíciles de implementar. Sus complejidades promedio también son peores que las de una tabla hash.

Restricciones sobre llaves

Todas las claves en una tabla hash deben ser hashables y comparables para la igualdad entre ellas. Esto es especialmente fácil para cadenas o enteros, pero también es bastante sencillo de extender a tipos definidos por el usuario. En algunos lenguajes como Java, estas propiedades están garantizadas por definición.

Las claves en un árbol RB deben tener un orden total: cada clave debe ser comparable con cualquier otra clave, y las dos claves deben ser más pequeñas, mayores o iguales. Esta igualdad de orden debe ser equivalente a la igualdad semántica. Esto es sencillo para los números enteros y otros números, también es bastante fácil para las cadenas (el orden solo necesita ser consistente y no observable externamente, por lo que el orden no necesita considerar las configuraciones regionales ^[1] ), pero es difícil para otros tipos que no tienen un orden inherente . Es absolutamente imposible tener claves de diferentes tipos a menos que sea posible alguna comparación entre ellas.

^{[1]: En realidad, estoy equivocado aquí. Es posible que dos cadenas no sean iguales en bytes, pero aún así sean equivalentes según las reglas de algún idioma. Vea, por ejemplo, normalizaciones Unicode para un ejemplo en el que dos cadenas iguales se codifican de manera diferente. Si la composición de caracteres Unicode es importante para su clave hash es algo que la implementación de una tabla hash no puede saber.}

Uno podría pensar que una solución barata para las claves de RB-Tree sería probar primero la igualdad, luego comparar la identidad (es decir, comparar punteros). Sin embargo, este orden no sería transitivo: si a == by id(a) > id(c), entonces debe seguir eso id(b) > id(c)también, lo cual no está garantizado aquí. Entonces, en su lugar, podríamos usar el código hash de claves como claves de búsqueda. Aquí, el orden funciona correctamente, pero podríamos terminar con varias claves distintas con el mismo código hash, que se asignarán al mismo nodo en el árbol RB. Para resolver estas colisiones hash, podemos usar el encadenamiento separado al igual que con las tablas hash, pero esto también hereda el peor comportamiento de las tablas hash, el peor de ambos mundos.

Otros aspectos

• Espero que una tabla hash tenga una mejor localidad de memoria que un árbol, porque una tabla hash es esencialmente solo una matriz.

• Las entradas en ambas estructuras de datos tienen una sobrecarga bastante alta:

  • tabla hash: clave, valor y siguiente puntero de entrada en el caso de encadenamiento separado. También almacenar el código hash puede acelerar el cambio de tamaño.
  • Árbol RB: clave, valor, color, puntero secundario izquierdo, puntero secundario derecho. Tenga en cuenta que si bien el color es un solo bit, los problemas de alineación podrían significar que aún estaría desperdiciando suficiente espacio para casi un puntero completo, o incluso casi cuatro punteros cuando solo se pueden asignar bloques de memoria de potencia de dos tamaños. En cualquier caso, una entrada de árbol RB consume más memoria que una entrada de tabla hash.

• Las inserciones y eliminaciones en un árbol RB implican rotaciones de árbol. Estos no son realmente costosos, pero implican una sobrecarga. En un hash, la inserción y eliminación no son más caras que un simple acceso (aunque cambiar el tamaño de una tabla hash tras la inserción es un O(n)esfuerzo).

• Las tablas hash son inherentemente mutables, mientras que un árbol RB también podría implementarse de manera inmutable. Sin embargo, esto rara vez es útil.

Hay toda una serie de razones que pueden ser ciertas, pero es probable que las principales sean:

• Las tablas hash son más fáciles de implementar que los árboles. Ninguno de los dos es completamente trivial, pero las tablas hash son un poco más fáciles, y el impacto en el dominio de las claves legales es menos estricto, ya que solo necesita una función hash y una función de igualdad; los árboles requieren una función de orden total, y eso es mucho más difícil de escribir.
• Las tablas hash (mayo) tienen un mejor rendimiento en tamaños pequeños. Esto es muy importante porque una fracción significativa del trabajo solo trata teóricamente con grandes conjuntos de datos; en la práctica, mucho realmente funciona con solo decenas o cientos de teclas, no millones. El rendimiento a pequeña escala es muy importante y no se puede utilizar el análisis asintótico para descubrir qué es lo mejor allí; tienes que implementar y medir realmente.

¿Es más fácil de escribir / mantener y un ganador de rendimiento en casos de uso típicos? ¡Inscríbeme, por favor!