En hashing hay una función hash que asigna claves a algunos valores. Pero esta función hash puede provocar una colisión, es decir, dos o más claves se asignan al mismo valor. El hash de string evita la colisión. La idea es hacer que cada celda de la tabla hash apunte a una lista vinculada de registros que tienen el mismo valor de función hash.
Vamos a crear una función hash, de modo que nuestra tabla hash tenga un número ‘N’ de cubos.
Para insertar un Node en la tabla hash, necesitamos encontrar el índice hash para la clave dada. Y podría calcularse usando la función hash.
Ejemplo: hashIndex = clave % noOfBuckets
Insertar : Mover al depósito correspondiente al índice hash calculado anteriormente e insertar el nuevo Node al final de la lista.
Borrar: para eliminar un Node de la tabla hash, calcule el índice hash para la clave, muévase al depósito correspondiente al índice hash calculado, busque en la lista en el depósito actual para encontrar y eliminar el Node con la clave dada (si se encuentra).
Consulte Hashing | Fije 2 (Enstringmiento separado) para más detalles.
Usamos una lista en C++ que se implementa internamente como lista enlazada (inserción y eliminación más rápidas).
CPP
// CPP program to implement hashing with chaining
#include<bits/stdc++.h>
using namespace std;
class Hash
{
int BUCKET; // No. of buckets
// Pointer to an array containing buckets
list<int> *table;
public:
Hash(int V); // Constructor
// inserts a key into hash table
void insertItem(int x);
// deletes a key from hash table
void deleteItem(int key);
// hash function to map values to key
int hashFunction(int x) {
return (x % BUCKET);
}
void displayHash();
};
Hash::Hash(int b)
{
this->BUCKET = b;
table = new list<int>[BUCKET];
}
void Hash::insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
void Hash::deleteItem(int key)
{
// get the hash index of key
int index = hashFunction(key);
// find the key in (index)th list
list <int> :: iterator i;
for (i = table[index].begin();
i != table[index].end(); i++) {
if (*i == key)
break;
}
// if key is found in hash table, remove it
if (i != table[index].end())
table[index].erase(i);
}
// function to display hash table
void Hash::displayHash() {
for (int i = 0; i < BUCKET; i++) {
cout << i;
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
// Driver program
int main()
{
// array that contains keys to be mapped
int a[] = {15, 11, 27, 8, 12};
int n = sizeof(a)/sizeof(a[0]);
// insert the keys into the hash table
Hash h(7); // 7 is count of buckets in
// hash table
for (int i = 0; i < n; i++)
h.insertItem(a[i]);
// delete 12 from hash table
h.deleteItem(12);
// display the Hash table
h.displayHash();
return 0;
}
0 1 --> 15 --> 8 2 3 4 --> 11 5 6 --> 27
Complejidad del tiempo:
Búsqueda: O(1+(n/m))
Eliminar: O(1+(n/m))
donde n = Número de llaves a insertar.
m = Número de ranuras en la tabla Hash.
Aquí n/m es el factor de carga .
El factor de carga (∝) debe ser lo más pequeño posible.
Si aumenta el factor de carga, entonces aumenta la posibilidad de colisión.
El factor de carga es el intercambio de espacio y tiempo.
Suponga, distribución uniforme de claves,
Longitud de string esperada : O(∝)
Tiempo esperado para buscar: O( 1 + ∝ )
Tiempo esperado para insertar/borrar: O( 1 + ∝ )
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA