logo

TechCodeview

Implementarea tabelului Hash în C/C++ folosind Separate Chaining

Introducere:

Scurtarea adreselor URL sunt un exemplu de hashing, deoarece mapează adresa URL de dimensiune mare la dimensiunea mică

Câteva exemple de funcții Hash:

  • cheie % numărul de găleți
  • Valoarea ASCII a caracterului * PrimeNumberX. Unde x = 1, 2, 3….n
  • Vă puteți crea propria funcție hash, dar ar trebui să fie o funcție hash bună, care să ofere un număr mai mic de coliziuni.

Componentele hashingului



Indexul găleții:

Valoarea returnată de funcția Hash este indexul bucket-ului pentru o cheie într-o metodă de înlănțuire separată. Fiecare index din matrice se numește găleată deoarece este o găleată dintr-o listă legată.

Reluare:

Rehashing este un concept care reduce coliziunea atunci când elementele sunt mărite în tabelul hash curent. Va face o nouă matrice de dimensiune dublată și va copia elementele anterioare ale matricei în ea și este ca funcționarea internă a vectorului în C++. Evident, funcția Hash ar trebui să fie dinamică, deoarece ar trebui să reflecte unele schimbări atunci când capacitatea este crescută. Funcția hash include capacitatea tabelului hash în ea, prin urmare, în timp ce copierea valorilor cheilor din funcția hash de matrice anterioară oferă indici de bucket diferiți, deoarece depinde de capacitatea (buckets) a tabelului hash. În general, atunci când valoarea factorului de încărcare este mai mare de 0,5, se fac reluări.

  • Dubla dimensiunea matricei.
  • Copiați elementele matricei anterioare în noua matrice. Folosim funcția hash în timp ce copiem fiecare nod într-o matrice nouă, prin urmare, va reduce coliziunea.
  • Ștergeți matricea anterioară din memorie și îndreptați indicatorul interior al hărții hash către această nouă matrice.
  • În general, Load Factor = numărul de elemente din Hash Map / numărul total de găleți (capacitate).

Coliziune:

Coliziunea este situația în care indexul găleții nu este gol. Înseamnă că un cap de listă legat este prezent la acel index al grupului. Avem două sau mai multe valori care se mapează la același indice de grup.



actor zeenat aman

Funcții majore din programul nostru

  • Inserare
  • Căutare
  • Funcția Hash
  • Șterge
  • Reluare

Harta Hash

Implementare fără Rehashing:

C




șir de caractere java înlocuiți



