algorithm - estructuras - tablas hash que es

Árboles Binarios vs. Listas Vinculadas vs. Tablas Hash (10)

Estoy construyendo una tabla de símbolos para un proyecto en el que estoy trabajando. Me preguntaba qué opiniones tienen las personas sobre las ventajas y desventajas de los diversos métodos disponibles para almacenar y crear una tabla de símbolos.

He realizado bastante búsqueda y los más recomendados son los árboles binarios o las listas enlazadas o tablas hash. ¿Cuáles son las ventajas o desventajas de todo lo anterior? (trabajando en c ++)

A menos que espere que su tabla de símbolos sea pequeña, debería evitar las listas vinculadas. Una lista de 1000 elementos tomará en promedio 500 iteraciones para encontrar cualquier elemento dentro de ella.

Un árbol binario puede ser mucho más rápido, siempre que esté equilibrado. Si persiste en los contenidos, es probable que se ordene el formulario serializado y, cuando se vuelva a cargar, el árbol resultante quedará totalmente desbalanceado como consecuencia, y se comportará igual que la lista vinculada, porque eso es Básicamente en lo que se ha convertido. Los algoritmos de árbol equilibrado resuelven este problema, pero hacen que todo el grupo sea más complejo.

Un hashmap (siempre que elijas un algoritmo hash adecuado) parece ser la mejor solución. No ha mencionado su entorno, pero casi todos los idiomas modernos tienen un Hashmap integrado.

Esto depende de varias cosas, por supuesto. Diría que una lista vinculada es correcta, ya que tiene pocas propiedades adecuadas para funcionar como una tabla de símbolos. Un árbol binario podría funcionar, si ya tiene uno y no tiene que perder tiempo escribiendo y depurándolo. Mi elección sería una tabla hash, creo que es más o menos la predeterminada para este propósito.

Lo que todo el mundo parece olvidar es que para pequeños Ns, es decir, pocos símbolos en su tabla, la lista enlazada puede ser mucho más rápida que la tabla hash, aunque en teoría su complejidad asintótica es de hecho más alta.

Hay un comentario famoso de Pike''s Notes on Programming in C: "Rule 3. Los algoritmos de lujo son lentos cuando n es pequeño, y n es usualmente pequeño. Los algoritmos de lujo tienen grandes constantes. Hasta que sepa que n con frecuencia será grande, no seas elegante ". http://www.lysator.liu.se/c/pikestyle.html

No puedo decir por tu publicación si tratarás con una N pequeña o no, pero recuerda siempre que el mejor algoritmo para N grandes no es necesariamente bueno para pequeñas Ns.

Me gusta la respuesta de Bill, pero en realidad no sintetiza las cosas.

De las tres opciones:

Las listas vinculadas son relativamente lentas para buscar elementos desde (O (n)). Entonces, si tiene muchos elementos en su mesa, o va a hacer muchas búsquedas, entonces no son la mejor opción. Sin embargo, son fáciles de construir y también fáciles de escribir. Si la tabla es pequeña, y / o solo hace un pequeño escaneo a través de ella después de que está construida, entonces esta podría ser la opción para usted.

Las tablas hash pueden ser tremendamente rápidas. Sin embargo, para que funcione, debe elegir un buen hash para su aportación, y debe elegir una tabla lo suficientemente grande como para contener todo sin muchas colisiones hash. Lo que eso significa es que tienes que saber algo sobre el tamaño y la cantidad de tu entrada. Si lo estropeas, terminas con un conjunto de listas vinculadas realmente caras y complejas. Yo diría que, a menos que sepa de antemano aproximadamente qué tan grande será la mesa, no use una tabla hash. Esto no está de acuerdo con su respuesta "aceptada". Lo siento.

Eso deja árboles. Sin embargo, tiene una opción aquí: equilibrar o no equilibrar. Lo que he encontrado al estudiar este problema en el código de C y Fortran que tenemos aquí es que la entrada de la tabla de símbolos tiende a ser lo suficientemente aleatoria como para que solo pierda uno o dos niveles de árbol al no equilibrar el árbol. Dado que los árboles equilibrados son más lentos para insertar elementos y son más difíciles de implementar, no me molestaría con ellos. Sin embargo, si ya tiene acceso a buenas bibliotecas de componentes depurados (por ejemplo: STL de C ++), entonces también podría seguir adelante y usar el árbol equilibrado.

