Tablas hash v árboles de búsqueda de autoequilibrado

Question

Tengo curiosidad por saber cuál es el razonamiento que podría sopesar el uso de una técnica de árbol de autoequilibrado para almacenar elementos que utilizando una tabla hash.

Veo que las tablas hash no pueden mantener el orden de inserción, pero siempre pude usar una lista vinculada en la parte superior para almacenar la secuencia de orden de inserción.

Veo que para un número pequeño de valores, hay un costo adicional de la función hash, pero siempre puedo guardar la función hash junto con la clave para búsquedas más rápidas.

entiendo que las tablas hash son difíciles de implementar que la aplicación recta de avance de un árbol rojo-negro, pero en una implementación práctica no sería uno estar dispuesto a ir un poco más allá de la molestia?

Veo que con las tablas hash es normal que se produzcan colisiones, pero con técnicas de direccionamiento abierto como el doble hash que permiten guardar las claves en la tabla hash, el problema no se ha reducido al efecto de ¿No inclinar el favor hacia los árboles negros rojos para tales implementaciones?

Tengo curiosidad si me falta una desventaja estricta de la tabla hash que todavía hace que los árboles negros rojos sean una estructura de datos bastante viable en aplicaciones prácticas (como sistemas de archivos, etc.).

Answer 1

Esto es lo que ocurre:

1. Hay tipos de datos que no pueden ser hash (o es demasiado cara para discutir a fondo), por lo tanto, no se puede almacenar en tablas hash.
2. árboles guardan los datos en el orden que necesita (clasificados), y no de orden de inserción. No puede (efectivamente) hacer eso con la tabla hash, incluso si ejecuta una lista vinculada a través de ella.
3. Los árboles tienen una mejor performace peor de los casos

Answer 2

En mi humilde opinión, los árboles que se equilibran a sí mismos funcionan bastante bien como temas académicos. E I no sé nada que pueda calificarse como "implementación directa de un árbol rojo-negro ".

En la vida real, la pared de memoria los hace mucho menos eficientes que en papel.

Con esto en mente, tablas hash son alternativas decentes, especialmente si usted no practica ellos el estilo académico (olvidarse de la restricción de tamaño de la tabla y que mágicamente resolver cambiar el tamaño de la tabla de emisión y casi todos los problemas de colisión).

En una palabra: que sea sencillo. Si eso es simple para usted, entonces es simple para su computadora.

Answer 3

asignación de almacenamiento es otra consideración. Cada vez que llena todos los cubos en una tabla hash, necesita asignar nuevo almacenamiento y volver a manipular todo. Esto puede evitarse si conoce el tamaño de los datos con anticipación. Por otro lado, los árboles equilibrados no sufren este problema en absoluto.

Answer 4

sólo quería añadir:

• árboles binarios equilibrados tienen un tiempo previsible de ir a buscar un conjunto de datos [log n] independiente del tipo de datos.Muchas veces puede ser importante para su aplicación estimar los tiempos de respuesta para su aplicación. [las tablas hash pueden tener tiempos de respuesta impredecibles]. Recuerde que para n menores, como en los casos de uso más comunes, la diferencia de rendimiento en una búsqueda en memoria difícilmente va a importar y el cuello de la botella del sistema estará en otro lugar y, a veces, solo desea hacer que el sistema sea mucho más simple. depurar y analizar

• Los árboles son generalmente más eficiente de la memoria en comparación con tablas hash y mucho más sencillo de implementar sin ningún análisis de la distribución de claves de entrada y posibles colisiones, etc.

Answer 5

Creo que si se desea consultar para una rango de claves en lugar de una clave, la estructura de árbol auto equilibrada tendrá un mejor rendimiento que una estructura de tabla hash.