Tablas hash versus árboles binarios

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í.

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.$n$

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(\mathrm{lg}(n))$$\mathrm{log}_2(n)$

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.$2n$$O(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(n)$
• $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.

$k_1 \equiv k_2 \implies h(k_1) = h(k_2)$

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.