Otros comentarios se han centrado en agregar / recuperar elementos, pero esta discusión no está completa sin considerar lo que se necesita para iterar sobre toda la colección. La respuesta breve aquí es que las tablas hash requieren menos memoria para iterar, pero los árboles requieren menos tiempo.

Para una tabla hash, la sobrecarga de memoria de iterar sobre los pares (clave, valor) no depende de la capacidad de la tabla o del número de elementos almacenados en la tabla; de hecho, iterar debería requerir solo una sola variable de índice o dos.

Para los árboles, la cantidad de memoria requerida siempre depende del tamaño del árbol. Puede mantener una cola de nodos no visitados al iterar o agregar punteros adicionales al árbol para facilitar la iteración (haciendo que el árbol, para propósitos de iteración, actúe como una lista enlazada), pero de cualquier manera, debe asignar memoria adicional para la iteración .

Pero la situación se revierte cuando se trata del tiempo. Para una tabla hash, el tiempo que lleva iterar depende de la capacidad de la tabla, no del número de elementos almacenados. ¡Entonces una tabla cargada al 10% de la capacidad tardará aproximadamente 10 veces más en iterarse que una lista enlazada con los mismos elementos!

Parece que todo lo siguiente puede ser cierto:

Tus llaves son cuerdas.
Los insertos se hacen una vez.
Las búsquedas se realizan con frecuencia.
El número de pares clave-valor es relativamente pequeño (digamos, menos de una K o más).

De ser así, podría considerar una lista ordenada sobre cualquiera de estas otras estructuras. Esto funcionaría peor que los demás durante las inserciones, ya que una lista ordenada es O (N) en la inserción, frente a O (1) para una lista vinculada o tabla hash, y O (log ₂ N) para un árbol binario equilibrado. Pero las búsquedas en una lista ordenada pueden ser más rápidas que cualquiera de estas otras estructuras (explicaré esto en breve), por lo que puede llegar a la cima. Además, si realiza todas sus inserciones a la vez (o no requiere búsquedas hasta que todas las inserciones estén completas), puede simplificar las inserciones en O (1) y hacer una clasificación mucho más rápida al final. Además, una lista ordenada utiliza menos memoria que cualquiera de estas otras estructuras, pero la única forma en que esto probablemente importará es si tiene muchas listas pequeñas. Si tiene una o varias listas grandes, es probable que una tabla hash supere una lista ordenada.

¿Por qué las búsquedas pueden ser más rápidas con una lista ordenada? Bueno, está claro que es más rápido que una lista vinculada, con el tiempo de búsqueda O (N) de este último. Con un árbol binario, las búsquedas solo permanecen O (log ₂ N) si el árbol permanece perfectamente equilibrado. Mantener el árbol equilibrado (rojo-negro, por ejemplo) se suma a la complejidad y al tiempo de inserción. Además, con las listas vinculadas y los árboles binarios, cada elemento es un nodo ¹ asignado por separado, lo que significa que tendrá que eliminar los punteros y probablemente saltar a direcciones de memoria potencialmente muy diferentes, aumentando las posibilidades de que falte un caché.

En cuanto a las tablas hash, probablemente debería leer algunas otras preguntas aquí en , pero los principales puntos de interés aquí son:

Una tabla hash puede degenerar a O (N) en el peor de los casos.
El costo del hashing no es cero, y en algunas implementaciones puede ser significativo, particularmente en el caso de cadenas.
Al igual que en las listas vinculadas y los árboles binarios, cada entrada es un nodo que almacena más que solo clave y valor, también asignada por separado en algunas implementaciones, por lo que utiliza más memoria y aumenta las posibilidades de que falte un caché.

