IMPLEMENTERING AF HASH-TABEL I C/C++ VED HJÆLP AF SEPARATE CHAINING - TECHCODEVIEW.COM

Introduktion:

URL-forkortere er et eksempel på hashing, da det kortlægger stor størrelse URL til lille størrelse

Nogle eksempler på hash-funktioner:

nøgle % antal spande
ASCII-værdi af karakter * PrimeNumber ^x. Hvor x = 1, 2, 3….n
Du kan lave din egen hash-funktion, men det bør være en god hash-funktion, der giver færre antal kollisioner.

Komponenter af hashing

Bucket Index:

Den værdi, der returneres af Hash-funktionen, er bucket-indekset for en nøgle i en separat kædemetode. Hvert indeks i arrayet kaldes en bucket, da det er en bucket af en linket liste.

Genhasning:

Rehashing er et koncept, der reducerer kollision, når elementerne øges i den aktuelle hash-tabel. Det vil lave et nyt array med fordoblet størrelse og kopiere de tidligere array-elementer til det, og det er ligesom vektorens interne arbejde i C++. Det er klart, at Hash-funktionen skal være dynamisk, da den skal afspejle nogle ændringer, når kapaciteten øges. Hash-funktionen inkluderer kapaciteten af hash-tabellen i den, derfor, mens kopiering af nøgleværdier fra den tidligere array-hash-funktion giver forskellige bucket-indekser, da den er afhængig af kapaciteten (buckets) af hash-tabellen. Generelt, når værdien af belastningsfaktoren er større end 0,5 udføres omhasninger.

Dobbelt størrelse af arrayet.
Kopier elementerne fra det forrige array til det nye array. Vi bruger hash-funktionen, mens vi kopierer hver node til et nyt array igen, derfor vil det reducere kollision.
Slet det forrige array fra hukommelsen, og peg dit hash-korts indvendige array-markør til dette nye array.
Generelt er Load Factor = antal elementer i Hash Map / samlet antal buckets (kapacitet).

Kollision:

Kollision er den situation, hvor skovlindekset ikke er tomt. Det betyder, at et linket listehoved er til stede ved det bucket-indeks. Vi har to eller flere værdier, der knytter sig til det samme bucket-indeks.

Vigtigste funktioner i vores program

Indskud
Søg
Hash funktion
Slet
Genhasning

Hash kort

Implementering uden rehashing:

C

#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->nøgle = nøgle;> > node->værdi = værdi;> > node->næste = 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->kapacitet = 100;> > mp->numOfElements = 0;> > // array of size = 1> > mp->arr = (> struct> node**)> malloc> (> sizeof> (> struct> node*)> > * mp->kapacitet);> > 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->kapacitet)> > + (((> int> )key[i]) * factor) % mp->kapacitet)> > % mp->kapacitet;> > // 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] = nyNode;> > }> > // Collision> > else> {> > // Adding newNode at the head of> > // linked list which is present> > // at bucket index....insertion at> > // head in linked list> > newNode->næste = mp->arr[bucketIndex];> > mp->arr[bucketIndex] = nyNode;> > }> > 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->nøgle) == 0) {> > // Head node> > // deletion> > if> (currNode == mp->arr[bucketIndex]) {> > mp->arr[bucketIndex] = currNode->næste;> > }> > // Last node or middle node> > else> {> > prevNode->næste = currNode->næste;> > }> > free> (currNode);> > break> ;> > }> > prevNode = currNode;> > currNode = currNode->næste;> > }> > 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->tast == tast) {> > return> bucketHead->værdi;> > }> > bucketHead = bucketHead->næste;> > }> > // 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;> }>

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->nøgle = nøgle;> > node->værdi = værdi;> > node->næste = 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->kapacitet = 100;> > mp->numOfElements = 0;> > // array of size = 1> > mp->arr = (> struct> node**)> malloc> (> sizeof> (> struct> node*) * mp->kapacitet);> > 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->kapacitet) + (((> int> )key[i]) * factor) % mp->kapacitet) % mp->kapacitet;> > // 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->næste = 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->tast) == 0) {> > // Head node> > // deletion> > if> (currNode == mp->arr[bucketIndex]) {> > mp->arr[bucketIndex] = currNode->næste;> > }> > // Last node or middle node> > else> {> > prevNode->næste = currNode->næste;> }> free> (currNode);> break> ;> }> prevNode = currNode;> > currNode = currNode->næste;> > }> 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->tast, tast) == 0) {> > return> bucketHead->værdi;> > }> > > bucketHead = bucketHead->næste;> }> // 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;> }>

Produktion

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

Forklaring:

hash-funktion = ASCII-værdi af karakter * primeNumber ^x

Denne implementering bruger ikke rehashing-konceptet. Det er en række af sammenkædede lister i fast størrelse.
Nøgle og værdi er begge strenge i det givne eksempel.

Tidskompleksitet og rumkompleksitet:

Tidskompleksiteten af hash tabel indsættelse og sletning operationer er O(1) i gennemsnit. Der er nogle matematiske beregninger, der beviser det.

Tidskompleksitet ved indsættelse: I gennemsnitstilfældet er den konstant. I værste fald er det lineært. Tidskompleksitet af søgning: I gennemsnitstilfældet er den konstant. I værste fald er det lineært. Tidskompleksitet for sletning: I gennemsnitlige tilfælde er den konstant. I værste fald er det lineært. Rumkompleksitet: O(n), da det har n antal elementer.

Relaterede artikler: