Tabla hash vs Árbol binario balanceado

Question

¿Qué factores debo tener en cuenta cuando tengo que elegir entre una tabla hash o un árbol binario balanceado para implementar un conjunto o una matriz asociativa?

Answer 1

Esta pregunta no puede ser respondida, en general, me temo.

El problema es que hay muchos tipos de tablas hash y árboles binarios balanceados, y sus rendimientos varían ampliamente.

Por lo tanto, la respuesta ingenua es: depende de la funcionalidad que necesita.Use una tabla hash si no necesita ordenar y un árbol binario balanceado de lo contrario.

Para una respuesta más elaborada, consideremos algunas alternativas.

Hash Table (ver la entrada de Wikipedia para algunos conceptos básicos)

• No todas las tablas hash utiliza una lista enlazada como un cubo. Una alternativa popular es utilizar un depósito "mejor", por ejemplo, un árbol binario u otra tabla hash (con otra función hash), ...
• Algunas tablas hash no usan cubetas en absoluto: consulte Abrir direcciones (viene con otros problemas, obviamente)
• Hay algo llamado re-hash lineal (es una calidad de detalle de implementación), que evita la trampa del "pare el mundo y rehaga". Básicamente, durante la fase de migración, solo se inserta en la tabla "nueva" y también se mueve una entrada "antigua" a la tabla "nueva". Por supuesto, fase de migración significa el doble de consulta, etc ...

Binary Tree

• reequilibrio es costoso, usted puede considerar un Skip-lista (también mejor para accesos multi-hilo) o un árbol Splay.
• Un buen asignador puede "agrupar" nodos en la memoria (mejor comportamiento de almacenamiento en caché), aunque esto no alivia el problema de búsqueda del puntero.
• árbol B y variantes también ofrecen "embalaje"

No olvidemos que O (1) es una complejidad asintótica. Para algunos elementos, el coeficiente suele ser más importante (rendimiento). Lo cual es especialmente cierto si su función hash es lenta ...

Finalmente, para los conjuntos, también puede considerar estructuras de datos probabilísticos, como Bloom Filters.

Answer 2

Las tablas hash son generalmente mejores si no hay necesidad de mantener los datos en cualquier clase de secuencia. Los árboles binarios son mejores si los datos deben mantenerse ordenados.

Answer 3

tablas hash son las búsquedas más rápidas:

• se necesita una llave que genera una distribución uniforme (de lo contrario vas a perder mucho y tienen que confiar en algo que no sea de hash; como una búsqueda lineal).
• Hash puede usar una gran cantidad de espacio vacío. Puede reservar 256 entradas pero solo necesita 8 (hasta ahora).

árboles binarios:

• determinista. O (log n) Creo que ...
• No necesita espacio adicional como tablas hash puede
• Se debe mantener ordenado. Agregar un elemento en el medio significa mover el resto.

Answer 4

Si solo necesita acceder a elementos individuales, las tablas hash son mejores. Si necesita un rango de elementos, simplemente no tiene otra opción que árboles binarios.

Answer 5

Un punto valioso en una arquitectura moderna: una tabla Hash generalmente, si su factor de carga es bajo, tendrá menos lecturas de memoria que un árbol binario. Dado que el acceso a la memoria suele ser bastante costoso en comparación con la grabación de ciclos de la CPU, la tabla Hash suele ser más rápida.

En el siguiente árbol binario se supone que es autoequilibrante, como un árbol negro rojo, un árbol AVL o como un tratamiento.

Por otro lado, si necesita volver a configurar todo en la tabla hash cuando decide extenderla, puede ser una operación costosa (amortizada). Los árboles binarios no tienen esta limitación.

Los árboles binarios son más fáciles de implementar en lenguajes puramente funcionales.

Los árboles binarios tienen un orden natural y una forma natural de recorrer el árbol para todos los elementos.

Cuando el factor de carga en la tabla hash es bajo, puede estar desperdiciando una gran cantidad de espacio en la memoria, pero con dos punteros, los árboles binarios tienden a ocupar más espacio.

Las tablas hash son casi O (1) (dependiendo de cómo se maneja el factor de carga) vs. Bin árboles O (lg n).

Los árboles tienden a ser el "artista promedio". No hay nada que hagan particularmente bien, pero luego nada de lo que hacen es particularmente malo.

Answer 6

Para añadir a las otras grandes respuestas anteriores, diría:

utiliza una tabla hash si la cantidad de datos no va a cambiar (por ejemplo, el almacenamiento de constantes); pero, si la cantidad de datos cambiará, use un árbol. Esto se debe al hecho de que, en una tabla hash, una vez que se ha alcanzado el factor de carga, la tabla hash debe cambiar de tamaño. La operación de cambio de tamaño puede ser muy lenta.

Answer 7

Un árbol de búsqueda binario requiere una relación de orden total entre las claves. Una tabla hash solo requiere una relación de equivalencia o identidad con una función hash consistente.

Si hay una relación de orden total disponible, una matriz ordenada tiene un rendimiento de búsqueda comparable a árboles binarios, el peor desempeño de inserción en el orden de las tablas hash, y menos complejidad y uso de memoria que ambos.

La complejidad de inserción del peor caso para una tabla hash se puede dejar en O (1)/O (log K) (con K la cantidad de elementos con el mismo hash) si es aceptable aumentar la búsqueda del peor de los casos complejidad a O (K) u O (log K) si los elementos pueden ser ordenados.

Los invariantes de árboles y tablas hash son caros de restaurar si las claves cambian, pero menos de O (n log N) para las matrices ordenadas.

Estos son factores a tener en cuenta para decidir qué aplicación utilizar:

1. Disponibilidad de una relación de orden total.
2. Disponibilidad de una buena función hash para la relación de equivalencia.
3. Conocimiento a priori de la cantidad de elementos.
4. Conocimiento sobre la tasa de inserciones, eliminaciones y búsquedas.
5. Complejidad relativa de las funciones de comparación y hashing.

Answer 8

Si tiene muchas instancias ligeramente diferentes de conjuntos, probablemente querrá que compartan estructura. Esto es fácil con árboles (si son inmutables o copy-on-write). No estoy seguro de lo bien que puedes hacerlo con hashtables; es al menos menos obvio.

Answer 9

En mi experiencia, los hastables son siempre más rápidos porque los árboles sufren demasiados efectos de caché.

Para ver algunos datos reales, se puede consultar la página de referencia de la biblioteca de mi TommyDS http://tommyds.sourceforge.net/

aquí se puede ver comparado el rendimiento de las bibliotecas tabla hash más común, los árboles y trie disponibles.

Answer 10

Un punto que no creo que se haya abordado es que los árboles son mucho mejores para estructuras de datos persistentes. Es decir, estructuras inmutables. Una tabla hash estándar (es decir, una que utiliza una única matriz de listas vinculadas) no se puede modificar sin modificar toda la tabla. Una situación en la que esto es relevante es si dos funciones simultáneas tienen una copia de una tabla hash, y una de ellas cambia la tabla (si la tabla es mutable, ese cambio también será visible para el otro). Otra situación sería algo como lo siguiente:

def bar(table): 
    # some intern stuck this line of code in 
    table["hello"] = "world" 
    return table["the answer"] 

def foo(x, y, table): 
    z = bar(table) 
    if "hello" in table: 
     raise Exception("failed catastrophically!") 
    return x + y + z 

important_result = foo(1, 2, { 
    "the answer": 5, 
    "this table": "doesn't contain hello", 
    "so it should": "be ok" 
}) 
# catastrophic failure occurs 

Con una mesa mutable, no podemos garantizar que la mesa recibe una llamada de función seguirá siendo de esa mesa durante toda su ejecución, ya que otras llamadas a funciones podrían modificarlo.

Por lo tanto, la mutabilidad a veces no es algo agradable. Ahora, una forma de evitar esto sería mantener la tabla inmutable, y hacer que las actualizaciones devuelvan una nueva tabla sin modificar la anterior. Pero con una tabla hash esto a menudo sería una costosa operación O (n), ya que toda la matriz subyacente necesitaría ser copiada. Por otro lado, con un árbol equilibrado, se puede generar un nuevo árbol con solo O (log n) nodos que deben crearse (el resto del árbol es idéntico).

Esto significa que un árbol eficiente puede ser muy conveniente cuando se desean mapas inmutables.

Answer 11

Un punto a tener en cuenta es sobre el elemento transversal, mínimo y máximo. Las tablas hash no admiten ningún tipo de recorrido ordenado ni acceso a los artículos mínimos o máximos. Si estas capacidades son importantes, el árbol binario es una mejor opción.