#include> #include> #include> // Linked List node> struct> node {> >// key is string> >char>* key;> >// value is also string> >char>* value;> >struct> node* next;> };> // like constructor> void> setNode(>struct> node* node,>char>* key,>char>* value)> {> >node->cheie = cheie;> >node->valoare = valoare;> >node->următorul = NULL;> >return>;> };> struct> hashMap {> >// Current number of elements in hashMap> >// and capacity of hashMap> >int> numOfElements, capacity;> >// hold base address array of linked list> >struct> node** arr;> };> // like constructor> void> initializeHashMap(>struct> hashMap* mp)> {> >// Default capacity in this case> >mp->capacitate = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*)> >* mp->capacitate);> >return>;> }> int> hashFunction(>struct> hashMap* mp,>char>* key)> {> >int> bucketIndex;> >int> sum = 0, factor = 31;> >for> (>int> i = 0; i <>strlen>(key); i++) {> >// sum = sum + (ascii value of> >// char * (primeNumber ^ x))...> >// where x = 1, 2, 3....n> >sum = ((sum % mp->capacitate)> >+ (((>int>)key[i]) * factor) % mp->capacitate)> >% mp->capacitate;> >// factor = factor * prime> >// number....(prime> >// number) ^ x> >factor = ((factor % __INT16_MAX__)> >* (31 % __INT16_MAX__))> >% __INT16_MAX__;> >}> >bucketIndex = sum;> >return> bucketIndex;> }> void> insert(>struct> hashMap* mp,>char>* key,>char>* value)> {> >// Getting bucket index for the given> >// key - value pair> >int> bucketIndex = hashFunction(mp, key);> >struct> node* newNode = (>struct> node*)>malloc>(> >// Creating a new node> >sizeof>(>struct> node));> >// Setting value of node> >setNode(newNode, key, value);> >// Bucket index is empty....no collision> >if> (mp->arr[bucketIndex] == NULL) {> >mp->arr[bucketIndex] = newNode;> >}> >// Collision> >else> {> >// Adding newNode at the head of> >// linked list which is present> >// at bucket index....insertion at> >// head in linked list> >newNode->următor = mp->arr[bucketIndex];> >mp->arr[bucketIndex] = newNode;> >}> >return>;> }> void> delete> (>struct> hashMap* mp,>char>* key)> {> >// Getting bucket index for the> >// given key> >int> bucketIndex = hashFunction(mp, key);> >struct> node* prevNode = NULL;> >// Points to the head of> >// linked list present at> >// bucket index> >struct> node* currNode = mp->arr[bucketIndex];> >while> (currNode != NULL) {> >// Key is matched at delete this> >// node from linked list> >if> (>strcmp>(key, currNode->cheie) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->următorul = currNode->next;> >}> >free>(currNode);> >break>;> >}> >prevNode = currNode;> >currNode = currNode->următorul;> >}> >return>;> }> char>* search(>struct> hashMap* mp,>char>* key)> {> >// Getting the bucket index> >// for the given key> >int> bucketIndex = hashFunction(mp, key);> >// Head of the linked list> >// present at bucket index> >struct> node* bucketHead = mp->arr[bucketIndex];> >while> (bucketHead != NULL) {> >// Key is found in the hashMap> >if> (bucketHead->cheie == cheie) {> >return> bucketHead->valoare;> >}> >bucketHead = bucketHead->următorul;> >}> >// If no key found in the hashMap> >// equal to the given key> >char>* errorMssg = (>char>*)>malloc>(>sizeof>(>char>) * 25);> >errorMssg =>'Oops! No data found. '>;> >return> errorMssg;> }> // Drivers code> int> main()> {> >// Initialize the value of mp> >struct> hashMap* mp> >= (>struct> hashMap*)>malloc>(>sizeof>(>struct> hashMap));> >initializeHashMap(mp);> >insert(mp,>'Yogaholic'>,>'Anjali'>);> >insert(mp,>'pluto14'>,>'Vartika'>);> >insert(mp,>'elite_Programmer'>,>'Manish'>);> >insert(mp,>'GFG'>,>'techcodeview.com'>);> >insert(mp,>'decentBoy'>,>'Mayank'>);> >printf>(>'%s '>, search(mp,>'elite_Programmer'>));> >printf>(>'%s '>, search(mp,>'Yogaholic'>));> >printf>(>'%s '>, search(mp,>'pluto14'>));> >printf>(>'%s '>, search(mp,>'decentBoy'>));> >printf>(>'%s '>, search(mp,>'GFG'>));> >// Key is not inserted> >printf>(>'%s '>, search(mp,>'randomKey'>));> >printf>(>' After deletion : '>);> >// Deletion of key> >delete> (mp,>'decentBoy'>);> >printf>(>'%s '>, search(mp,>'decentBoy'>));> >return> 0;> }> 

>

simbol derivat parțial latex 

>

C++




