Programa para implementar Tabla Hash usando Direccionamiento Abierto

La tarea es diseñar una estructura de datos de tabla hash general con caso de colisión manejado y que admita las funciones Insert() , Find() y Delete() .

Ejemplos:

Suponga que las operaciones se realizan en una array de pares, {{1, 5}, {2, 15}, {3, 20}, {4, 7}}. Y una array de capacidad 20 se utiliza como tabla hash:

1. Insertar (1, 5 ): asigne el par {1, 5} en el índice (1% 20 = 1) en la tabla hash.
2. Insertar (2, 15 ): asigne el par {2, 15} en el índice (2% 20 = 2) en la tabla hash.
3. Insertar (3, 20 ): asigne el par {3, 20} en el índice (3% 20 = 3) en la tabla hash.
4. Insertar (4, 7 ): asigne el par {4, 7} en el índice (4% 20 = 4) en la tabla hash.
5. Find(4): La clave 4 se almacena en el índice (4%20 = 4). Por lo tanto, imprima el 7 ya que es el valor de la clave, 4, en el índice 4 de la tabla hash.
6. Delete(4): La clave 4 se almacena en el índice (4%20 = 4). Después de eliminar la clave 4, la tabla hash tiene las claves {1, 2, 3}.
7. Find(4): imprime -1, ya que la clave 4 no existe en la tabla hash.

Enfoque: el problema dado se puede resolver usando la función de hash del módulo y usando una array de estructuras como tabla hash, donde cada elemento de la array almacenará el par {clave, valor} que se va a codificar. El caso de colisión puede manejarse mediante sondeo lineal , direccionamiento abierto . Siga los pasos a continuación para resolver el problema:

• Defina un Node, estructura digamos HashNode, a un par clave-valor para ser hash.
• Inicialice una array del puntero de tipo HashNode , diga *arr[] para almacenar todos los pares clave-valor.
• Insertar (clave, valor): inserte el par {clave, valor} en la tabla hash.
  • Inicialice una variable HashNode , digamos temp , con valor {Clave, Valor}.
  • Encuentre el índice donde se puede almacenar la clave usando la función Hash y luego almacene el índice en una variable, digamos HashIndex .
  • Si arr[HashIndex] no está vacío o existe otra clave , realice un sondeo lineal actualizando continuamente HashIndex como HashIndex =(HashIndex+1)%capacity.
  • Si arr[HashIndex] no es nulo, inserte el Node dado asignando la dirección de temp a arr[HashIndex].
• Find(Key): encuentra el valor de la clave en la tabla hash.
  • Encuentre el índice donde puede existir la clave usando una función Hash y luego almacene el índice en una variable, digamos HashIndex .
  • Si arr[HashIndex] contiene la clave, Key devuelve su valor.
  • De lo contrario, realice un sondeo lineal actualizando continuamente HashIndex como HashIndex =(HashIndex+1)%capacity. Luego , si se encuentra Key , devuelva el valor de Key en ese HashIndex y luego devuelva true .
  • Si no se encuentra la clave , devuelve -1 que representa no encontrada. De lo contrario, devuelve el valor de la clave.
• Delete(Key): elimina la clave de la tabla hash.
  • Encuentre el índice donde puede existir la clave usando una función Hash y luego almacene el índice en una variable, digamos HashIndex .
  • Si arr[HashIndex ] contiene la clave, Key luego elimínela asignando {-1, -1} a arr[HashIndex] y luego devuelva true .
  • De lo contrario, realice un sondeo lineal actualizando continuamente HashIndex como HashIndex =(HashIndex+1)%capacity. Luego , si se encuentra la clave , elimine el valor de la clave en ese HashIndex y luego devuelva true .
  • Si no se encuentra la clave , la devolución es falsa.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
struct HashNode {
    int key;
    int value;
};
 
const int capacity = 20;
int size = 0;
 
struct HashNode** arr;
struct HashNode* dummy;
 
// Function to add key value pair
void insert(int key, int V)
{
 
    struct HashNode* temp
        = (struct HashNode*)malloc(sizeof(struct HashNode));
    temp->key = key;
    temp->value = V;
 
    // Apply hash function to find
    // index for given key
    int hashIndex = key % capacity;
 
    // Find next free space
    while (arr[hashIndex] != NULL
           && arr[hashIndex]->key != key
           && arr[hashIndex]->key != -1) {
        hashIndex++;
        hashIndex %= capacity;
    }
 
    // If new node to be inserted
    // increase the current size
    if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
        size++;
 
    arr[hashIndex] = temp;
}
 
// Function to delete a key value pair
int deleteKey(int key)
{
    // Apply hash function to find
    // index for given key
    int hashIndex = key % capacity;
 
    // Finding the node with given
    // key
    while (arr[hashIndex] != NULL) {
        // if node found
        if (arr[hashIndex]->key == key) {
            // Insert dummy node here
            // for further use
            arr[hashIndex] = dummy;
 
            // Reduce size
            size--;
 
            // Return the value of the key
            return 1;
        }
        hashIndex++;
        hashIndex %= capacity;
    }
 
    // If not found return null
    return 0;
}
 
