Hashing abierto (encadenamiento separado):
En el hash abierto, las claves se almacenan en listas vinculadas adjuntas a las celdas de una tabla hash.
Hash cerrado (direccionamiento abierto):
En hash cerrado, todas las claves se almacenan en la propia tabla hash sin el uso de listas vinculadas.
No puedo entender por qué se llaman abiertos, cerrados y separados. ¿Alguien puede explicarlo?
Respuestas:
El uso de "cerrado" frente a "abierto" refleja si estamos o no encerrados en el uso de una determinada posición o estructura de datos (esta es una descripción extremadamente vaga, pero es de esperar que el resto ayude).
Por ejemplo, "abrir" en "direccionamiento abierto" nos dice que el índice (también conocido como dirección) en el que se almacenará un objeto en la tabla hash no está completamente determinado por su código hash. En cambio, el índice puede variar según lo que ya esté en la tabla hash.
El "cerrado" en "hash cerrado" se refiere al hecho de que nunca abandonamos la tabla hash; cada objeto se almacena directamente en un índice en la matriz interna de la tabla hash. Tenga en cuenta que esto solo es posible mediante el uso de algún tipo de estrategia de direccionamiento abierto. Esto explica por qué "hash cerrado" y "direccionamiento abierto" son sinónimos.
Compare esto con el hash abierto: en esta estrategia, ninguno de los objetos se almacena realmente en la matriz de la tabla hash; en lugar de eso, una vez que un objeto es hash, se almacena en una lista separada de la matriz interna de la tabla hash. "abierto" se refiere a la libertad que obtenemos al dejar la tabla hash y usar una lista separada. Por cierto, la "lista separada" sugiere por qué el hash abierto también se conoce como "encadenamiento separado".
En resumen, "cerrado" siempre se refiere a algún tipo de garantía estricta, como cuando garantizamos que los objetos siempre se almacenan directamente dentro de la tabla hash (hash cerrado). Entonces, lo contrario de "cerrado" es "abierto", por lo que si no tiene tales garantías, la estrategia se considera "abierta".
fuente
Tiene una matriz que es la "tabla hash".
En Open Hashing, cada celda de la matriz apunta a una lista que contiene las colisiones. El hash ha producido el mismo índice para todos los elementos de la lista vinculada.
En Hashing cerrado, usa solo una matriz para todo. Almacena las colisiones en la misma matriz. El truco consiste en utilizar alguna forma inteligente de saltar de una colisión a otra hasta que encuentre lo que busca. Y haz esto de una manera reproducible / determinista.
fuente
El nombre de direccionamiento abierto se refiere al hecho de que la ubicación ("dirección") del elemento no está determinada por su valor hash. (Este método también se llama hash cerrado).
En el encadenamiento separado , cada depósito es independiente y tiene algún tipo de ADT (lista, árboles de búsqueda binaria, etc.) de entradas con el mismo índice. En una buena tabla hash, cada cubeta tiene cero o una entrada, porque necesitamos operaciones de orden O (1) para insertar, buscar, etc.
Este es un ejemplo de encadenamiento separado usando C ++ con una función hash simple usando el operador mod (claramente, una función hash incorrecta)
fuente