Anunțuri

Hash Table este o structură de date care stochează date într-o manieră asociativă. Într-un tabel hash, datele sunt stocate într-un format de matrice, în care fiecare valoare de date are propria sa valoare de index unică. Accesul la date devine foarte rapid dacă cunoaștem indexul datelor dorite.

Astfel, devine o structură de date în care operațiile de inserție și căutare sunt foarte rapide, indiferent de dimensiunea datelor. Hash Table utilizează o matrice ca mediu de stocare și folosește tehnica hash pentru a genera un index în care urmează să fie inserat sau să fie localizat un element.

Hashing

Hashing este o tehnică de conversie a unui interval de valori cheie într-un interval de indexuri ale unei matrice. Vom folosi operatorul modulo pentru a obține un interval de valori cheie. Să considerăm un exemplu de tabel hash de dimensiune 20, iar următoarele elemente urmează să fie stocate. Elementele sunt în formatul (cheie,valoare).

Funcția hash

  • (1,20)
  • (2,70)
  • (42,80)
  • (4,25)
  • (12,44)
  • (14,32)
  • (17,11)
  • (13,78)
  • (37,98)

.

Sr.Nr. Key Hash Array Index
1 1 1 1 % 20 = 1 1
2 2 2 2 % 20 = 2 2
3 42 42 % 20 = 2 2
4 4 4 % 20 = 4 4
5 12 12 % 20 = 12 12
6 14 14 % 20 = 14 14
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 37 % 20 = 17 17

Sondaj liniar

După cum se vede, se poate întâmpla ca tehnica de hașurare să fie utilizată pentru a crea un index deja utilizat al matricei. Într-un astfel de caz, putem căuta următoarea locație goală din array căutând în următoarea celulă până când găsim o celulă goală. Această tehnică se numește sondare liniară.

.

Sr.nr. Key Hash Indexul tabloului După sondarea liniară, Array Index
1 1 1 % 20 = 1 1 1 1
2 2 2 % 20 = 2 2 2
3 42 42 % 20 = 2 2 3
4 4 4 % 20 = 4 4 4
5 12 12 % 20 = 12 12 12
6 14 14 % 20 = 14 14 14
7 17 17 % 20 = 17 17 17
8 13 13 % 20 = 13 13 13
9 37 37 % 20 = 17 17 18

Operații de bază

În continuare sunt prezentate operațiile primare de bază ale unui tabel hash.

  • Cercetare – Caută un element într-un tabel hash.

  • Insertare – Inserează un element într-un tabel hash.

  • Deletare – Șterge un element dintr-un tabel hash.

DataItem

Define un element de date având anumite date și o cheie, pe baza căruia se va efectua căutarea într-un tabel hash.

struct DataItem { int data; int key;};

Metoda hash

Definiți o metodă de hashing pentru a calcula codul hash al cheii elementului de date.

int hashCode(int key){ return key % SIZE;}

Operațiune de căutare

Când trebuie căutat un element, se calculează codul hash al cheii transmise și se localizează elementul folosind acest cod hash ca index în tablou. Folosiți sondarea liniară pentru a obține elementul înainte dacă elementul nu este găsit la codul hash calculat.

Exemplu

struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray != NULL) { if(hashArray->key == key) return hashArray; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Operație de inserare

Când trebuie inserat un element, se calculează codul hash al cheii transmise și se localizează indexul folosind acel cod hash ca index în matrice. În cazul în care se găsește un element la codul hash calculat, se utilizează sondarea liniară pentru o locație goală.

Exemplu

void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray != NULL && hashArray->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray = item; }

Operație de ștergere

Când trebuie șters un element, se calculează codul hash al cheii transmise și se localizează indexul folosind acest cod hash ca index în matrice. Utilizați sondarea liniară pentru a obține elementul înainte dacă nu se găsește un element la codul hash calculat. Atunci când este găsit, stocați acolo un element fictiv pentru a păstra intacte performanțele tabelului hash.

Exemplu

struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray !=NULL) { if(hashArray->key == key) { struct DataItem* temp = hashArray; //assign a dummy item at deleted position hashArray = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Pentru a afla despre implementarea hash în limbajul de programare C, vă rugăm să faceți clic aici.

Publicitate

.