Solución:
Las tablas hash tratan las colisiones de dos formas.
Opción 1: Al hacer que cada depósito contenga una lista vinculada de elementos que se han agregado a ese depósito. Esta es la razón por la que una función hash incorrecta puede hacer que las búsquedas en tablas hash sean muy lentas.
Opcion 2: Si las entradas de la tabla hash están todas llenas, la tabla hash puede aumentar la cantidad de depósitos que tiene y luego redistribuir todos los elementos de la tabla. La función hash devuelve un número entero y la tabla hash tiene que tomar el resultado de la función hash y modificarlo contra el tamaño de la tabla de esa manera puede estar seguro de que llegará al cubo. Entonces, al aumentar el tamaño, repetirá y ejecutará los cálculos de módulo que, si tiene suerte, podrían enviar los objetos a diferentes cubos.
Java usa tanto la opción 1 como la 2 en sus implementaciones de tabla hash.
Cuando hablaste de “Hash Table colocará una nueva entrada en el grupo ‘siguiente disponible’ si la nueva entrada clave choca con otra”, estás hablando de la Estrategia de direccionamiento abierto de resolución de colisión de la tabla hash.
Existen varias estrategias para que la tabla hash resuelva una colisión.
El primer tipo de método grande requiere que las claves (o punteros a ellas) se almacenen en la tabla, junto con los valores asociados, que además incluye:
- Encadenamiento separado
- Direccionamiento abierto
- Hash combinado
- Hash de cuco
- Hash de robin hood
- Hash de 2 opciones
- Hash de rayuela
Otro método importante para manejar una colisión es Cambio de tamaño dinámico, que además tiene varias formas:
- Cambiar el tamaño copiando todas las entradas
- Cambio de tamaño incremental
- Teclas monotónicas
EDITAR: lo anterior se tomó prestado de wiki_hash_table, donde debe ir a echar un vistazo para obtener más información.
Hay varias técnicas disponibles para manejar una colisión. Te explicare algunos de ellos
Encadenamiento:
En el encadenamiento usamos índices de matriz para almacenar los valores. Si el código hash del segundo valor también apunta al mismo índice, entonces reemplazamos ese valor de índice con una lista vinculada y todos los valores que apuntan a ese índice se almacenan en la lista vinculada y el índice de la matriz real apunta al encabezado de la lista vinculada. Pero si solo hay un código hash que apunta a un índice de matriz, el valor se almacena directamente en ese índice. Se aplica la misma lógica al recuperar los valores. Esto se usa en Java HashMap / Hashtable para evitar colisiones.
Palpado lineal: Esta técnica se utiliza cuando tenemos más índice en la tabla que los valores a almacenar. La técnica de palpado lineal se basa en el concepto de seguir aumentando hasta encontrar una ranura vacía. El pseudocódigo se ve así:
index = h(k)
while( val(index) is occupied)
index = (index+1) mod n
Técnica de doble hash: En esta técnica usamos dos funciones hash h1 (k) y h2 (k). Si la ranura en h1 (k) está ocupada, entonces la segunda función hash h2 (k) se usa para incrementar el índice. El pseudocódigo se ve así:
index = h1(k)
while( val(index) is occupied)
index = (index + h2(k)) mod n
Las técnicas de sondeo lineal y doble hash son parte de la técnica de direccionamiento abierto y solo se pueden usar si las ranuras disponibles son más que la cantidad de elementos que se agregarán. Se necesita menos memoria que el encadenamiento porque no se usa ninguna estructura adicional aquí, pero es lento debido a que ocurren muchos movimientos hasta que encontramos una ranura vacía. También en la técnica de direccionamiento abierto, cuando un elemento se quita de una ranura, colocamos una lápida para indicar que el elemento se quita de aquí y por eso está vacío.
Para obtener más información, consulte este sitio.