¿Cuál es más rápido para encontrar un elemento en una tabla hash o en una lista ordenada?

Question

¿Cuál es más rápido para encontrar un elemento en una tabla hash o en una lista ordenada?

Answer 1

La complejidad del algoritmo es algo bueno de saber, y se sabe que las tablas hash son 0 (1) mientras que un vector ordenado (en su caso supongo que es mejor usar una matriz ordenada que una lista) proporcionará 0 (log n) tiempo de acceso.

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

Cuando sepa que sus datos se mantendrán bastante cortos: por ejemplo, con solo unas pocas entradas en su matriz/hashtable, debe ir con su reloj y medir. Entonces ten una prueba.

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

También, de acuerdo a otras respuestas, y dependiendo de su item, debes intentar encontrar la mejor función hash para tu instancia de hashtable. De lo contrario, puede llevar a un mal rendimiento dramático para la búsqueda en su hashtable (como se señala en la respuesta de Hank Gay).

Editar: Eche un vistazo a este artículo para comprender the meaning of Big O notation.

Answer 2

A menos que el algoritmo hash sea extremadamente lento (y/o malo), la tabla hash será más rápida.

ACTUALIZACIÓN: como comentaron los comentaristas, también podría estar obteniendo rendimiento degradado por demasiadas colisiones, no porque su algoritmo hash sea malo sino simplemente porque la tabla hash no es lo suficientemente grande. La mayoría de las implementaciones de la biblioteca (al menos en los lenguajes de alto nivel) crecerán automáticamente su hashtable detrás de escena, lo que provocará un rendimiento más lento de lo esperado en la inserción que desencadena el crecimiento, pero si usted está haciendo lo propio, definitivamente es algo considerar.

Answer 3

Suponiendo que por "lista ordenada" se quiere decir "colección ordenada al azar". Una lista tiene la propiedad de que solo se puede atravesar elemento por elemento, lo que dará como resultado una complejidad O (N).

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

Answer 4

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

Answer 5

HashTable sería más eficiente para la lista que contiene más de 10 elementos. Si la lista tiene menos de 10 elementos, la sobrecarga debido a hashing algo será más.

En caso de que necesite un diccionario rápido pero también necesite guardar los artículos de manera ordenada, utilice el OrderedDictionary. (.Net 2.0 en adelante)

Answer 6

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

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

Answer 7

Depende totalmente en la cantidad de datos que ha almacenado.

Suponiendo que tiene memoria suficiente para lanzarla (por lo que la tabla hash es lo suficientemente grande), la tabla hash localizará los datos de destino en un período de tiempo fijo, pero la necesidad de calcular el hash agregará algunos (también fijo) por encima.

Buscar en una lista ordenada no tendrá esa sobrecarga de hashing, pero el tiempo requerido para hacer el trabajo de localizar realmente los datos de destino aumentará a medida que la lista crezca.

Por lo tanto, en general, una lista ordenada generalmente será más rápida para conjuntos de datos pequeños. (Para conjuntos de datos extremadamente pequeños que se cambian frecuentemente y/o se buscan con poca frecuencia, una lista ordenada un puede ser aún más rápida, ya que evita la sobrecarga de hacer el tipo.) A medida que el conjunto de datos se vuelve grande, el crecimiento de la lista el tiempo de búsqueda eclipsa la sobrecarga fija de hash, y la tabla hash se vuelve más rápida.

Donde ese punto de interrupción variará dependiendo de su tabla hash específica y de las implementaciones de búsqueda ordenada. Ejecute pruebas y compare el rendimiento en una serie de conjuntos de datos de tamaño típico para ver cuál funcionará mejor en su caso particular. (O, si el código ya se ejecuta "lo suficientemente rápido", no lo haga. Simplemente use el que le resulte más cómodo y no se preocupe por optimizar algo que no necesite ser optimizado).