data structures - Ventajas de los árboles de búsqueda binaria sobre las tablas hash

data-structures hashtable (19)

Además de todos los otros buenos comentarios:

Las tablas hash en general tienen un mejor comportamiento de caché que requiere menos lecturas de memoria en comparación con un árbol binario. Para una tabla hash, normalmente solo incurre en una sola lectura antes de tener acceso a una referencia que contiene sus datos. El árbol binario, si es una variante equilibrada, requiere algo en el orden de k * lg (n) lecturas de memoria para alguna constante k.

Por otro lado, si un enemigo conoce tu función hash, el enemigo puede aplicar tu tabla hash para hacer colisiones, dificultando en gran medida su rendimiento. La solución consiste en elegir aleatoriamente la función hash de una familia, pero una BST no tiene esta desventaja. Además, cuando la presión de la tabla hash crece demasiado, a menudo tiende a agrandarse y reasignar la tabla hash que puede ser una operación costosa. El BST tiene un comportamiento más simple aquí y no tiende a asignar repentinamente una gran cantidad de datos y realizar una operación de reajuste.

Los árboles tienden a ser la estructura de datos promedio final. Pueden actuar como listas, pueden dividirse fácilmente para una operación paralela, tienen una eliminación rápida, una inserción y una búsqueda del orden de O (lg n) . No hacen nada particularmente bien, pero tampoco tienen un comportamiento excesivamente malo.

Finalmente, las BST son mucho más fáciles de implementar en los lenguajes funcionales (puros) en comparación con las tablas hash y no requieren la implementación de actualizaciones destructivas (el argumento de persistencia de Pascal anterior).

¿Cuáles son las ventajas de los árboles de búsqueda binarios sobre las tablas hash?

Las tablas Hash pueden buscar cualquier elemento en tiempo Theta (1) y es tan fácil agregar un elemento ... pero no estoy seguro de las ventajas al revés.

BST también proporciona las operaciones "findPredecessor" y "findSuccessor" (para encontrar los siguientes elementos más pequeños y próximos) en el tiempo O (logn), lo que también podría ser una operación muy útil. Hash Table no puede proporcionar en ese momento eficiencia.

De Cracking the Coding Interview, 6ª Edición

Podemos implementar la tabla hash con un árbol de búsqueda binaria equilibrado (BST). Esto nos da un tiempo de búsqueda O (log n). La ventaja de esto es potencialmente el uso de menos espacio, ya que no asignamos una gran matriz. También podemos iterar a través de las teclas en orden, lo que a veces puede ser útil.

La principal ventaja de la tabla hash es que hace casi todas las operaciones en ~ = O (1). Y es muy fácil de entender e implementar. Resuelve muchos "problemas de entrevista" de manera eficiente. Entonces, si quieres descifrar una entrevista de codificación, haz mejores amigos con hash table ;-)

Las clases HashSet y Table son colecciones desordenadas. No es obvio desde la interfaz (y podría ser de otro modo), pero las tablas hash se han implementado utilizando Árboles AVL. Esto significa que el código hash no se reduce por el módulo de una matriz (menos colisiones) y también significa que no hay reajuste de una matriz para hacer (rendimiento más suave). El hecho de que sean colecciones no ordenadas significa que usted solo proporciona una función igual y una función hashCode, no un comparador completo en cuanto a árboles. Entonces, ya sea que use una tabla hash Tabla <K, T> o un árbol binario Árbol <K, T> depende de la clase K - si es totalmente comparable o solo comparable a la igualdad.

Hay ocasiones en que el tipo de datos es comparable e igual a la igualdad, como String. Esto significa que HashSet <String> y Set <String> son ambos posibles. Las búsquedas en un conjunto de cadenas hash tienden a ser unas 10 veces más rápidas que las búsquedas en un conjunto ordenado de cadenas. Si el comparador es costoso, los árboles se ralentizan en comparación con HashTables. Si el comparador es rápido (como para enteros y flotantes), los árboles se ejecutarán más rápido que las tablas hash.

Las principales ventajas de un árbol binario sobre una tabla hash es que el árbol binario le da dos operaciones adicionales que no puede hacer (fácil, rápidamente) con una tabla hash

encuentre el elemento más cercano (no necesariamente igual a) algún valor clave arbitrario (o más cercano arriba / abajo)
iterar a través del contenido del árbol en orden ordenado

Los dos están conectados: el árbol binario mantiene sus contenidos en un orden ordenado, por lo que las cosas que requieren ese orden son fáciles de hacer.

