Cuckoo Hashing – Peor caso O(1) ¡Búsqueda!

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: 

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

ch1

Comencemos insertando 20 en su posible posición en la primera tabla determinada por h1(20):

ch2

Siguiente: 50

ch3

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) 

ch4

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) 

ch6

Siguiente: 100 . h1(100) = 1. 

ch

Siguiente: 67 . h1(67) = 1. Pero 100 ya está allí en 1. Colocamos 67 en la tabla 1 y 100 en la tabla 2 

ch8

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.

ch9

Siguiente: 3 . h1(3) = 3.

ch10

Siguiente: 36 . h1(36) = 3. h2(3) = 0.

ch11

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ó.

ch12

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *