Que es más rápido para buscar un elemento en una tabla hash o en una lista ordenada?

Question

Que es más rápido para buscar un elemento en una tabla hash o en una lista ordenada?

Answer 1

Algoritmo complejidad es una buena cosa para saber y tablas hash son conocidos por ser O (1) , mientras que un vector ordenado (en su caso, supongo que es mejor utilizar una matriz ordenada de una lista ) proporcionará O (log n) tiempo de acceso.

Sin embargo, usted debe saber que la notación complejidad le da el tiempo de acceso para N ir al infinito. Eso significa que si usted sabe que sus datos seguirán creciendo , la notación complejidad le da alguna pista sobre el algoritmo para elegir.

Cuando se sabe que sus datos serán mantener una longitud bastante bajo: por ejemplo con sólo unas pocas entradas en la matriz / tabla hash, debe ir con su reloj y medida. Así que tener una prueba.

Por ejemplo, en otro problema: la clasificación de una matriz. Para unas pocas entradas burbuja especie mientras que O (N ^ 2) puede ser más rápido que .. el tipo rápida, mientras que es O (N log N) .

Además, de acuerdo a otras respuestas, y dependiendo de su artículo, usted debe tratar de encontrar la mejor función hash para la instancia de tabla hash. De lo contrario puede conducir a la mala actuación dramática para las operaciones de búsqueda en su tabla hash (como se señaló en la respuesta de Hank Gay).

Editar: Echa un vistazo a este artículo para entender el significado de la notación O grande .

Answer 2

Suponiendo que por 'lista ordenada' que quiere decir 'al azar de ruedas, la recogida clasificada'. Una lista tiene la propiedad de que sólo se puede atravesarlo elemento por elemento, lo que se traducirá en una complejidad de O (N).

La forma más rápida de encontrar un elemento en una colección ordenada es indexable por búsqueda de N-ario, O (logN), mientras que una tabla hash sin collissions tiene un encontrar complejidad de O (1).

Answer 3

A menos que el algoritmo de hash es muy lenta (y / o mala), la tabla hash será más rápido.

ACTUALIZACIÓN: Como comentaristas han señalado, también podría estar recibiendo el rendimiento sea menor de demasiadas colisiones no porque el algoritmo de hash es mala, sino simplemente porque la tabla hash no es lo suficientemente grande. La mayoría de las implementaciones de la biblioteca (al menos en lenguajes de alto nivel) crecerán automáticamente su tabla hash detrás de las escenas-que causarán más lento de lo esperado, el rendimiento en el inserto que desencadena el crecimiento, pero si usted está rodando su propio, es definitivamente algo a tener en cuenta.

Answer 4

El get operación en un SortedList es O(log n) mientras que la misma operación e una tabla Hash es O(1).Así, normalmente, el HashTable sería mucho más rápido.Pero esto depende de una serie de factores:

• El tamaño de la lista
• El rendimiento del algoritmo de hash
• El número de colisiones / calidad el algoritmo de hash

Answer 5

Todo depende de la cantidad de datos que se han almacenado.

Asumiendo que tiene suficiente memoria para lanzar en él (lo que la tabla hash es lo suficientemente grande), la tabla hash se localice a los datos de destino en una cantidad fija de tiempo, pero la necesidad de calcular el hash agregarán algunos (también fija ) de arriba.

Búsqueda en una lista ordenada no tendrá que hash encima, pero el tiempo necesario para hacer el trabajo de realidad localizar los datos de destino aumentará a medida que crece la lista.

Así que, en general, una lista ordenada generalmente será más rápido para los pequeños conjuntos de datos. (Por muy pequeños conjuntos de datos que se cambian con frecuencia y / o buscados, con poca frecuencia un un lista ordenada puede ser incluso más rápido, ya que evita la sobrecarga de hacer eso.) A medida que el conjunto de datos se hace grande, el crecimiento del tiempo de búsqueda de la lista eclipsa la sobrecarga fija de algoritmos hash y la tabla hash se vuelve más rápido.

Cuando ese punto de interrupción se va a variar dependiendo de la tabla de hash específica y ordenados lista de búsqueda de implementaciones. Ejecutar pruebas y comparar el desempeño en una serie de datos por lo general de tamaño Sets para ver lo que van a actuar mejor en su caso particular. (O, si el código ya se ejecuta "lo suficientemente rápido", no. Sólo tiene que utilizar lo que es más cómodo y no se preocupe por la optimización de algo que no necesita ser optimizado.)

Answer 6

En algunos casos, depende del tamaño de la colección (y, en menor grado, los detalles de implementación). Si la lista es muy pequeño, tal vez 5-10 artículos, supongo que la lista sería más rápido. De lo contrario xtofl tiene razón.

Answer 7

HashTable sería más eficiente para la lista que contiene más de 10 unidades. Si la lista tiene menos de 10 unidades, la sobrecarga debida a hash algo será más.

En caso de que necesite un diccionario rápido, pero también es necesario para mantener los elementos de una manera ordenada utilizar el OrderedDictionary. (.Net 2.0 en adelante)