Las tablas hash no son buenas para indexar. Cuando busca un rango, las BST son mejores. Esa es la razón por la cual la mayoría de los índices de bases de datos usan árboles B + en lugar de Tablas Hash

Los árboles binarios de búsqueda son una buena opción para implementar diccionario si las claves tienen un orden total (las claves son comparables) definidas en ellas y usted desea conservar la información de la orden.

Como BST conserva la información de la orden, le proporciona cuatro operaciones de conjunto dinámico adicionales que no se pueden realizar (de manera eficiente) utilizando tablas hash. Estas operaciones son:

Máximo
Mínimo
Sucesor
Predecesor

Todas estas operaciones, como todas las operaciones BST, tienen una complejidad temporal de O (H). Además, todas las claves almacenadas permanecen ordenadas en la BST, lo que le permite obtener la secuencia ordenada de las claves simplemente atravesando el árbol en orden.

En resumen, si todo lo que quiere es insertar operaciones, eliminar y eliminar, entonces la tabla hash es inmejorable (la mayoría de las veces) en rendimiento. Pero si desea alguna o todas las operaciones enumeradas anteriormente, debe usar una BST, preferiblemente una BST autoequilibrante.

Recuerde que los árboles de búsqueda binarios (basados en referencias) son eficientes en cuanto a la memoria. No reservan más memoria de la que necesitan.

Por ejemplo, si una función hash tiene un rango R(h) = 0...100 , entonces necesita asignar una matriz de 100 elementos (punteros a), incluso si solo está mezclando 20 elementos. Si tuviera que usar un árbol de búsqueda binario para almacenar la misma información, solo asignaría el espacio que necesitara, así como algunos metadatos sobre los enlaces.

Se puede implementar un árbol de búsqueda binario con una interfaz persistente , donde se devuelve un nuevo árbol pero el árbol viejo continúa existiendo. Implementado cuidadosamente, los árboles viejos y nuevos comparten la mayoría de sus nodos. No puedes hacer esto con una tabla hash estándar.

Si desea acceder a los datos de una manera ordenada, entonces una lista ordenada debe mantenerse en paralelo a la tabla hash. Un buen ejemplo es Dictionary in .Net. (vea http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx ).

Esto tiene el efecto secundario de no solo ralentizar inserciones, sino que consume una mayor cantidad de memoria que un b-tree.

Además, dado que se ordena un árbol b, es simple encontrar rangos de resultados o realizar uniones o fusiones.

También depende del uso, Hash permite localizar la coincidencia exacta. Si desea consultar un rango, BST es la opción. Supongamos que tiene muchos datos e1, e2, e3 ..... en.

Con la tabla hash puede ubicar cualquier elemento en tiempo constante.

Si desea encontrar valores de rango mayores que e41 e inferiores a e8, BST puede encontrarlos rápidamente.

La clave es la función hash utilizada para evitar una colisión. Por supuesto, no podemos evitar totalmente una colisión, en cuyo caso recurrimos al encadenamiento u otros métodos. Esto hace que la recuperación ya no sea un tiempo constante en los peores casos.

Una vez que esté completa, la tabla hash debe aumentar el tamaño de la cubeta y copiar de nuevo todos los elementos. Este es un costo adicional no presente en BST.

Un árbol binario es más lento de buscar e insertar, pero tiene la característica muy agradable de infijo transversal que esencialmente significa que puede iterar a través de los nodos del árbol en un orden ordenado.

Iterar a través de las entradas de una tabla hash simplemente no tiene mucho sentido porque están todos desperdigados en la memoria.

Un árbol de búsqueda binaria (equilibrado) también tiene la ventaja de que su complejidad asintótica es en realidad un límite superior, mientras que los tiempos "constantes" de las tablas hash son tiempos amortizados: si tiene una función hash inapropiada, puede terminar degradando a tiempo lineal , en lugar de constante.

Un hashmap es una matriz asociativa establecida. Por lo tanto, su matriz de valores de entrada se agrupa en grupos. En un esquema de direccionamiento abierto, tiene un puntero a un segmento, y cada vez que agrega un nuevo valor en un segmento, descubre en qué lugar del espacio hay espacios libres. Hay algunas formas de hacerlo: comience por el principio del cubo e incremente el puntero cada vez y compruebe si está ocupado. Esto se llama sondeo lineal. Luego, puede hacer una búsqueda binaria como agregar, donde duplica la diferencia entre el inicio del depósito y donde se duplica o retrocede cada vez que busca un espacio libre. Esto se llama exploración cuadrática. DE ACUERDO. Ahora los problemas en ambos métodos son que si el cubo se desborda en la siguiente dirección de cubos, entonces debes:

