comparar Hash con árbol de búsqueda binaria

Question

Todos sabemos que una tabla hash tiene O (1) tiempo para ambas inserciones y búsquedas si la función hash fue bien elegida. Entonces, ¿cuál es el motivo por el que queremos utilizar el árbol de búsqueda binaria? ¿Solo porque una función de hash perfecta era difícil de diseñar?

¿Cómo surgió esta pregunta? noto que estándar C++ STL tiene set y map que se implementa con binario árbol de búsqueda, pero no tiene la almohadilla (no estamos hablando de no stardard hash_set, hash_map). Mientras, Ruby solo tiene Hash. Quiero entender lo racional detrás de esta diferencia.

Answer 1

Los árboles permiten la traversión en orden.

El peor de los casos para una tabla hash es O (N) (búsqueda lineal a través de un cubo), una búsqueda binaria está limitada por O (log N).

NB: esto requiere que el árbol esté equilibrado, es por eso que la implementación típica usa un árbol de autoequilibrado, como un árbol rojo-negro.

Mientras que una degradación de este tipo es poco probable, que no es imposible y depende fuertemente de la capacidad para elegir una función hash apropiado y la distribución de los datos reales.

Una implementación de árbol también crece trivialmente al tamaño requerido, mientras que un hashmap comienza a degradarse cuando se llena (para la mayoría de las implementaciones, se dice que alrededor del 70% de los cubos se rellenan). O necesita volver a configurar toda la tabla (una vez más, malas aplicaciones en tiempo real), o pasar gradualmente a una nueva tabla, que no es una implementación simple.

Al final, STL probablemente solo utilizó una plantilla de contenedor "base", el árbol, para evitar la complejidad de implementación adicional.

Answer 2

Los árboles de búsqueda de pozos están ordenados, los hash no lo son.

Answer 3

Puede acceder a los datos en un árbol de búsqueda binario en orden.

Answer 4

Para agregar una respuesta peterchen, las estructuras hash aunque teóricamente más rápidas en la inserción y eliminación dependen enormemente de los datos reales, la función hash elegida y la cantidad de datos.

• Una función de hash perfecta depende de la cantidad y la distribución de los datos.

Tener grandes variaciones de rendimiento entre los mejores y peores casos los hace aptos para estructuras de propósito general. Los árboles binarios, por otro lado, son más predecibles independientemente de la cantidad/tipo de datos utilizados, aunque son menos eficientes en el mejor de los casos.

Answer 5

El STL no incluía inicialmente una tabla hash entre los contenedores, ya que las tablas hash son más complejas; debe elegir entre direcciones abiertas y cerradas, sin mencionar la función hash, etc. En ese momento, Stepanov y Stroustrup estábamos tratando de acelerar el progreso para que fuera aceptado rápidamente en el estándar.

Los árboles, por otro lado, son relativamente más simples. Ya se sabía que, dado que estas son estructuras de datos en memoria, podemos simplemente usar un árbol binario en lugar de un árbol B.Luego fue una elección entre los árboles AVL y RB. Los árboles RB tienden a ser elegidos debido a las mejores características de rendimiento que no estoy en condiciones de comentar, pero los artículos de Wikipedia sobre ambas estructuras (AVL y RB) le darán más información con relativamente buen detalle.

De lo contrario, los árboles y las tablas hash son buenos para cosas diferentes. Si necesita inserciones o recuperaciones rápidas, y no le importa el orden en que están almacenadas, las tablas hash son buenas. Si necesita características de pedido y garantías sólidas sobre inserciones y recuperaciones, entonces los árboles binarios son buenos. Otra buena regla general es el perfil. Dado que la mayoría de los usos de cualquiera de ellos serían compatibles con la interfaz, también ayuda el perfil para ver qué le ofrece un mejor rendimiento.

Answer 6

Para usar un árbol necesita una forma de pedir artículos en el árbol. Para usar una tabla hash, necesita una función para calcular el valor hash de un elemento en la tabla hash.

Curiosamente, el .NET Framework requiere que cada clase implemente (o herede) la función GetHashCode que permite que cada objeto se almacene en una tabla hash. Sin embargo, esto también agrega una carga adicional a los desarrolladores que están obligados a implementar funciones hash semánticamente correctas, incluso si no tienen la intención de que la clase sea hash. Una solución es devolver un valor constante desde GetHashCode, que es semánticamente correcto, pero no muy eficiente si la función alguna vez se utiliza para hash.

Answer 7

En la época de C++ las personas seguían siendo fanáticas del enfoque académico riguroso de las estructuras de datos y los algoritmos, por lo que preferían estructuras con menor huella de memoria y el mejor y mejor comportamiento del caso.

En el momento en que apareció Ruby, y para propósitos de scripting, las personas se dieron cuenta de que favorecen la simplicidad sobre el rendimiento sin procesar, y dado que las tablas permiten semánticas de ambas matrices (si usa el índice secuencial como clave) Y de diccionarios (si usar la clave natural), se consideraron como una estructura de datos más universal.

Answer 8

Si puede salirse con la suya, siempre debe preferir un hash sobre un árbol de búsqueda binario. Hashes tiene una memoria superior más alta que los árboles, pero toda la memoria que están utilizando se puede asignar en un bloque grande. Para los árboles, cada nodo agregado requiere una asignación separada que provoca una gran fragmentación y es malo para el rendimiento. De forma similar, preferiría leer 1000 bytes de 1 archivo en lugar de 1 byte de 1000 archivos diferentes.

El caso en el que hashes no funciona es cuando el orden importa. Por ejemplo, suponga que está escribiendo un asignador de memoria y almacena bloques de memoria libres en una estructura de datos. Las claves son los tamaños de los bloques y los valores son los indicadores para ellos.

Una solicitud de memoria implica consultar esta estructura de datos y encontrar el bloque más pequeño (¡implica pedir!) Que satisface la solicitud. Por ejemplo, si tiene bloques con las teclas 10, 20, 30 y aparece una solicitud de 20 bytes de memoria, seleccione el segundo bloque. Un hashmap puede hacer eso fácilmente.

Pero, ¿y si la solicitud es para 22 bytes? Como no hay una clave con el valor 20, debe iterar todo el hashmap para encontrar la tecla derecha (30) que es una operación O (n). Pero si ha usado un árbol, entonces, para "encontrar la clave más pequeña más grande que una tecla dada", es una operación O (log n).