Hash Table v/s Trees

¿Las tablas hash siempre son más rápidas que los árboles? Aunque las Hashtables tienen O (1) complejidad de búsqueda, pero supongamos que debido a la función hash mal diseñada muchas colisiones ocurren y si manejamos las colisiones usando una estructura encadenada (digamos un árbol balanceado) entonces el peor tiempo de ejecución para la búsqueda sería O (log n) Entonces, ¿puedo concluir que para los conjuntos de datos grandes o pequeños, incluso en el caso de los peores escenarios, las tablas hash siempre serán más rápidas que los árboles? Además, si tengo una memoria amplia y no quiero búsquedas de rango, ¿siempre puedo buscar una tabla hash?Hash Table v/s Trees

Fuente

2012-04-05 avinash shah

No soy un experto, pero diría que es situacional. Muchas funciones de hashing son caras, y para ciertos patrones de acceso, un árbol es bueno. –

"Siempre" es una palabra tan grande que abarca todo. ¿Alguna posibilidad de que puedas editar esta pregunta para reducirla a algo un poco más específico, como escenarios específicos (solo)? De lo contrario, casi con certeza se cerrará como no constructivo. –

Mucha gente aquí ha mencionado que el peor caso sería O (N). ¿Cómo puede ser O (n) si las colisiones se manejan usando una estructura de árbol balanceado en lugar de una lista vinculada? El peor caso para buscar en un árbol balanceado como AVL sería O (log n) –

¿Las tablas hash siempre son más rápidas que los árboles?

No, no siempre. Esto depende de muchas cosas, como el tamaño de la colección, la función hash, y para algunas implementaciones de tablas hash, también el número de operaciones de eliminación.

hash-tables son O(1) por op en promedio - pero este no es siempre el caso. Pueden ser O(n) en peores casos.

Algunas de las razones que se me ocurre en este momento a los árboles prefieren:

Ordenar es importante. [las tablas hash no mantienen el orden, BST está ordenada por definición]
Latency es un problema, y no puede sufrir el O(n) que pueda ocurrir. [Esto podría ser crítico para los sistemas en tiempo real]
Los datos de Ther podrían ser "similares" a su función de hash, y muchos elementos hash a las mismas ubicaciones [colisiones] no es imposible. [esto puede resolverse algunas veces usando una función hash diferente]
Para colecciones relativamente pequeñas: muchas veces la constante oculta entre la tabla hashtable O(1) es mucho más alta que la del árbol, y usar un árbol podría ser más rápido para colecciones pequeñas.

Sin embargo, si los datos son enormes, la latencia no es un problema y las colisiones no son probables, las tablas hash son asintóticamente mejores que usar un árbol.

Fuente

2012-04-05 17:56:30 amit

A menudo, los árboles cuidadosamente empaquetados pueden superar una tabla hash debido a la coherencia de la memoria caché (ya sea desde la memoria principal o el disco). No importa la cantidad de datos que tenga en este caso: las tablas hash pueden no ser su mejor opción según cómo esté utilizando la estructura del diccionario. – Kaganar

¿Qué tablas hash? ¿Está abierto el direccionamiento de tablas hash o tablas hash "cubo"? Con o sin cambio de tamaño incremental? ¿O basado en Hashing lineal? ¡Hay * tantas implementaciones de tablas hash! Su respuesta es incorrecta para algunos de ellos, así que por favor, sean precisos. –

@MatthieuM .: Estos son los inconvenientes tradicionales de prácticamente todas las tablas hash, incluso si se usa el direccionamiento abierto o el encadenamiento con una matriz simple como el "cubo". Hacer un pedido es una desventaja porque el hashing no garantiza que se mantendrá el orden. La latencia es un problema debido al peor de los casos (si no puede sufrir ninguna operación 'O (n)' debido a algunas restricciones, es un problema), el valor hash similar no es realmente un inconveniente, ya que puede resolverse fácilmente eligiendo un función de hash diferente, y el problema de tamaño suele ser debido a la tara de las funciones hash si no recuerdo mal. ¿Con qué específicamente tienes un problema? – amit

Use hashtable e inícielo con la dimensión adecuada. Por ejemplo, si usa solo la mitad de espacio, las colisiones son muy pocas.

Fuente

2012-04-05 17:55:28 dash1e

En el peor de los casos, tendrá O (n) tiempo en hast-tables. Pero esto es una explosión de miles de millones menos probable que el sol escriba ahora, por lo que cuando se utiliza una buena función hash se puede asumir con seguridad que funciona en O (1) a menos que el sol explote.
Por otro lado, el rendimiento de Hash-Tables y Trees puede variar según la implementación, el idioma y la fase de la luna, por lo que la única buena respuesta es "Pruebe ambos, think y elija mejor".

Fuente

2012-04-05 17:55:39 kilotaras

Si debido al mal diseñados función montón de hash de colisiones suceda y si manejamos colisiones utilizando la estructura encadenada (por ejemplo un árbol equilibrado) entonces el peor de los casos el tiempo de funcionamiento para la búsqueda sería O (n) (no O (log norte)). Por lo tanto, no puede concluir con los conjuntos de datos grandes o pequeños, incluso en el caso de los peores escenarios, las tablas hash siempre serán más rápidas que los árboles.

Fuente

2012-04-05 17:56:38

Respuesta

Cuestiones relacionadas