Duplique el tamaño de cada cubeta: malloc (N cubetas) / cambie la función hash. Tiempo requerido: depende de la implementación de malloc.
Transfiera / copie cada uno de los datos de los cubos anteriores en los datos de los nuevos cubos. Esta es una operación O (N) donde N representa toda la información

DE ACUERDO. pero si usa una lista de enlaces, no debería haber tal problema ¿no? Sí, en las listas vinculadas no tiene este problema. Teniendo en cuenta que cada cubo debe comenzar con una lista vinculada, y si tiene 100 elementos en un depósito, debe recorrer esos 100 elementos para llegar al final de la lista enlazada, por lo tanto, List.add (Elemento E) tomará tiempo para:

Hash el elemento a un cubo - Normal como en todas las implementaciones
Tómese el tiempo para encontrar el último elemento en dicha operación de cubo O (N).

La ventaja de la implementación de la lista enlazada es que no necesita la operación de asignación de memoria y O (N) transferencia / copia de todos los segmentos como en el caso de la implementación de direccionamiento abierto.

Entonces, la forma de minimizar la operación O (N) es convertir la implementación a la de un árbol de búsqueda binaria donde las operaciones de búsqueda son O (log (N)) y se agrega el elemento en su posición en función de su valor. ¡La característica adicional de un BST es que viene ordenado!

Una "ventaja" de un árbol binario es que puede atravesarse para listar todos los elementos en orden. Esto no es imposible con una tabla Hash, pero no es un diseño de operación normal en una estructura hash.

Una tabla hash es una estructura de datos desordenada. Al diseñar un teléfono celular, desea mantener la mayor cantidad posible de datos para el almacenamiento de datos. Una tabla hash es una estructura de datos desordenada, lo que significa que no mantiene sus elementos en un orden particular. Por lo tanto, si usa una tabla hash para una libreta de direcciones de un teléfono celular, necesitaría memoria adicional para ordenar los valores porque definitivamente tendría que mostrar los valores en orden alfabético; después de todo, es una libreta de direcciones. Por lo tanto, al usar una tabla hash, debe separar la memoria para ordenar los elementos que, de lo contrario, se usarían como espacio de almacenamiento. Pero el árbol de búsqueda binaria es una estructura de datos ordenados. Debido a que un árbol de búsqueda binaria ya está ordenado, no habrá necesidad de perder memoria o procesar registros de clasificación de tiempo en un teléfono celular. Como mencionamos anteriormente, hacer una búsqueda o insertar en un árbol binario es más lento que hacerlo con una tabla hash, pero la libreta de direcciones de un teléfono celular casi nunca tendrá más de 5,000 entradas. Con un número tan pequeño de entradas, la O (log (n)) de un árbol de búsqueda binaria definitivamente será lo suficientemente rápida. Entonces, dada toda esa información, un árbol de búsqueda binario es la estructura de datos que debe usar en este escenario, ya que es una mejor opción que una tabla hash.

Una tabla hash ocuparía más espacio cuando se creó por primera vez: tendrá espacios disponibles para los elementos que aún no se han insertado (independientemente de si están o no insertados), un árbol de búsqueda binaria solo será tan grande como sea necesario para ser. Además, cuando una tabla hash necesita más espacio, expandirse a otra estructura puede llevar mucho tiempo, pero eso podría depender de la implementación.

Una ventaja que nadie más ha señalado es que el árbol de búsqueda binario le permite hacer búsquedas de rango de manera eficiente.

Para ilustrar mi idea, quiero hacer un caso extremo. Digamos que quiere obtener todos los elementos cuyas claves están entre 0 y 5000. Y en realidad solo hay un elemento y 10000 elementos más cuyas claves no están en el rango. BST puede hacer búsquedas de rango de manera bastante eficiente ya que no busca un subárbol que es imposible tener la respuesta.

Mientras, ¿cómo puedes hacer búsquedas de rango en una tabla hash? O necesita iterar cada espacio de cubeta, que es O (n), o tiene que buscar si cada uno de 1,2,3,4 ... hasta 5000 existe. (¿Qué pasa con las teclas entre 0 y 5000 que son un conjunto infinito? Por ejemplo, las teclas pueden ser decimales)