Hola
En una estructura de open hashing la idea es que dos elecciones esencialmente aseguren O(1) promedio para altas, bajas y consultas en una colacción (conjunto, tabla/mapping, etc). Por un lado la función de hash debería tener distribución uniforme (asignar los elementos en las posiciones con probabilidad similar) y la elección de la cantidad esperada de elementos no debe superar en mucho el tamaño del arreglo (que normalmente se define en la operación crear/vacío).
Si las condiciones anteriores se cumplen, "en promedio" en cada lista del arreglo se tiene un elemento. Esto es, las listas deberían ser muy cortas en cada posición del arreglo, luego no es muy relevante pensar en estructuras complejas de listas u otras estructuras de datos en vez de listas. Las listas que tienen siempre una cabecera lo que permiten es tratar de manera uniforme las opciones de actualización; no obstante esto no es necesario si se consideran los casos adecuados. Tener en cuenta que en una colección no hay orden posicional, razón por la cual el orden de los nodos dentro de cada lista no es relevante.
Saludos, Carlos
En una estructura de open hashing la idea es que dos elecciones esencialmente aseguren O(1) promedio para altas, bajas y consultas en una colacción (conjunto, tabla/mapping, etc). Por un lado la función de hash debería tener distribución uniforme (asignar los elementos en las posiciones con probabilidad similar) y la elección de la cantidad esperada de elementos no debe superar en mucho el tamaño del arreglo (que normalmente se define en la operación crear/vacío).
Si las condiciones anteriores se cumplen, "en promedio" en cada lista del arreglo se tiene un elemento. Esto es, las listas deberían ser muy cortas en cada posición del arreglo, luego no es muy relevante pensar en estructuras complejas de listas u otras estructuras de datos en vez de listas. Las listas que tienen siempre una cabecera lo que permiten es tratar de manera uniforme las opciones de actualización; no obstante esto no es necesario si se consideran los casos adecuados. Tener en cuenta que en una colección no hay orden posicional, razón por la cual el orden de los nodos dentro de cada lista no es relevante.
Saludos, Carlos