Tenemos la solución a esta duda, al menos eso pensamos. Si continuas con dudas dínoslo y con placer te responderemos
Solución:
El artículo de Wikipedia sobre tablas hash brinda una explicación y una descripción general claramente mejores de los diferentes esquemas de tablas hash que la gente ha usado de lo que puedo imaginar. De hecho, probablemente sea mejor que lea ese artículo que hacer la pregunta aquí. 🙂
Dicho esto…
Una tabla hash encadenada se indexa en un array de punteros a los encabezados de listas enlazadas. Cada celda de la lista enlazada tiene el key para el que se asignó y el valor que se insertó para ese key. Cuando desee buscar un elemento en particular de su keylos keyEl hash de se usa para determinar qué lista vinculada seguir, y luego esa lista en particular se recorre para encontrar el elemento que está buscando. si mas de uno key en la tabla hash tiene el mismo hash, entonces tendrás listas enlazadas con más de un elemento.
La desventaja del hashing encadenado es tener que seguir punteros para buscar listas enlazadas. La ventaja es que las tablas hash encadenadas solo se vuelven linealmente más lentas a medida que el factor de carga (la proporción de elementos en la tabla hash a la longitud del cubo array) aumenta, incluso si se eleva por encima de 1.
Una tabla hash de direccionamiento abierto se indexa en un array de punteros a pares de (key, valor). usas el keyel valor hash para calcular qué ranura en el array para mirar primero. si mas de uno key en la tabla hash tiene el mismo hash, luego usa algún esquema para decidir en otra ranura para buscar en su lugar. Por ejemplo, el sondeo lineal consiste en mirar 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 key estás buscando, o golpeas una ranura vacía (en cuyo caso el key 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 tiene que seguir los punteros entre los nodos de la lista. Se vuelve muy, muy lento si el factor de carga se acerca a 1, porque generalmente termina teniendo que buscar en muchas de las ranuras en el depósito. array antes de encontrar el key que estabas buscando o un espacio vacío. Además, nunca puede tener más elementos en la tabla hash que entradas en el depósito. array.
Para lidiar con el hecho de que todas las tablas hash al menos se vuelven más lentas (y en algunos casos se rompen por completo) cuando su factor de carga se acerca a 1, las implementaciones prácticas de tablas hash hacen que el cubo array más grande (asignando un nuevo cubo arrayy copiando elementos del anterior al nuevo, y luego liberando el anterior) cuando el factor de carga supera un cierto valor (normalmente alrededor de 0,7).
Hay muchas variaciones en todo lo anterior. Una vez más, consulte el artículo de wikipedia, realmente es bastante bueno.
Para una biblioteca destinada a ser utilizada por otras personas, yo fuertemente recomienda experimentar. Dado que generalmente son bastante cruciales para el rendimiento, generalmente es mejor usar la implementación de otra persona de una tabla hash que ya ha sido cuidadosamente ajustada. Hay muchas implementaciones de tablas hash con licencia BSD, LGPL y GPL de código abierto.
Si está trabajando con GTK, por ejemplo, encontrará que hay una buena tabla hash en GLib.
Dado que se proporciona una excelente explicación, solo agregaría visualizaciones tomadas de CLRS para una ilustración más detallada:
Direccionamiento abierto:
Encadenamiento:
Mi entendimiento (en términos simples) es que ambos métodos tienen ventajas y desventajas, aunque la mayoría de las bibliotecas usan la estrategia de encadenamiento.
Método de encadenamiento:
Aquí las tablas hash array 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 de la tabla.
Direccionamiento abierto con sonda lineal:
Aquí, cuando ocurra la colisión, pasar al siguiente índice hasta que encontremos un lugar abierto. Entonces, si el número de colisiones es bajo, esto es muy rápido y ahorra espacio. La limitación aquí es que el número total de entradas en la tabla está limitado por el tamaño de la array. Este no es el caso con el encadenamiento.
Hay otro enfoque que es Encadenamiento con árboles de búsqueda binarios. En este enfoque, cuando ocurre la colisión, se almacenan en un árbol de búsqueda binario en lugar de una lista enlazada. 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 existe una distribución extremadamente no uniforme.
Nos puedes añadir valor a nuestra información participando con tu experiencia en las anotaciones.