Por lo general, una lista ordenada no es algo particularmente útil, y también genera mucho tiempo generarla. Esto se debe a que no puede hacer una búsqueda binaria en una lista: debe comenzar desde el final, porque no puede encontrar el siguiente elemento de la lista sin mirar el puntero (s) dentro del elemento actual. Por lo tanto, su tiempo de búsqueda promedio es O (n).
Una tabla hash, por otro lado, tiene típicamente un tiempo de búsqueda O (1) .
Analicemos los algoritmos más profundamente:
- Paso mucho tiempo pensando en el diseño, por lo que la implementación es terriblemente lenta. ¿Cómo supero este problema?
- ¿Qué es la fuerza bruta?
- Dado un componente fuertemente conectado, ¿puede determinar en tiempo lineal si la eliminación de un solo nodo convierte el SCC en un gráfico acíclico dirigido?
- ¿Qué significa "adherencia del brazo" en los algoritmos de programación de E / S?
- ¿Cuáles son los mejores métodos para el análisis competitivo?
Los pasos para la lista serían, comenzando al final (cabeza si está unida individualmente, cabeza o cola si está doblemente vinculada):
¿El valor del nodo de la lista es igual al elemento de búsqueda?
- Sí: devolver el artículo.
- No: ¿es mayor (menor que) el artículo?
- Sí: devuelve "no encontrado"
- No: ¿estamos al final de la lista?
- Sí: devuelve "no encontrado".
- No: establezca el nodo actual en el siguiente nodo y vaya al paso 1.
Curiosamente, esto no es una mejora en una lista desordenada, ya que las posibilidades de hacer coincidir el elemento, dados N nodos, son 1 / N en cualquier caso.
El algoritmo de una tabla hash es más o menos esto:
Calcule el hash de la clave. Use el valor hash como índice en la tabla hash.
Hay varias opciones sobre qué hacer a continuación, dependiendo de la implementación particular de la tabla hash:
Una tabla hash que usa listas internamente para resolver colisiones hará esto:
Verifique cada elemento en el "contenedor" para ver si coincide. Continúe hasta que se encuentre una coincidencia o se llegue al final de la lista.
Una tabla hash de tamaño fijo tiene un algoritmo para encontrar la siguiente ranura posible:
¿Es este artículo un partido?
Sí: devolver el artículo.
No: calcule la siguiente dirección de la ranura posible
Fuera de las direcciones?
Sí: devuelve "no encontrado"
No: vaya al siguiente espacio posible y salte al paso 1.
Una función hash “perfecta” se construye a partir de un conjunto de valores que ya son completamente conocidos. Se puede crear una función de este tipo que no tendrá colisiones.
Devuelva el artículo en el índice.
Asi que….
La búsqueda en la lista siempre será de O (n). El examen de cada elemento implica una desreferencia de memoria (de la dirección del nodo), una extracción del valor y una comparación.
Para las tablas hash, siempre tenemos que calcular un valor hash. Si bien es constante en el tiempo, ese cálculo generalmente implica un bucle y una operación en una parte de la clave, hasta que la clave completa se procesa en hash. Eso podría tomar el tiempo equivalente de verificar varios elementos de la lista.
Entonces, necesitamos hacer una búsqueda en la tabla. Una tabla bien construida tendrá muy pocas colisiones, y la búsqueda también será una desreferencia de memoria (de la entrada de la tabla), una extracción del valor y una comparación. Si nos encontramos con una colisión, tendremos que desreferenciar la siguiente ubicación y repetir.
Una función hash deficiente podría conducir a un caso degenerado para la implementación que usa listas internamente. Todos los datos en la tabla hash podrían almacenarse en una sola lista, con el resto de la tabla vacía. Eso constituiría una búsqueda O (n) , con la sobrecarga adicional del cálculo de la clave hash.
Del mismo modo, las tablas de tamaño fijo con funciones hash deficientes también podrían degenerar en O (n).
Una lista muy corta tendría un tiempo de búsqueda más rápido que una tabla hash. Supongo que aproximadamente diez elementos antes de que la búsqueda de la tabla hash sea más rápida, principalmente debido al tiempo de generación de la clave hash. Si se tratara de una tabla “perfecta”, la lista “perdería” a la tabla hash en un recuento de elementos inferior.
En conclusión, la tabla hash “ganará” cuando, aproximadamente, la velocidad de cálculo del hash se vuelva más rápida que la velocidad de atravesar la lista.
