Hashing fusionado

El hash combinado es una técnica para evitar colisiones cuando hay datos de tamaño fijo. Es una combinación de enstringmiento separado y direccionamiento abierto . Utiliza el concepto de direccionamiento abierto (sondeo lineal) para encontrar el primer lugar vacío para el elemento en colisión desde la parte inferior de la tabla hash y el concepto de enstringmiento separado para vincular los elementos en colisión entre sí a través de punteros. La función hash utilizada es h=(key)%(total number of keys) . Dentro de la tabla hash, cada Node tiene tres campos:

• h(clave): El valor de la función hash para una clave.
• Datos: La clave en sí.
• Siguiente: El enlace a los siguientes elementos en colisión.

Las operaciones básicas del hash Coalesced son:

1. INSERTAR (clave): la operación de inserción inserta la clave de acuerdo con el valor hash de esa clave si ese valor hash en la tabla está vacío; de lo contrario, la clave se inserta en el primer lugar vacío desde la parte inferior de la tabla hash y la dirección de este vacío el lugar se mapea en el campo SIGUIENTE del Node señalador anterior de la string. (Explicado en el ejemplo a continuación).
2. ELIMINAR (clave): la clave, si está presente, se elimina. Además, si el Node que se eliminará contiene la dirección de otro Node en la tabla hash, esta dirección se asigna en el campo SIGUIENTE del Node que apunta al Node que se eliminará
3. SEARCH(clave): Devuelve Verdadero si la clave está presente, de lo contrario devuelve Falso.

La complejidad del mejor caso de todas estas operaciones es O(1) y la complejidad del peor caso es O(n) donde n es el número total de claves. Es mejor que el enstringmiento separado porque inserta el elemento en colisión en la memoria de la tabla hash solo en lugar de crear una nueva lista enlazada como en un enstringmiento separado.
Ilustración:
Ejemplo :

n = 10
Input : {20, 35, 16, 40, 45, 25, 32, 37, 22, 55}

Función hash

h(key) = key%10

Pasos:

1. Inicialmente, la tabla hash vacía se crea con todos los campos SIGUIENTE inicializados con valores NULL y h (clave) que van de 0 a 9.

valor hash	Datos	próximo
0	–	NULO
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	–	NULO
6	–	NULO
7	–	NULO
8	–	NULO
9	–	NULO

2. Comencemos con la inserción de 20, como h(20)=0 y el índice 0 está vacío, por lo que insertamos 20 en el índice 0.

valor hash	Datos	próximo
0	20	NULO
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	–	NULO
6	–	NULO
7	–	NULO
8	–	NULO
9	–	NULO

3. El siguiente elemento que se insertará es 35, h(35)=5 y el quinto índice está vacío, por lo que insertamos 35 allí.

valor hash	Datos	próximo
0	20	NULO
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	35	NULO
6	–	NULO
7	–	NULO
8	–	NULO
9	–	NULO

4. A continuación tenemos 16, h(16)=6 que está vacío, por lo que 16 se inserta en el valor de índice 6.

valor hash	Datos	próximo
0	20	NULO
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	35	NULO
6	dieciséis	NULO
7	–	NULO
8	–	NULO
9	–	NULO

5. Ahora tenemos que insertar 40, h(40)=0 que ya está ocupado, por lo que buscamos el primer bloque vacío desde abajo y lo insertamos allí, es decir, 9 valores de índice. También la dirección de este Node recién insertado (de la dirección queremos decir valor de índice de un Node), es decir, (9) se inicializa en el siguiente campo del Node de valor de índice 0.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	35	NULO
6	dieciséis	NULO
7	–	NULO
8	–	NULO
9	40	NULO

6. Para insertar 45, h (45) = 5 que está ocupado, por lo que nuevamente buscamos el bloque vacío desde la parte inferior, es decir, valor de índice 8 y asignamos la dirección de este Node recién insertado, es decir (8) al campo Siguiente del Node de valor de índice 5 es decir, en el siguiente campo de key=35.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	35	8
6	dieciséis	NULO
7	–	NULO
8	45	NULO
9	40	NULO