Por supuesto, si realmente te importa cómo funcionará alguna de estas estructuras de datos, debes probarlas. Debería tener pocos problemas para encontrar buenas implementaciones de cualquiera de estos para la mayoría de los lenguajes comunes. No debería ser demasiado difícil arrojar algunos de sus datos reales en cada una de estas estructuras de datos y ver cuál funciona mejor.

_{Es posible que una implementación preasigne una matriz de nodos, lo que ayudaría con el problema de falta de memoria caché.} _{No he visto esto en ninguna implementación real de listas vinculadas o árboles binarios (no es que haya visto a todos, por supuesto), aunque ciertamente podría hacer el suyo propio.} _{Sin embargo, todavía tendría una posibilidad ligeramente mayor de error de caché, ya que los objetos del nodo serían necesariamente más grandes que los pares clave / valor.}

Se aplican las compensaciones estándar entre estas estructuras de datos.

Árboles binarios
- complejidad media para implementar (suponiendo que no pueda obtenerlos de una biblioteca)
- las inserciones son O (logN)
- las búsquedas son O (logN)
Listas enlazadas (sin clasificar)
- baja complejidad para implementar
- los insertos son O (1)
- las búsquedas son O (N)
Tablas hash
- alta complejidad para implementar
- las inserciones son O (1) en promedio
- las búsquedas son O (1) en promedio

Su caso de uso presumiblemente será "insertar los datos una vez (por ejemplo, el inicio de la aplicación) y luego realizar muchas lecturas, pero pocas, si hay, otras inserciones".

Por lo tanto, debe usar un algoritmo que sea rápido para buscar la información que necesita.

Por lo tanto, creo que HashTable es el algoritmo más adecuado para usar, ya que simplemente genera un hash de su objeto clave y lo usa para acceder a los datos de destino: es O (1). Los otros son O (N) (Listas vinculadas de tamaño N - tiene que recorrer la lista una a la vez, un promedio de N / 2 veces) y O (registrar N) (Árbol binario - reduce a la mitad el espacio de búsqueda con cada iteración, solo si el árbol está equilibrado, por lo que esto depende de su implementación, un árbol desequilibrado puede tener un rendimiento significativamente peor).

Solo asegúrese de que haya suficientes espacios (cubos) en la tabla Hash para sus datos (Re, comentario de Soraz en esta publicación). La mayoría de las implementaciones de framework (Java, .NET, etc.) serán de una calidad que no tendrá que preocuparse por las implementaciones.

¿Hiciste un curso sobre estructuras de datos y algoritmos en la universidad?

Un par de cosas para tener en cuenta.

Los árboles binarios solo tienen una búsqueda O (log n) e insertan complejidad si el árbol está equilibrado . Si sus símbolos se insertan de una manera bastante aleatoria, esto no debería ser un problema. Si se insertan en orden, construirás una lista vinculada. (Para su aplicación específica, no deberían estar en ningún tipo de orden, por lo que debería estar bien.) Si existe la posibilidad de que los símbolos sean demasiado ordenados, un Árbol Red-Black es una mejor opción.
Las tablas hash le dan a O (1) complejidad promedio de inserción y búsqueda, pero también hay una advertencia aquí. Si su función de hash es mala (y me refiero a muy mala), podría terminar construyendo una lista vinculada aquí también. Sin embargo, cualquier función razonable de hash de cadena debería funcionar, por lo que esta advertencia es solo para asegurarse de que sea consciente de que podría suceder. Debería poder probar que su función hash no tiene muchas colisiones sobre su rango esperado de entradas, y estará bien. Otro inconveniente menor es si está usando una tabla hash de tamaño fijo. La mayoría de las implementaciones de tablas hash crecen cuando alcanzan un cierto tamaño (factor de carga para ser más precisos, ver here para más detalles). Esto es para evitar el problema que tiene cuando inserta un millón de símbolos en diez cubos. Eso solo lleva a diez listas vinculadas con un tamaño promedio de 100,000.
Solo usaría una lista vinculada si tuviera una tabla de símbolos realmente corta. Es más fácil de implementar, pero el mejor rendimiento de casos para una lista vinculada es el peor de los casos para sus otras dos opciones.

Esta pregunta pasa por los diferentes contenedores en C #, pero son similares en cualquier idioma que use.