c - examples - hash table java
Cuadros hash encadenados vs. Cuadros hash de direcciones abiertas (4)
Dado que se brinda una excelente explicación, simplemente agregaría visualizaciones tomadas de CLRS para una mayor ilustración:
¿Alguien puede explicar las principales diferencias entre (ventajas / desventajas) las dos implementaciones?
Para una biblioteca, ¿qué implementación se recomienda?
Mi comprensión (en términos simples) es que ambos métodos tienen pros y contras, aunque la mayoría de las bibliotecas usan la estrategia de encadenamiento.
Método de encadenamiento:
Aquí la matriz de tablas hash se asigna a una lista vinculada de elementos. Esto es eficiente si el número de colisiones es bastante pequeño. El peor de los casos es O(n) donde n es el número de elementos en la tabla.
Direccionamiento abierto con sonda lineal:
Aquí cuando ocurre la colisión, avance al siguiente índice hasta que encontremos un punto abierto. Por lo tanto, si el número de colisiones es bajo, esto es muy rápido y eficiente en el uso del espacio. La limitación aquí es que el número total de entradas en la tabla está limitado por el tamaño de la matriz. Este no es el caso con el encadenamiento.
Hay otro enfoque que es Encadenamiento con árboles de búsqueda binarios . En este enfoque, cuando se produce la colisión, se almacenan en el árbol de búsqueda binaria en lugar de la lista vinculada. Por lo tanto, el peor de los casos aquí sería O(log n) . En la práctica, este enfoque es más adecuado cuando hay una distribución extremadamente no uniforme.
Si la cantidad de elementos que se insertarán en una tabla hash no se conoce cuando se crea la tabla, la tabla hash encadenada es preferible para abrir el direccionamiento.
El aumento del factor de carga (número de elementos / tamaño de la tabla) causa importantes penalizaciones de rendimiento en las tablas hash direccionadas abiertas, pero el rendimiento se degrada solo linealmente en las tablas hash encadenadas.
Si se trata de poca memoria y desea reducir el uso de la memoria, busque el direccionamiento abierto. Si no está preocupado por la memoria y quiere velocidad, busque tablas hash encadenadas.
En caso de duda, utilice tablas hash encadenadas. Agregar más datos de los anticipados no hará que el rendimiento se ralentice.
El artículo de Wikipedia sobre tablas hash ofrece una mejor explicación y visión general de los diferentes esquemas de tabla hash que la gente ha usado de lo que puedo imaginar. De hecho, probablemente sea mejor leer ese artículo que hacer la pregunta aquí. :)
Eso dijo ...
Una tabla hash encadenada se indexa en una matriz de punteros a los encabezados de las listas vinculadas. Cada celda de la lista vinculada tiene la clave para la cual fue asignada y el valor que se insertó para esa clave. Cuando quiere buscar un elemento particular desde su clave, el hash de la clave se usa para determinar qué lista vinculada seguir, y luego esa lista en particular se atraviesa para encontrar el elemento que está buscando. Si más de una clave en la tabla hash tiene el mismo hash, entonces tendrá listas vinculadas con más de un elemento.
La desventaja del hashing encadenado es tener que seguir punteros para buscar listas enlazadas. Lo bueno es que las tablas hash encadenadas solo se vuelven linealmente más lentas a medida que aumenta el factor de carga (la proporción de elementos en la tabla hash a la longitud de la matriz del cubo), incluso si se eleva por encima de 1.
Una tabla hash de direccionamiento abierto indiza en una matriz de punteros a pares de (clave, valor). Utiliza el valor hash de la clave para calcular qué ranura de la matriz mirar primero. Si más de una clave en la tabla hash tiene el mismo hash, entonces utiliza algún esquema para decidir en otro espacio en el que buscar. Por ejemplo, el sondeo lineal es cuando mira la siguiente ranura después de la elegida, y luego la siguiente ranura después de esa, y así sucesivamente hasta que encuentre una ranura que coincida con la clave que está buscando, o golpee una casilla vacía. ranura (en cuyo caso la clave no debe estar allí).
El direccionamiento abierto suele ser más rápido que el hash encadenado cuando el factor de carga es bajo porque no es necesario seguir los punteros entre los nodos de la lista. Se vuelve muy, muy lento si el factor de carga se acerca a 1, porque terminas teniendo que buscar a través de muchas de las ranuras en la matriz de cubetas antes de encontrar la clave que estabas buscando o una ranura vacía. Además, nunca puede tener más elementos en la tabla hash que entradas en la matriz de cubetas.
Para lidiar con el hecho de que todas las tablas hash al menos se vuelven más lentas (y en algunos casos realmente se rompen por completo) cuando su factor de carga se aproxima a 1, las prácticas implementaciones de la tabla hash hacen que el conjunto de cubos sea más grande (asignando un nuevo conjunto de cubos y copiando elementos de la anterior en la nueva, luego liberando la anterior) cuando el factor de carga supera un cierto valor (generalmente alrededor de 0.7).
Hay muchas variaciones en todo lo anterior. Nuevamente, por favor vea el artículo de wikipedia, realmente es bastante bueno.
Para una biblioteca que debe ser utilizada por otras personas, recomiendo experimentar. Dado que generalmente son bastante cruciales para el rendimiento, generalmente es mejor utilizar la implementación de otra persona de una tabla hash que ya se ha ajustado cuidadosamente. Hay muchas implementaciones de tablas hash con licencia BSD, LGPL y GPL de fuente abierta.
Si estás trabajando con GTK, por ejemplo, entonces encontrarás que hay una buena tabla hash en GLib .