#include> #include> // Linked List node> struct> node {> >// key is string> >char>* key;> >// value is also string> >char>* value;> >struct> node* next;> };> // like constructor> void> setNode(>struct> node* node,>char>* key,>char>* value) {> >node->cheie = cheie;> >node->valoare = valoare;> >node->următorul = NULL;> >return>;> }> struct> hashMap {> >// Current number of elements in hashMap> >// and capacity of hashMap> >int> numOfElements, capacity;> >// hold base address array of linked list> >struct> node** arr;> };> // like constructor> void> initializeHashMap(>struct> hashMap* mp) {> >// Default capacity in this case> >mp->capacitate = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*) * mp->capacitate);> >return>;> }> int> hashFunction(>struct> hashMap* mp,>char>* key) {> >int> bucketIndex;> >int> sum = 0, factor = 31;> >for> (>int> i = 0; i <>strlen>(key); i++) {> >// sum = sum + (ascii value of> >// char * (primeNumber ^ x))...> >// where x = 1, 2, 3....n> >sum = ((sum % mp->capacitate) + (((>int>)key[i]) * factor) % mp->capacitate) % mp->capacitate;> >// factor = factor * prime> >// number....(prime> >// number) ^ x> >factor = ((factor % __INT16_MAX__) * (31 % __INT16_MAX__)) % __INT16_MAX__;> >}> >bucketIndex = sum;> >return> bucketIndex;> }> void> insert(>struct> hashMap* mp,>char>* key,>char>* value) {> >// Getting bucket index for the given> >// key - value pair> >int> bucketIndex = hashFunction(mp, key);> >struct> node* newNode = (>struct> node*)>malloc>(> >// Creating a new node> >sizeof>(>struct> node));> >// Setting value of node> >setNode(newNode, key, value);> >// Bucket index is empty....no collision> >if> (mp->arr[bucketIndex] == NULL) {> >mp->arr[bucketIndex] = newNode;> >}> >// Collision> >else> {> >// Adding newNode at the head of> >// linked list which is present> >// at bucket index....insertion at> >// head in linked list> >newNode->următor = mp->arr[bucketIndex];> >mp->arr[bucketIndex] = newNode;> >}> >return>;> }> void> deleteKey(>struct> hashMap* mp,>char>* key) {> >// Getting bucket index for the> >// given key> >int> bucketIndex = hashFunction(mp, key);> >struct> node* prevNode = NULL;> >// Points to the head of> >// linked list present at> >// bucket index> >struct> node* currNode = mp->arr[bucketIndex];> >while> (currNode != NULL) {> >// Key is matched at delete this> >// node from linked list> >if> (>strcmp>(key, currNode->cheie) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->următorul = currNode->next;> }> free>(currNode);> break>;> }> prevNode = currNode;> >currNode = currNode->următorul;> >}> return>;> }> char>* search(>struct> hashMap* mp,>char>* key) {> // Getting the bucket index for the given key> int> bucketIndex = hashFunction(mp, key);> // Head of the linked list present at bucket index> struct> node* bucketHead = mp->arr[bucketIndex];> while> (bucketHead != NULL) {> > >// Key is found in the hashMap> >if> (>strcmp>(bucketHead->cheie, cheie) == 0) {> >return> bucketHead->valoare;> >}> > >bucketHead = bucketHead->următorul;> }> // If no key found in the hashMap equal to the given key> char>* errorMssg = (>char>*)>malloc>(>sizeof>(>char>) * 25);> strcpy>(errorMssg,>'Oops! No data found. '>);> return> errorMssg;> }> // Drivers code> int> main()> {> // Initialize the value of mp> struct> hashMap* mp = (>struct> hashMap*)>malloc>(>sizeof>(>struct> hashMap));> initializeHashMap(mp);> insert(mp,>'Yogaholic'>,>'Anjali'>);> insert(mp,>'pluto14'>,>'Vartika'>);> insert(mp,>'elite_Programmer'>,>'Manish'>);> insert(mp,>'GFG'>,>'techcodeview.com'>);> insert(mp,>'decentBoy'>,>'Mayank'>);> printf>(>'%s '>, search(mp,>'elite_Programmer'>));> printf>(>'%s '>, search(mp,>'Yogaholic'>));> printf>(>'%s '>, search(mp,>'pluto14'>));> printf>(>'%s '>, search(mp,>'decentBoy'>));> printf>(>'%s '>, search(mp,>'GFG'>));> // Key is not inserted> printf>(>'%s '>, search(mp,>'randomKey'>));> printf>(>' After deletion : '>);> // Deletion of key> deleteKey(mp,>'decentBoy'>);> // Searching the deleted key> printf>(>'%s '>, search(mp,>'decentBoy'>));> return> 0;> }>

tip de dată dactilografiată 

>

>

ștergerea cache-ului npm
Ieșire 

Manish Anjali Vartika Mayank techcodeview.com Oops! No data found. After deletion : Oops! No data found.>

Explicaţie:

    inserare: inserează perechea cheie-valoare în capul unei liste conectate care este prezentă la indexul grupului dat. hashFunction: Oferă indexul bucket-ului pentru cheia dată. Al nostru funcția hash = valoarea ASCII a caracterului * primNumberX . Numărul prim în cazul nostru este 31, iar valoarea lui x crește de la 1 la n pentru caracterele consecutive dintr-o cheie. ștergere: șterge perechea cheie-valoare din tabelul hash pentru cheia dată. Acesta șterge nodul din lista legată care deține perechea cheie-valoare. Căutare: Căutați valoarea cheii date.
  • Această implementare nu folosește conceptul de rehashing. Este o matrice de dimensiuni fixe de liste legate.
  • Cheia și valoarea ambele sunt șiruri în exemplul dat.

Complexitatea timpului și complexitatea spațiului:

Complexitatea de timp a operațiunilor de inserare și ștergere a tabelului hash este O(1) în medie. Există un calcul matematic care o dovedește.

    Timpul Complexitatea inserției: În cazul mediu, este constantă. În cel mai rău caz, este liniară. Timpul complexitatea căutării: în cazul mediu, este constantă. În cel mai rău caz, este liniară. Timpul Complexitatea ștergerii: În cazurile medii, este constantă. În cel mai rău caz, este liniară. Complexitatea spațială: O(n) deoarece are n număr de elemente.

Articole similare:

  • Tehnica separată de manipulare a coliziunilor în lanț în hashing .