HASH TABLES V Auto-balanceo de árboles

Question

Tengo curiosidad por saber cuál es el razonamiento que podría sobreviverse hacia el uso de una técnica de árbol de equilibrio para almacenar artículos que usar 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 pequeño número de valores, existe un costo adicional de la función hash, pero siempre pude guardar la función hash junto con la clave para buscas más rápidas.

Entiendo que las tablas de hash son difíciles de implementar que la implementación directa de un árbol negro rojo, pero en una implementación práctica ¿no estaría dispuesta a ir a un milla extra para el problema?

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

Tengo curiosidad si estoy perdiendo estrictamente una desventaja de la tabla de hash que aún hace que los árboles negros rojos sean una estructura de datos bastante viables en aplicaciones prácticas (como sistemas de archivos, etc.).

Answer 1

Aquí es lo que puedo pensar:

1. Hay tipos de datos que no pueden ser hash (o es demasiado caro para el hash), por lo tanto, no se pueden almacenar en tablas de hash.
2. Los árboles mantienen los datos en el orden que necesita (ordenado), no orden de inserción.No puede (efectivamente) hacerlo con la tabla Hash, incluso si ejecuta una lista vinculada a través de él.
3. Los árboles tienen una mejor actuación del peor de los casos

Answer 2

La asignación de almacenamiento es otra consideración.Cada vez que llena todos los cubos en una tabla de hash, necesitas asignar un nuevo almacenamiento y re-hash todo.Esto se puede evitar si conoce el tamaño de los datos con anticipación.Por otro lado, los árboles equilibrados no sufren de este problema.

Answer 3

En mi opinión humilde, los árboles de equilibrio de auto equalojas funcionan bastante bien como temas académicos.Y yo no sabe nada que pueda ser calificado como una implementación directa de una " Árbol rojo-negro ".

En el mundo real, la pared de memoria los hace mucho menos eficientes de lo que están en papel.

Con esto en mente, las tablas hash son alternativas decentes, especialmente si no practicas ellos el estilo académico (olvídate de la restricción de tamaño de la mesa y usted resuelve mágicamente La tabla cambia el tamaño del problema y casi todos los problemas de colisión).

En una palabra: manténgalo simple.Si eso es simple para usted, entonces es simple para su computadora.

Answer 4

Solo quería agregar:

• Los árboles binarios equilibrados tienen un tiempo predecible de recuperar un [log n] independiente del tipo de datos.Muchas veces, puede ser importante para su aplicación para estimar los tiempos de respuesta para su solicitud.[Las tablas hash pueden tener tiempos de respuesta impredecibles].Recuerde para los N más pequeños como en los casos de uso más comunes, la diferencia en el rendimiento en un aspecto en memoria apenas va a importar y el cuello de la botella del sistema va a estar en otra parte y, a veces, solo desea hacer que el sistema sea mucho más sencillo paradepurar y analizar.

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

Answer 5

Algunas razones por las que puedo pensar:

1. Los árboles son dinámicos (la complejidad del espacio es n), mientras que las tablas hash a menudo se implementan como matrices que son de tamaño fijo, lo que significa que a menudo se inicializarán con k tamaño, donde k> n, así que incluso si usted Solo tiene 1 elemento en un hashmap, es posible que todavía tenga 100 ranuras vacías que toman memoria. Otro efecto de esto es:

2. Aumentar el tamaño de una tabla hash a base de matriz es costoso (O (N) Tiempo promedio, O (n log n) peor caso), mientras que los árboles pueden crecer en un tiempo constante (O (1)) + (Tiempo para localizar el punto de inserción (O (log N))

3. Los elementos en un árbol se pueden recolectar en orden ordenado (usando EX: en orden. Traversal). Por lo tanto, a menudo obtienes una lista ordenada como un beneficio libre con árboles.
4. Los árboles pueden tener un mejor desempeño en el peor de los casos frente a un hashmap, dependiendo de cómo se implementa el hashmap (Ej: HashMap con encadenamiento tendrá el peor de los casos, mientras que los árboles autoalancados pueden garantizar o (registro n) peor Caso para todas las operaciones).

Tanto los árboles autoalancados como los hosthmaps tienen la mejor eficiencia de O (log N) en el mejor peor de los casos (suponiendo que el hashmap maneja las colisiones), pero los paps pueden tener un mejor rendimiento de caso (a menudo cerca de O (1)), mientras que los árboles tendrán una OF constante (log n). Esto se debe a que incluso un hashmap puede localizar el índice de inserción en O (1), tiene que tener en cuenta las colisiones de hash (más de un elemento hasta el mismo índice de matriz), y por lo tanto, en el mejor caso se degrada a un auto-equilibrado. El árbol (como la implementación de Java de HashMap), es decir, cada elemento en el hashmap se puede implementar como un árbol autolancado, almacenando todos los elementos que ha hecho hasta la célula de matriz dada.

Answer 6

Creo que si desea consultar para un rango de llaves en lugar de una tecla, la estructura de árbol auto equilibrada se desempeñará mejor que una estructura de tabla hash.