7. Junto a insertar 25, h(25)=5 está ocupado, así que busque el primer bloque vacío desde abajo, es decir, el valor del índice 7 e inserte 25 allí. Ahora es importante tener en cuenta que la dirección de este nuevo Node no se puede mapear en el quinto Node de valor de índice que ya apunta a algún otro Node. Para insertar la dirección del nuevo Node, debemos seguir la string de enlace desde el quinto Node de índice hasta que obtengamos NULL en el siguiente campo y asignar la dirección del nuevo Node al siguiente campo de ese Node, es decir, desde el quinto Node de índice vamos al octavo Node de índice. que contiene NULL en el siguiente campo, por lo que insertamos la dirección del nuevo Node, es decir (7) en el siguiente campo del octavo Node de índice.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	–	NULO
3	–	NULO
4	–	NULO
5	35	8
6	dieciséis	NULO
7	25	NULO
8	45	7
9	40	NULO

8. Para insertar 32, h(32)=2, que está vacío, así que inserte 32 en el segundo valor de índice.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	32	NULO
3	–	NULO
4	–	NULO
5	35	8
6	dieciséis	NULO
7	25	NULO
8	45	7
9	40	NULO

9. Para insertar 37, h(37)=7 que está ocupado, así que busque el primer bloque libre desde abajo, que es el cuarto valor de índice. Así que inserte 37 en el cuarto valor de índice y copie la dirección de este Node en el siguiente campo del Node de valor de índice 7.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	32	NULO
3	–	NULO
4	37	NULO
5	35	8
6	dieciséis	NULO
7	25	4
8	45	7
9	40	NULO

10. Para insertar 22, h(22)=2 que está ocupado, insértelo en el tercer valor de índice y asigne la dirección de este Node en el siguiente campo del segundo Node de valor de índice.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	32	3
3	22	NULO
4	37	NULO
5	35	8
6	dieciséis	NULO
7	25	4
8	45	7
9	40	NULO

11. Finalmente, para insertar 55 h(55)=5 que está ocupado y el único espacio vacío es el primer valor de índice, así que inserte 55 allí. Ahora, nuevamente, para mapear la dirección de este nuevo Node, debemos seguir la string que comienza desde el Node de valor de índice 5 hasta que obtengamos NULL en el siguiente campo, es decir, desde el índice 5-> índice 8-> índice 7-> índice 4 que contiene NULL en Siguiente e insertamos la dirección del Node recién insertado en el cuarto Node de valor de índice.

valor hash	Datos	próximo
0	20	9
1	55	NULO
2	32	3
3	22	NULO
4	37	1
5	35	8
6	dieciséis	NULO
7	25	4
8	45	7
9	40	NULO

El proceso de eliminación es simple, por ejemplo:
Caso 1: Para eliminar la clave = 37, primero busque 37. Si está presente, simplemente elimine el valor de los datos y si el Node contiene alguna dirección en el siguiente campo y el Node que se eliminará, es decir, 37 es señalado por otro Node (es decir, clave = 25), luego copie esa dirección en el siguiente campo de 37 al siguiente campo del Node que apunta a 37 (es decir, clave = 25) e inicialice el campo SIGUIENTE de clave = 37 como NULL nuevamente y borre la clave=37.

valor hash	Datos	próximo
0	20	9
1	55	NULO
2	32	3
3	22	NULO
4	–	NULO
5	35	8
6	dieciséis	NULO
7	25	1
8	45	7
9	40	NULO

Caso 2: si la clave que se eliminará es 35, que no está apuntada por ningún otro Node, entonces tenemos que tirar de la string unida al Node que se eliminará, es decir, 35, un paso atrás y marcar el último valor de la string en NULL nuevamente.

valor hash	Datos	próximo
0	20	9
1	–	NULO
2	32	3
3	22	NULO
4	–	NULO
5	45	8
6	dieciséis	NULO
7	55	NULO
8	25	7
9	40	NULO