logo

TechCodeview

Implementació de la taula Hash en C/C++ mitjançant Separate Chaining

Introducció:

Els escurçadors d'URL són un exemple de hash, ja que mapegen URL de mida gran a mida petita

Alguns exemples de funcions hash:

  • clau % nombre de cubs
  • Valor ASCII del caràcter * PrimeNumberx. On x = 1, 2, 3….n
  • Podeu crear la vostra pròpia funció hash, però hauria de ser una bona funció hash que doni menys nombre de col·lisions.

Components del hashing



vlc baixar vídeos de youtube

Índex de cubs:

El valor que retorna la funció Hash és l'índex de cub per a una clau en un mètode d'encadenament independent. Cada índex de la matriu s'anomena cub ja que és un cub d'una llista enllaçada.

Refs:

El refresc és un concepte que redueix la col·lisió quan els elements augmenten a la taula hash actual. Farà una nova matriu de mida duplicada i hi copiarà els elements de la matriu anterior i serà com el funcionament intern del vector en C++. Òbviament, la funció Hash hauria de ser dinàmica, ja que hauria de reflectir alguns canvis quan s'augmenta la capacitat. La funció hash inclou la capacitat de la taula hash, per tant, mentre copiar els valors de clau de la funció hash de la matriu anterior ofereix diferents índexs de cub ja que depèn de la capacitat (cubos) de la taula hash. En general, quan el valor del factor de càrrega és superior a 0,5 es fan repeticions.

  • Doble la mida de la matriu.
  • Copieu els elements de la matriu anterior a la nova matriu. Utilitzem la funció hash mentre copiem cada node a una nova matriu, per tant, reduirà la col·lisió.
  • Suprimeix la matriu anterior de la memòria i apunta el punter de la matriu interior del mapa hash cap a aquesta nova matriu.
  • Generalment, Factor de càrrega = nombre d'elements al mapa hash / nombre total de cubs (capacitat).

Col·lisió:

La col·lisió és la situació en què l'índex del cub no està buit. Significa que hi ha un cap de llista enllaçat a aquest índex de cub. Tenim dos o més valors que s'assignen al mateix índex de compartiment.



Funcions principals del nostre programa

  • Inserció
  • Cerca
  • Funció hash
  • Suprimeix
  • Refet

Mapa hash

Implementació sense repetició:

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->clau = clau;> >node->valor = valor;> >node->següent = 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->capacitat = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*)> >* mp->capacitat);> >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->capacitat)> >+ (((>int>)key[i]) * factor) % mp->capacitat)> >% mp->capacitat;> >// 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] = nouNode;> >}> >// Collision> >else> {> >// Adding newNode at the head of> >// linked list which is present> >// at bucket index....insertion at> >// head in linked list> >newNode->següent = mp->arr[bucketIndex];> >mp->arr[bucketIndex] = nouNode;> >}> >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->clau) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->següent = currNode->next;> >}> >free>(currNode);> >break>;> >}> >prevNode = currNode;> >currNode = currNode->següent;> >}> >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->clau == clau) {> >return> bucketHead->valor;> >}> >bucketHead = bucketHead->següent;> >}> >// 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->clau = clau;> >node->valor = valor;> >node->següent = 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->capacitat = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*) * mp->capacitat);> >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->capacitat) + (((>int>)key[i]) * factor) % mp->capacitat) % mp->capacitat;> >// 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] = nouNode;> >}> >// Collision> >else> {> >// Adding newNode at the head of> >// linked list which is present> >// at bucket index....insertion at> >// head in linked list> >newNode->següent = mp->arr[bucketIndex];> >mp->arr[bucketIndex] = nouNode;> >}> >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->clau) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->següent;> >}> >// Last node or middle node> >else> {> >prevNode->següent = currNode->next;> }> free>(currNode);> break>;> }> prevNode = currNode;> >currNode = currNode->següent;> >}> 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->clau, clau) == 0) {> >return> bucketHead->valor;> >}> > >bucketHead = bucketHead->següent;> }> // 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;> }> 

>

osi model de referència en xarxa 

>

Sortida 

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

Explicació:

    inserció: insereix el parell clau-valor a l'encapçalament d'una llista enllaçada que està present a l'índex de compartiment donat. hashFunction: proporciona l'índex de cub per a la clau donada. El nostre funció hash = valor ASCII del caràcter * nombre primerx . El nombre primer en el nostre cas és 31 i el valor de x augmenta d'1 a n per a caràcters consecutius d'una clau. supressió: elimina el parell clau-valor de la taula hash per a la clau donada. Elimina el node de la llista enllaçada que conté el parell clau-valor. Cerca: cerca el valor de la clau donada.
  • Aquesta implementació no utilitza el concepte de repetició. És una matriu de mida fixa de llistes enllaçades.
  • La clau i el valor són cadenes en l'exemple donat.

Complexitat temporal i complexitat espacial:

La complexitat temporal de les operacions d'inserció i supressió de taules hash és O(1) de mitjana. Hi ha algun càlcul matemàtic que ho demostra.

    Complexitat temporal d'inserció: En el cas mitjà és constant. En el pitjor dels casos, és lineal. Complexitat temporal de la cerca: en el cas mitjà és constant. En el pitjor dels casos, és lineal. Complexitat temporal de la supressió: en els casos mitjans és constant. En el pitjor dels casos, és lineal. Complexitat espacial: O(n) ja que té n nombre d'elements.

Articles relacionats:

  • Tècnica de maneig de col·lisions d'encadenament separat en hashing.