logo

TechCodeview

Hash tabulas ieviešana C/C++, izmantojot atsevišķu ķēdi

Ievads:

URL saīsinātāji ir jaukšanas piemērs, jo liela izmēra URL tiek piesaistīts mazam izmēram

Daži jaucējfunkciju piemēri:

  • atslēga % spaiņu skaits
  • Rakstzīmes * PrimeNumber ASCII vērtībax. Kur x = 1, 2, 3….n
  • Varat izveidot savu jaucējfunkciju, taču tai ir jābūt labai jaucējfunkcijai, kas nodrošina mazāku sadursmju skaitu.

Jaukšanas sastāvdaļas



pārvērst virkni interger

Grupas indekss:

Funkcijas Hash atgrieztā vērtība ir atslēgas segmenta indekss atsevišķā ķēdes savienošanas metodē. Katrs indekss masīvā tiek saukts par segmentu, jo tas ir saistītā saraksta segments.

Rehashing:

Atkārtota jaukšana ir jēdziens, kas samazina sadursmes, kad elementi tiek palielināti pašreizējā hash tabulā. Tas izveidos jaunu dubultota izmēra masīvu un kopēs uz to iepriekšējos masīva elementus, un tas ir kā vektora iekšējais darbs C++. Acīmredzot Hash funkcijai jābūt dinamiskai, jo tai jāatspoguļo dažas izmaiņas, kad tiek palielināta jauda. Jaucējfunkcija ietver tajā esošās jaukšanas tabulas ietilpību, tāpēc, kopējot atslēgas vērtības no iepriekšējās masīva jaucējfunkcijas, tiek iegūti dažādi segmentu indeksi, jo tas ir atkarīgs no jaukšanas tabulas ietilpības (spaiņiem). Parasti, ja slodzes koeficienta vērtība ir lielāka par 0,5, tiek veikta atkārtota pārskatīšana.

  • Divkāršojiet masīva izmēru.
  • Kopējiet iepriekšējā masīva elementus jaunajā masīvā. Mēs izmantojam jaucējfunkciju, vienlaikus kopējot katru mezglu uz jaunu masīvu, tāpēc tas samazinās sadursmi.
  • Izdzēsiet iepriekšējo masīvu no atmiņas un norādiet jaucējkartes iekšējās masīva rādītāju uz šo jauno masīvu.
  • Parasti slodzes koeficients = elementu skaits hash kartē / kopējais segmentu skaits (ietilpība).

Sadursme:

Sadursme ir situācija, kad kausa indekss nav tukšs. Tas nozīmē, ka šajā segmenta indeksā atrodas saistītā saraksta galva. Mums ir divas vai vairākas vērtības, kas saistītas ar vienu un to pašu segmenta indeksu.



Galvenās funkcijas mūsu programmā

  • Ievietošana
  • Meklēt
  • Jaucējfunkcija
  • Dzēst
  • Rehashing

Hash karte

Ieviešana bez atkārtotas apstrādes:

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->taustiņš = atslēga;> >node->vērtība = vērtība;> >node->nākamais = 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->ietilpība = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*)> >* mp->jauda);> >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->jauda)> >+ (((>int>)key[i]) * factor) % mp->jauda)> >% mp->jauda;> >// 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ākamais = 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->taustiņš) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->next = currNode->next;> >}> >free>(currNode);> >break>;> >}> >prevNode = currNode;> >currNode = currNode->nākamais;> >}> >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->taustiņš == taustiņš) {> >return> bucketHead->vērtība;> >}> >bucketHead = bucketHead->nākamais;> >}> >// 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->taustiņš = atslēga;> >node->vērtība = vērtība;> >node->nākamais = 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->ietilpība = 100;> >mp->numOfElements = 0;> >// array of size = 1> >mp->arr = (>struct> node**)>malloc>(>sizeof>(>struct> node*) * mp->jauda);> >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->ietilpība) + (((>int>)key[i]) * factor) % mp->jauda) % mp->kapacitāte;> >// 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ākamais = 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->taustiņš) == 0) {> >// Head node> >// deletion> >if> (currNode == mp->arr[bucketIndex]) {> >mp->arr[bucketIndex] = currNode->next;> >}> >// Last node or middle node> >else> {> >prevNode->next = currNode->next;> }> free>(currNode);> break>;> }> prevNode = currNode;> >currNode = currNode->nākamais;> >}> 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->taustiņš, taustiņš) == 0) {> >return> bucketHead->vērtība;> >}> > >bucketHead = bucketHead->nākamais;> }> // 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;> }> 

>

augšraksts ilustratorā 

>

Izvade 

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

Paskaidrojums:

    ievietošana: ievieto atslēgas vērtību pāri saistītā saraksta sākumā, kas atrodas dotajā segmenta indeksā. hashFunction: sniedz dotās atslēgas segmenta indeksu. Mūsu jaucējfunkcija = rakstzīmes * primeNumber ASCII vērtībax . Mūsu gadījumā galvenais skaitlis ir 31, un atslēgas secīgām rakstzīmēm x vērtība palielinās no 1 līdz n. dzēšana: izdzēš atslēgas-vērtības pāri no jaucēj tabulas dotajai atslēgai. Tas izdzēš mezglu no saistītā saraksta, kurā ir atslēgas un vērtības pāris. Meklēt: meklējiet dotās atslēgas vērtību.
  • Šajā ieviešanā netiek izmantota atkārtotas jaukšanas koncepcija. Tas ir fiksēta lieluma saistīto sarakstu masīvs.
  • Dotajā piemērā gan atslēga, gan vērtība ir virknes.

Laika un telpas sarežģītība:

Hash tabulas ievietošanas un dzēšanas operāciju laika sarežģītība vidēji ir O(1). Ir daži matemātiski aprēķini, kas to pierāda.

    Ievietošanas laika sarežģītība: vidējā gadījumā tā ir nemainīga. Sliktākajā gadījumā tas ir lineārs. Meklēšanas laika sarežģītība: vidējā gadījumā tā ir nemainīga. Sliktākajā gadījumā tas ir lineārs. Dzēšanas laika sarežģītība: vidējos gadījumos tas ir nemainīgs. Sliktākajā gadījumā tas ir lineārs. Telpas sarežģītība: O(n), jo tajā ir n elementu skaits.

Saistītie raksti:

  • Atsevišķa ķēdes sadursmes apstrādes tehnika jaukšanā.