hashtable - transformacion - ¿Cuál es más rápido para encontrar un elemento en una tabla hash o en una lista ordenada?
transformacion hash (7)
¿Cuál es más rápido para encontrar un elemento en una tabla hash o en una lista ordenada?
A menos que el algoritmo de hash sea extremadamente lento (y / o malo), la tabla hash será más rápida.
ACTUALIZACIÓN: como los comentaristas han señalado, también podría estar obteniendo un rendimiento degradado debido a 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 lenguajes de alto nivel) aumentarán automáticamente tu tabla hash detrás de escena, lo que provocará un rendimiento más lento del esperado en el inserto que desencadena el crecimiento, pero si lo haces solo, definitivamente es algo considerar.
Depende completamente de la cantidad de datos que haya almacenado.
Suponiendo que tiene suficiente memoria para lanzarle (de modo que la tabla hash es lo suficientemente grande), la tabla hash ubicará los datos de destino en un tiempo fijo, pero la necesidad de calcular el hash agregará cierta sobrecarga (también fija).
La búsqueda en una lista ordenada no tendrá esa sobrecarga de hash, pero el tiempo requerido para realizar el trabajo de localización real de los datos de destino aumentará a medida que la lista crezca.
Entonces, 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 con frecuencia y / o se buscan con poca frecuencia, una lista no ordenada puede ser incluso más rápida, ya que evita la sobrecarga de hacer la clasificación). 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 hash, y la tabla hash se vuelve más rápida.
El lugar donde se encuentre ese punto de interrupción variará según la tabla hash específica y las implementaciones de búsqueda ordenada por lista. Ejecute pruebas y evalúe 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 hagas. Solo usa el que te resulte más cómodo y no te preocupes por optimizar algo que no necesita ser optimizado).
En algunos casos, depende del tamaño de la colección (y, en menor medida, de los detalles de la implementación). Si su lista es muy pequeña, quizás de 5 a 10 elementos, supongo que la lista sería más rápida. De lo contrario, xtofl lo tiene bien.
Es bueno saber la complejidad del algoritmo, y se sabe que las tablas hash son O (1) mientras que un vector ordenado (en su caso, creo que es mejor usar una matriz ordenada que una lista) proporcionará tiempo de acceso O (log n) .
Pero debes saber que la notación de complejidad te 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á algunas pistas sobre el algoritmo que debe elegir.
Cuando sepa que sus datos mantendrán una longitud bastante baja: por ejemplo, al tener solo unas pocas entradas en su matriz / tabla hash, debe ir con su reloj y su medida. Así que hazte una prueba.
Por ejemplo, en otro problema: ordenar una matriz. Para algunas entradas, la ordenación de burbuja mientras que O (N ^ 2) puede ser más rápida que ... la ordenación rápida, mientras que es O (n log n) .
Además, de acuerdo con otras respuestas, y dependiendo de su elemento, debe intentar encontrar la mejor función hash para su instancia de tabla hash. De lo contrario, puede llevar a un mal rendimiento dramático para la búsqueda en su tabla hash (como se señaló en la respuesta de Hank Gay).
Edición: Eche un vistazo a este artículo para comprender el significado de la notación Big O.
HashTable sería más eficiente para listas que contengan más de 10 elementos. Si la lista tiene menos de 10 elementos, la sobrecarga debida al hashing algo será mayor.
En caso de que necesite un diccionario rápido, pero también necesita mantener los artículos ordenados, utilice el OrderedDictionary. (.Net 2.0 en adelante)
Suponiendo que por ''lista ordenada'' usted quiere decir ''colección ordenada, accesible al azar''. Una lista tiene la propiedad de que solo puede atravesarla elemento por elemento, lo que resultará en una complejidad O (N).
La forma más rápida de encontrar un elemento en una colección indexable ordenada es mediante la búsqueda N-aria, O (logN), mientras que una tabla hash sin colisiones tiene una complejidad de búsqueda de O (1).
La operación de get en una lista SortedList es O(log n) mientras que la misma operación que HashTable es O(1) . Entonces, normalmente , el HashTable sería mucho más rápido. Pero esto depende de una serie de factores:
- El tamaño de la lista.
- Rendimiento del algoritmo hash
- Número de colisiones / calidad del algoritmo hash