// Function to search the value
// for a given key
int find(int key)
{
    // Apply hash function to find
    // index for given key
    int hashIndex = (key % capacity);
 
    int counter = 0;
 
    // Find the node with given key
    while (arr[hashIndex] != NULL) {
 
        int counter = 0;
        // If counter is greater than
        // capacity
        if (counter++ > capacity)
            break;
 
        // If node found return its
        // value
        if (arr[hashIndex]->key == key)
            return arr[hashIndex]->value;
 
        hashIndex++;
        hashIndex %= capacity;
    }
 
    // If not found return
    // -1
    return -1;
}
 
// Driver Code
int main()
{
    // Space allocation
    arr = (struct HashNode**)malloc(sizeof(struct HashNode*)
                                    * capacity);
    // Assign NULL initially
    for (int i = 0; i < capacity; i++)
        arr[i] = NULL;
 
    dummy
        = (struct HashNode*)malloc(sizeof(struct HashNode));
 
    dummy->key = -1;
    dummy->value = -1;
 
    insert(1, 5);
    insert(2, 15);
    insert(3, 20);
    insert(4, 7);
    if (find(4) != -1)
        cout << "Value of Key 4 = " << find(4) << endl;
    else
        cout << ("Key 4 does not exists\n");
 
    if (deleteKey(4))
        cout << ("Node value of key 4 is deleted "
                 "successfully\n");
    else {
        cout << ("Key does not exists\n");
    }
 
    if (find(4) != -1)
        cout << ("Value of Key 4 = %d\n", find(4));
    else
        cout << ("Key 4 does not exists\n");
}
 
// This code is contributed by Lovely Jain

// C program for the above approach
#include <stdio.h>
#include <stdlib.h>
 
struct HashNode {
    int key;
    int value;
};
 
const int capacity = 20;
int size = 0;
 
struct HashNode** arr;
struct HashNode* dummy;
 
// Function to add key value pair
void insert(int key, int V)
{
 
    struct HashNode* temp
        = (struct HashNode*)malloc(sizeof(struct HashNode));
    temp->key = key;
    temp->value = V;
 
    // Apply hash function to find
    // index for given key
    int hashIndex = key % capacity;
 
    // Find next free space
    while (arr[hashIndex] != NULL
           && arr[hashIndex]->key != key
           && arr[hashIndex]->key != -1) {
        hashIndex++;
        hashIndex %= capacity;
    }
 
    // If new node to be inserted
    // increase the current size
    if (arr[hashIndex] == NULL
        || arr[hashIndex]->key == -1)
        size++;
 
    arr[hashIndex] = temp;
}
 
// Function to delete a key value pair
int delete (int key)
{
    // Apply hash function to find
    // index for given key
    int hashIndex = key % capacity;
 
    // Finding the node with given
    // key
    while (arr[hashIndex] != NULL) {
        // if node found
        if (arr[hashIndex]->key == key) {
            // Insert dummy node here
            // for further use
            arr[hashIndex] = dummy;
 
            // Reduce size
            size--;
 
            // Return the value of the key
            return 1;
        }
        hashIndex++;
        hashIndex %= capacity;
    }
 
    // If not found return null
    return 0;
}
 
// Function to search the value
// for a given key
int find(int key)
{
    // Apply hash function to find
    // index for given key
    int hashIndex = (key % capacity);
 
    int counter = 0;
 
    // Find the node with given key
    while (arr[hashIndex] != NULL) {
 
        int counter = 0;
        // If counter is greater than
        // capacity
        if (counter++ > capacity)
            break;
 
        // If node found return its
        // value
        if (arr[hashIndex]->key == key)
            return arr[hashIndex]->value;
 
        hashIndex++;
        hashIndex %= capacity;
    }
 
    // If not found return
    // -1
    return -1;
}
 
// Driver Code
int main()
{
    // Space allocation
    arr = (struct HashNode**)malloc(sizeof(struct HashNode*)
                                    * capacity);
    // Assign NULL initially
    for (int i = 0; i < capacity; i++)
        arr[i] = NULL;
 
    dummy
        = (struct HashNode*)malloc(sizeof(struct HashNode));
 
    dummy->key = -1;
    dummy->value = -1;
 
    insert(1, 5);
    insert(2, 15);
    insert(3, 20);
    insert(4, 7);
 
    if (find(4) != -1)
        printf("Value of Key 4 = %d\n", find(4));
    else
        printf("Key 4 does not exists\n");
 
    if (delete (4))
        printf("Node value of key 4 is deleted "
               "successfully\n");
    else {
        printf("Key does not exists\n");
    }
 
    if (find(4) != -1)
        printf("Value of Key 4 = %d\n", find(4));
    else
        printf("Key 4 does not exists\n");
}

Value of Key 4 = 7
Node value of key 4 is deleted successfully
Key 4 does not exists

Tiempo Complejidad: O(capacidad), para cada operación
Espacio Auxiliar: O(capacidad)