Fondo :
Hay tres operaciones básicas que deben ser compatibles con una tabla hash (o un diccionario):
- Búsqueda (clave): devuelve verdadero si la clave está en la tabla, de lo contrario, falso
- Insertar (clave): agregue el elemento ‘clave’ a la tabla si aún no está presente
- Eliminar (clave): elimina ‘clave’ de la tabla
Las colisiones son muy probables aunque tengamos una mesa grande para guardar las llaves. Usando los resultados de la paradoja del cumpleaños : ¡con solo 23 personas, la probabilidad de que dos personas compartan la misma fecha de nacimiento es del 50%! Hay 3 estrategias generales para resolver colisiones hash:
- Direccionamiento cerrado o enstringmiento : almacene elementos en colisión en una estructura de datos auxiliar como una lista enlazada o un árbol de búsqueda binaria.
- Direccionamiento abierto : permita que los elementos se desborden fuera de su depósito de destino y entren en otros espacios.
Aunque las soluciones anteriores proporcionan un costo de búsqueda esperado como O(1), el costo esperado en el peor de los casos de una búsqueda en Direccionamiento abierto (con sondeo lineal) es Ω(log n) y Θ(log n / log log n) en enstringmiento simple ( Fuente: Standford Lecture Notes ). Para cerrar la brecha entre el tiempo esperado y el tiempo esperado en el peor de los casos, se utilizan dos ideas:
- Hash de opción múltiple : dé a cada elemento múltiples opciones para las posiciones en las que puede residir en la tabla hash
- Hashing de reubicación : permite que los elementos de la tabla hash se muevan después de colocarlos
Hashing de cuco:
Cuckoo hashing aplica la idea de opción múltiple y reubicación juntas y garantiza el tiempo de búsqueda en el peor de los casos O(1).
- Opción múltiple: le damos a una clave dos opciones theh1(key) y h2(key) para residir.
- Reubicación : Puede suceder que h1(clave) y h2(clave) estén preocupados. Esto se resuelve imitando al pájaro cuco: empuja a los demás huevos o crías fuera del nido cuando eclosiona . De manera análoga, insertar una nueva clave en una tabla hash de cuco puede empujar una clave más antigua a una ubicación diferente. Esto nos deja con el problema de reemplazar la llave anterior.
- Si la posición alternativa de la llave anterior está vacante, no hay problema.
- De lo contrario, la clave anterior desplaza a otra clave. Esto continúa hasta que el procedimiento encuentra un puesto vacante o entra en un ciclo. En el caso de un ciclo, se eligen nuevas funciones hash y se ‘rehace’ toda la estructura de datos. Es posible que se necesiten varios refritos antes de que Cuckoo tenga éxito.
Se espera una inserción O(1) (amortizada) con alta probabilidad, incluso considerando la posibilidad de rehashing, siempre que el número de claves se mantenga por debajo de la mitad de la capacidad de la tabla hash, es decir, el factor de carga esté por debajo del 50%.
La eliminación es O(1) en el peor de los casos, ya que requiere la inspección de solo dos ubicaciones en la tabla hash.
Ilustración
Aporte:
{20, 50, 53, 75, 100, 67, 105, 3, 36, 39}
Funciones hash:
h1(key) = key%11 h2(key) = (key/11)%11
Comencemos insertando 20 en su posible posición en la primera tabla determinada por h1(20):
Siguiente: 50
Siguiente: 53 . h1(53) = 9. Pero 20 ya está ahí en 9. Colocamos 53 en la tabla 1 y 20 en la tabla 2 en h2(20)
Siguiente: 75 . h1(75) = 9. Pero 53 ya está ahí en 9. Colocamos 75 en la tabla 1 y 53 en la tabla 2 en h2(53)
Siguiente: 100 . h1(100) = 1.
Siguiente: 67 . h1(67) = 1. Pero 100 ya está allí en 1. Colocamos 67 en la tabla 1 y 100 en la tabla 2
Siguiente: 105 . h1(105) = 6. Pero 50 ya está allí en 6. Colocamos 105 en la tabla 1 y 50 en la tabla 2 en h2(50) = 4. Ahora 53 ha sido desplazado. h1(53) = 9. 75 desplazado: h2(75) = 6.
Siguiente: 3 . h1(3) = 3.
Siguiente: 36 . h1(36) = 3. h2(3) = 0.
Siguiente: 39 . h1(39) = 6. h2(105) = 9. h1(100) = 1. h2(67) = 6. h1(75) = 9. h2(53) = 4. h1(50) = 6. h2 (39) = 3.
Aquí, la nueva clave 39 se desplaza posteriormente en las llamadas recursivas al lugar 105, al que desplazó.
Implementación:
A continuación se muestra la implementación de Cuckoo hash
C++
// C++ program to demonstrate working of Cuckoo
// hashing.
#include<bits/stdc++.h>
// upper bound on number of elements in our set
#define MAXN 11
// choices for position
#define ver 2
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
int hashtable[ver][MAXN];
// Array to store possible positions for a key
int pos[ver];
/* function to fill hash table with dummy value
* dummy value: INT_MIN
* number of hashtables: ver */
void initTable()
{
for (int j=0; j<MAXN; j++)
for (int i=0; i<ver; i++)
hashtable[i][j] = INT_MIN;
}
/* return hashed value for a key
* function: ID of hash function according to which
key has to hashed
* key: item to be hashed */
int hash(int function, int key)
{
switch (function)
{
case 1: return key%MAXN;
case 2: return (key/MAXN)%MAXN;
}
}
/* function to place a key in one of its possible positions
* tableID: table in which key has to be placed, also equal
to function according to which key must be hashed
* cnt: number of times function has already been called
in order to place the first input key
* n: maximum number of times function can be recursively
called before stopping and declaring presence of cycle */
void place(int key, int tableID, int cnt, int n)
{
/* if function has been recursively called max number
of times, stop and declare cycle. Rehash. */
if (cnt==n)
{
printf("%d unpositioned\n", key);
printf("Cycle present. REHASH.\n");
return;
}
/* calculate and store possible positions for the key.
* check if key already present at any of the positions.
If YES, return. */
for (int i=0; i<ver; i++)
{
pos[i] = hash(i+1, key);
if (hashtable[i][pos[i]] == key)
return;
}
/* check if another key is already present at the
position for the new key in the table
* If YES: place the new key in its position
* and place the older key in an alternate position
for it in the next table */
if (hashtable[tableID][pos[tableID]]!=INT_MIN)
{
int dis = hashtable[tableID][pos[tableID]];
hashtable[tableID][pos[tableID]] = key;
place(dis, (tableID+1)%ver, cnt+1, n);
}
else //else: place the new key in its position
hashtable[tableID][pos[tableID]] = key;
}
/* function to print hash table contents */
void printTable()
{
printf("Final hash tables:\n");
for (int i=0; i<ver; i++, printf("\n"))
for (int j=0; j<MAXN; j++)
(hashtable[i][j]==INT_MIN)? printf("- "):
printf("%d ", hashtable[i][j]);
printf("\n");
}
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
void cuckoo(int keys[], int n)
{
// initialize hash tables to a dummy value (INT-MIN)
// indicating empty position
initTable();
// start with placing every key at its position in
// the first hash table according to first hash
// function
for (int i=0, cnt=0; i<n; i++, cnt=0)
place(keys[i], 0, cnt, n);
//print the final hash tables
printTable();
}
/* driver function */
int main()
{
/* following array doesn't have any cycles and
hence all keys will be inserted without any
rehashing */
int keys_1[] = {20, 50, 53, 75, 100, 67, 105,
3, 36, 39};
int n = sizeof(keys_1)/sizeof(int);
cuckoo(keys_1, n);
/* following array has a cycle and hence we will
have to rehash to position every key */
int keys_2[] = {20, 50, 53, 75, 100, 67, 105,
3, 36, 39, 6};
int m = sizeof(keys_2)/sizeof(int);
cuckoo(keys_2, m);
return 0;
}
Java
// Java program to demonstrate working of
// Cuckoo hashing.
import java.util.*;
class GFG
{
// upper bound on number of elements in our set
static int MAXN = 11;
// choices for position
static int ver = 2;
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
static int [][]hashtable = new int[ver][MAXN];
// Array to store possible positions for a key
static int []pos = new int[ver];
/* function to fill hash table with dummy value
* dummy value: INT_MIN
* number of hashtables: ver */
static void initTable()
{
for (int j = 0; j < MAXN; j++)
for (int i = 0; i < ver; i++)
hashtable[i][j] = Integer.MIN_VALUE;
}
/* return hashed value for a key
* function: ID of hash function according to which
key has to hashed
* key: item to be hashed */
static int hash(int function, int key)
{
switch (function)
{
case 1: return key % MAXN;
case 2: return (key / MAXN) % MAXN;
}
return Integer.MIN_VALUE;
}
/* function to place a key in one of its possible positions
* tableID: table in which key has to be placed, also equal
to function according to which key must be hashed
* cnt: number of times function has already been called
in order to place the first input key
* n: maximum number of times function can be recursively
called before stopping and declaring presence of cycle */
static void place(int key, int tableID, int cnt, int n)
{
/* if function has been recursively called max number
of times, stop and declare cycle. Rehash. */
if (cnt == n)
{
System.out.printf("%d unpositioned\n", key);
System.out.printf("Cycle present. REHASH.\n");
return;
}
/* calculate and store possible positions for the key.
* check if key already present at any of the positions.
If YES, return. */
for (int i = 0; i < ver; i++)
{
pos[i] = hash(i + 1, key);
if (hashtable[i][pos[i]] == key)
return;
}
/* check if another key is already present at the
position for the new key in the table
* If YES: place the new key in its position
* and place the older key in an alternate position
for it in the next table */
if (hashtable[tableID][pos[tableID]] != Integer.MIN_VALUE)
{
int dis = hashtable[tableID][pos[tableID]];
hashtable[tableID][pos[tableID]] = key;
place(dis, (tableID + 1) % ver, cnt + 1, n);
}
else // else: place the new key in its position
hashtable[tableID][pos[tableID]] = key;
}
/* function to print hash table contents */
static void printTable()
{
System.out.printf("Final hash tables:\n");
for (int i = 0; i < ver; i++, System.out.printf("\n"))
for (int j = 0; j < MAXN; j++)
if(hashtable[i][j] == Integer.MIN_VALUE)
System.out.printf("- ");
else
System.out.printf("%d ", hashtable[i][j]);
System.out.printf("\n");
}
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
static void cuckoo(int keys[], int n)
{
// initialize hash tables to a dummy value
// (INT-MIN) indicating empty position
initTable();
// start with placing every key at its position in
// the first hash table according to first hash
// function
for (int i = 0, cnt = 0; i < n; i++, cnt = 0)
place(keys[i], 0, cnt, n);
// print the final hash tables
printTable();
}
// Driver Code
public static void main(String[] args)
{
/* following array doesn't have any cycles and
hence all keys will be inserted without any
rehashing */
int keys_1[] = {20, 50, 53, 75, 100,
67, 105, 3, 36, 39};
int n = keys_1.length;
cuckoo(keys_1, n);
/* following array has a cycle and hence we will
have to rehash to position every key */
int keys_2[] = {20, 50, 53, 75, 100,
67, 105, 3, 36, 39, 6};
int m = keys_2.length;
cuckoo(keys_2, m);
}
}
// This code is contributed by Princi Singh
C#
// C# program to demonstrate working of
// Cuckoo hashing.
using System;
class GFG
{
// upper bound on number of
// elements in our set
static int MAXN = 11;
// choices for position
static int ver = 2;
// Auxiliary space bounded by a small
// multiple of MAXN, minimizing wastage
static int [,]hashtable = new int[ver, MAXN];
// Array to store
// possible positions for a key
static int []pos = new int[ver];
/* function to fill hash table
with dummy value
* dummy value: INT_MIN
* number of hashtables: ver */
static void initTable()
{
for (int j = 0; j < MAXN; j++)
for (int i = 0; i < ver; i++)
hashtable[i, j] = int.MinValue;
}
/* return hashed value for a key
* function: ID of hash function
according to which key has to hashed
* key: item to be hashed */
static int hash(int function, int key)
{
switch (function)
{
case 1: return key % MAXN;
case 2: return (key / MAXN) % MAXN;
}
return int.MinValue;
}
/* function to place a key in one of
its possible positions
* tableID: table in which key
has to be placed, also equal to function
according to which key must be hashed
* cnt: number of times function has already
been called in order to place the first input key
* n: maximum number of times function
can be recursively called before stopping and
declaring presence of cycle */
static void place(int key, int tableID,
int cnt, int n)
{
/* if function has been recursively
called max number of times,
stop and declare cycle. Rehash. */
if (cnt == n)
{
Console.Write("{0} unpositioned\n", key);
Console.Write("Cycle present. REHASH.\n");
return;
}
/* calculate and store possible positions
* for the key. Check if key already present
at any of the positions. If YES, return. */
for (int i = 0; i < ver; i++)
{
pos[i] = hash(i + 1, key);
if (hashtable[i, pos[i]] == key)
return;
}
/* check if another key is already present
at the position for the new key in the table
* If YES: place the new key in its position
* and place the older key in an alternate position
for it in the next table */
if (hashtable[tableID,
pos[tableID]] != int.MinValue)
{
int dis = hashtable[tableID, pos[tableID]];
hashtable[tableID, pos[tableID]] = key;
place(dis, (tableID + 1) % ver, cnt + 1, n);
}
else // else: place the new key in its position
hashtable[tableID, pos[tableID]] = key;
}
/* function to print hash table contents */
static void printTable()
{
Console.Write("Final hash tables:\n");
for (int i = 0; i < ver;
i++, Console.Write("\n"))
for (int j = 0; j < MAXN; j++)
if(hashtable[i, j] == int.MinValue)
Console.Write("- ");
else
Console.Write("{0} ",
hashtable[i, j]);
Console.Write("\n");
}
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
static void cuckoo(int []keys, int n)
{
// initialize hash tables to a
// dummy value (INT-MIN)
// indicating empty position
initTable();
// start with placing every key
// at its position in the first
// hash table according to first
// hash function
for (int i = 0, cnt = 0;
i < n; i++, cnt = 0)
place(keys[i], 0, cnt, n);
// print the final hash tables
printTable();
}
// Driver Code
public static void Main(String[] args)
{
/* following array doesn't have
any cycles and hence all keys
will be inserted without any rehashing */
int []keys_1 = {20, 50, 53, 75, 100,
67, 105, 3, 36, 39};
int n = keys_1.Length;
cuckoo(keys_1, n);
/* following array has a cycle and
hence we will have to rehash to
position every key */
int []keys_2 = {20, 50, 53, 75, 100,
67, 105, 3, 36, 39, 6};
int m = keys_2.Length;
cuckoo(keys_2, m);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to demonstrate working of
// Cuckoo hashing.
// upper bound on number of elements in our set
let MAXN = 11;
// choices for position
let ver = 2;
// Auxiliary space bounded by a small multiple
// of MAXN, minimizing wastage
let hashtable = new Array(ver);
for (var i = 0; i < hashtable.length; i++) {
hashtable[i] = new Array(2);
}
// Array to store possible positions for a key
let pos = Array(ver).fill(0);
/* function to fill hash table with dummy value
* dummy value: let_MIN
* number of hashtables: ver */
function initTable()
{
for (let j = 0; j < MAXN; j++)
for (let i = 0; i < ver; i++)
hashtable[i][j] = Number.MIN_VALUE;
}
/* return hashed value for a key
* function: ID of hash function according to which
key has to hashed
* key: item to be hashed */
function hash(function, key)
{
switch (function)
{
case 1: return key % MAXN;
case 2: return (Math.floor(key / MAXN)) % MAXN;
}
return Number.MIN_VALUE;
}
/* function to place a key in one of its possible positions
* tableID: table in which key has to be placed, also equal
to function according to which key must be hashed
* cnt: number of times function has already been called
in order to place the first input key
* n: maximum number of times function can be recursively
called before stopping and declaring presence of cycle */
function place(key, tableID, cnt, n)
{
/* if function has been recursively called max number
of times, stop and declare cycle. Rehash. */
if (cnt == n)
{
document.write(key + " unpositioned" + "<br/>");
document.write("Cycle present. REHASH." + "<br/>");
return;
}
/* calculate and store possible positions for the key.
* check if key already present at any of the positions.
If YES, return. */
for (let i = 0; i < ver; i++)
{
pos[i] = hash(i + 1, key);
if (hashtable[i][pos[i]] == key)
return;
}
/* check if another key is already present at the
position for the new key in the table
* If YES: place the new key in its position
* and place the older key in an alternate position
for it in the next table */
if (hashtable[tableID][pos[tableID]] != Number.MIN_VALUE)
{
let dis = hashtable[tableID][pos[tableID]];
hashtable[tableID][pos[tableID]] = key;
place(dis, (tableID + 1) % ver, cnt + 1, n);
}
else // else: place the new key in its position
hashtable[tableID][pos[tableID]] = key;
}
/* function to print hash table contents */
function printTable()
{
document.write("Final hash tables:" + "<br/>");
for (let i = 0; i < ver; i++, document.write("<br/>"))
for (let j = 0; j < MAXN; j++)
if(hashtable[i][j] == Number.MIN_VALUE)
document.write("- ");
else
document.write(hashtable[i][j] + " ");
document.write("<br/>");
}
/* function for Cuckoo-hashing keys
* keys[]: input array of keys
* n: size of input array */
function cuckoo(keys, n)
{
// initialize hash tables to a dummy value
// (let-MIN) indicating empty position
initTable();
// start with placing every key at its position in
// the first hash table according to first hash
// function
for (let i = 0, cnt = 0; i < n; i++, cnt = 0)
place(keys[i], 0, cnt, n);
// print the final hash tables
printTable();
}
// Driver program
/* following array doesn't have any cycles and
hence all keys will be inserted without any
rehashing */
let keys_1 = [20, 50, 53, 75, 100,
67, 105, 3, 36, 39];
let n = keys_1.length;
cuckoo(keys_1, n);
/* following array has a cycle and hence we will
have to rehash to position every key */
let keys_2 = [20, 50, 53, 75, 100,
67, 105, 3, 36, 39, 6];
let m = keys_2.length;
cuckoo(keys_2, m);
</script>
Producción
Final hash tables: - 100 - 36 - - 50 - - 75 - 3 20 - 39 53 - 67 - - 105 - 105 unpositioned Cycle present. REHASH. Final hash tables: - 67 - 3 - - 39 - - 53 - 6 20 - 36 50 - 75 - - 100 -
Se puede esperar que las generalizaciones de cuckoo hash que usan más de 2 funciones hash alternativas utilicen una mayor parte de la capacidad de la tabla hash de manera eficiente mientras sacrifican algo de velocidad de búsqueda e inserción. Ejemplo: si usamos 3 funciones hash, es seguro cargar el 91% y seguir operando dentro de los límites esperados.
Este artículo es una contribución de Yash Varyani. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA