Tablas hash versus árboles binarios

30

Al implementar un diccionario ('Quiero buscar datos de clientes por sus ID de cliente'), las estructuras de datos típicas utilizadas son tablas hash y árboles de búsqueda binarios. Sé, por ejemplo, que la biblioteca C ++ STL implementa diccionarios (los llaman mapas) usando árboles de búsqueda binarios (equilibrados), y .NET Framework usa tablas hash debajo del capó.

¿Cuáles son las ventajas y desventajas de estas estructuras de datos? ¿Hay alguna otra opción que sea razonable en ciertas situaciones?

Tenga en cuenta que no estoy particularmente interesado en los casos en que las claves tienen una estructura subyacente fuerte, por ejemplo, son todos enteros entre 1 y n o algo así.

Alex ten Brink
fuente
1
Te exasperaré pero no puedes decir "enteros entre 1 yn", ya que en ese caso una matriz superará a todas las demás estructuras de datos :-). "Strings" parece justo y cubre la mayoría de las situaciones.
jmad
@jmad dijo que no está interesado en ese caso.
Joe
@ Joe, pensé que estaba claro, tomé esto en cuenta. De todos modos, esa no es una razón para dar el peor ejemplo posible de clave.
jmad
1
En realidad .NET tiene ambos diccionarios implementados usando árboles y diccionarios implementados usando tablas hash (y también C ++ desde el estándar 2011).
sepp2k
Posible lo mismo en SO: stackoverflow.com/questions/371136/…
Ciro Santilli 新疆 改造 中心 法轮功 六四 事件

Respuestas:

26

Se podría escribir un tratado completo sobre este tema; Solo voy a cubrir algunos puntos sobresalientes, y mantendré la discusión de otras estructuras de datos al mínimo (de hecho, hay muchas variantes). A lo largo de esta respuesta, es el número de claves en el diccionario.norte

La respuesta corta es que las tablas hash son más rápidas en la mayoría de los casos , pero pueden ser muy malas en el peor de los casos. Los árboles de búsqueda tienen muchas ventajas, incluido el comportamiento manso en el peor de los casos , pero en algunos casos son algo más lentos.

Los árboles de búsqueda binarios balanceados tienen una complejidad bastante uniforme: cada elemento ocupa un nodo en el árbol (típicamente 4 palabras de memoria), y las operaciones básicas (búsqueda, inserción, eliminación) toman tiempo (asintótico garantizado límite superior). Más precisamente, un acceso en el árbol de toma alrededor de l o g 2 ( n ) comparaciones.O(lsol(norte))losol2(norte)

Las tablas hash son un poco más variables. Requieren una matriz de alrededor de punteros. El acceso a un elemento depende de la calidad de la función hash. El propósito de una función hash es dispersar los elementos. Una tabla hash "funciona" si todos los elementos que desea almacenar tienen hashes diferentes. Si este es el caso, las operaciones básicas (búsqueda, inserción, eliminación) toman O ( 1 ) tiempo, con una constante bastante pequeña (un cálculo de hash más una búsqueda de puntero). Esto hace que las tablas hash sean muy rápidas en muchos casos típicos.2norteO(1)

Un problema general con las tablas hash es que la complejidad no está garantizada.O(1)

  • Además, hay un punto donde la tabla se llena; cuando eso sucede (o, mejor, un poco antes de que eso suceda), la tabla debe ampliarse, lo que requiere mover todos sus elementos, por un costo . Esto puede introducir un comportamiento "desigual" cuando se agregan muchos elementos.O(norte)
  • O(1)

Cuando arroja la localidad de datos en la mezcla, las tablas hash funcionan mal. Funcionan precisamente porque almacenan elementos relacionados muy separados, lo que significa que si la aplicación busca elementos que comparten un prefijo en secuencia, no se beneficiará de los efectos de caché. Esto no es relevante si la aplicación realiza búsquedas esencialmente aleatorias.

Otro factor a favor de los árboles de búsqueda es que son una estructura de datos inmutable : si necesita tomar una copia de un árbol y cambiar algunos elementos, puede compartir la mayor parte de la estructura de datos. Si toma una copia de una tabla hash, debe copiar toda la matriz de punteros. Además, si está trabajando en un lenguaje puramente funcional, las tablas hash a menudo no son una opción.

k1k2h(k1)=h(k2)

En particular, si va a necesitar el orden de las claves, por ejemplo, si desea poder enumerar las claves en orden alfabético, las tablas hash no son de ayuda (tendrá que ordenarlas), mientras que usted puede atravesar directamente un árbol de búsqueda en orden.

Puede combinar árboles de búsqueda binarios y tablas hash en forma de árboles hash . Un árbol de hash almacena las claves en un árbol de búsqueda de acuerdo con su hash. Esto es útil, por ejemplo, en un lenguaje de programación puramente funcional donde desea trabajar en datos que no tienen una relación de orden fácil de calcular.

Cuando las teclas son cadenas (o enteros), un trie puede ser otra opción. Un trie es un árbol, pero indexado de manera diferente a un árbol de búsqueda: escribe la clave en binario, y va a la izquierda por un 0 y a la derecha por un 1. El costo de un acceso es, por lo tanto, proporcional a la longitud de la clave. Los intentos se pueden comprimir para eliminar nodos intermedios; esto se conoce como patricia trie o árbol radix . Los árboles Radix pueden superar a los árboles balanceados, particularmente cuando muchas claves comparten un prefijo común.

Gilles 'SO- deja de ser malvado'
fuente
2
¿Los BST también tienen una localidad de datos incorrecta?
svick
@svick Pueden o no, dependiendo de cómo se asignen los nodos. Aumentar la aridad del árbol puede ayudar sin comprometer el tiempo de ejecución (el costo es mayor y el código más complejo).
Gilles 'SO- deja de ser malvado'
2
En un BST es fácil poner los elementos "en orden", para una tabla hash está fuera de discusión.
vonbrand
Aparte de por razones de seguridad, ¿por qué importa si las tablas hash tienen un mal momento en el peor de los casos si su caso promedio es mejor que el de los árboles binarios? Me imagino que la conveniencia de utilidad / usuario tiene una relación aproximadamente lineal con el tiempo que tarda el árbol en terminar, por lo que el valor esperado (promedio) debería ser lo único que importa.
Kelmikra
@ Kyth'Py1k ¿Qué quieres decir con "el árbol para terminar"? El objetivo de las tablas hash es acceder a un valor a la vez, no a todo el árbol, de lo contrario, una lista o matriz funcionaría mejor. Incluso en situaciones donde el valor promedio es lo que importa (que no siempre es el caso, por ejemplo, cuando tiene restricciones en tiempo real), es el promedio sobre las solicitudes que se hacen en una situación dada, que a menudo no son del todo uniformes sobre la mesa - por ejemplo, sesgado a un cierto prefijo.
Gilles 'SO- deja de ser malvado'