Hash Table

În acest tutorial, veți afla ce este tabelul hash. De asemenea, veți găsi exemple de lucru ale operațiilor de tabel hash în C, C ++, Java și Python.

Hash table este o structură de date care reprezintă date sub formă de perechi cheie-valoare . Fiecare cheie este mapată la o valoare din tabelul hash. Tastele sunt utilizate pentru indexarea valorilor / datelor. O abordare similară este aplicată de o matrice asociativă.

Datele sunt reprezentate într-o pereche de valori cheie cu ajutorul tastelor, așa cum se arată în figura de mai jos. Fiecare dată este asociată cu o cheie. Cheia este un număr întreg care indică datele.

1. Tabel de adrese directe

Tabelul de adrese directe este utilizat atunci când spațiul folosit de tabel nu reprezintă o problemă pentru program. Aici, presupunem că

  • cheile sunt numere întregi mici
  • numărul de taste nu este prea mare și
  • nu există două date care au aceeași cheie

Se ia un bazin de numere întregi numit univers U = (0, 1,… ., n-1).
Fiecare slot al unui tabel de adrese directe T(0… n-1)conține un indicator către elementul care corespunde datelor.
Indexul matricei Teste cheia în sine, iar conținutul Teste un indicator către set (key, element). Dacă nu există nici un element pentru o cheie , atunci, acesta este lăsat ca NULL.

Uneori, cheia în sine este datele.

Pseudocod pentru operații

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Limitările unui tabel de adrese directe

  • Valoarea cheii trebuie să fie mică.
  • Numărul de taste trebuie să fie suficient de mic, astfel încât să nu depășească limita de dimensiune a unui tablou.

2. Hash Table

Într-un tabel hash, cheile sunt procesate pentru a produce un nou index care mapează elementul cerut. Acest proces se numește hashing.

Să h(x)fie o funcție hash și să kfie o cheie.
h(k)este calculat și este utilizat ca index pentru element.

Limitările unui tabel Hash

  • Dacă același index este produs de funcția hash pentru mai multe taste, atunci apare un conflict. Această situație se numește coliziune.
    Pentru a evita acest lucru, este aleasă o funcție hash adecvată. Dar, este imposibil să se producă toate cheile unice, deoarece |U|>m. Astfel, o funcție de hash bună nu poate preveni coliziunile complet, dar poate reduce numărul de coliziuni.

Cu toate acestea, avem alte tehnici pentru rezolvarea coliziunii.

Avantajele tabelului hash față de tabelul de adrese directe:

Principalele probleme cu tabelul de adrese directe sunt dimensiunea matricei și valoarea posibilă a unei chei. Funcția hash reduce intervalul de index și, astfel, dimensiunea matricei este, de asemenea, redusă.
De exemplu, Dacă k = 9845648451321, atunci h(k) = 11(prin utilizarea unei funcții hash). Acest lucru ajută la salvarea memoriei irosite în timp ce furnizați indexul 9845648451321matricei

Rezoluția coliziunii prin înlănțuire

În această tehnică, dacă o funcție hash produce același index pentru mai multe elemente, aceste elemente sunt stocate în același index folosind o listă dublă legată.

Dacă jeste slotul pentru mai multe elemente, acesta conține un indicator către capul listei de elemente. Dacă nu este prezent niciun element, jconține NIL.

Pseudocod pentru operații

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Implementare Python, Java, C și C ++

Python Java C C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::iterator i; for (i = table(index).begin(); i != table(index).end(); i++) ( if (*i == key) break; ) if (i != table(index).end()) table(index).erase(i); ) void HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

Funcții Hash bune

O funcție hash bună are următoarele caracteristici.

  1. Nu ar trebui să genereze chei prea mari, iar spațiul bucket-ului este mic. Spațiul este irosit.
  2. Cheile generate nu trebuie să fie nici foarte apropiate, nici prea îndepărtate.
  3. Coliziunea trebuie minimizată cât mai mult posibil.

Unele dintre metodele utilizate pentru hashing sunt:

Metoda diviziunii

Dacă keste o cheie și mare dimensiunea tabelului hash, funcția hash h()este calculată astfel:

h(k) = k mod m

De exemplu, dacă dimensiunea unui tabel hash este 10și k = 112apoi h(k) = 112mod 10 = 2. Valoarea lui mnu trebuie să fie puterile 2. Acest lucru se datorează faptului că puterile 2în format binar sunt 10, 100, 1000,… . Când vom găsi k mod m, vom obține întotdeauna p-biți de ordinul inferior.

 if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m

Multiplication Method

h(k) = ⌊m(kA mod 1)⌋
where,

  • kA mod 1 gives the fractional part kA,
  • ⌊ ⌋ gives the floor value
  • A is any constant. The value of A lies between 0 and 1. But, an optimal choice will be ≈ (√5-1)/2 suggested by Knuth.

Universal Hashing

In Universal hashing, the hash function is chosen at random independent of keys.

Open Addressing

Multiple values can be stored in a single slot in a normal hash table.

By using open addressing, each slot is either filled with a single key or left NIL. All the elements are stored in the hash table itself.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1și sunt constante auxiliare pozitive,c2
  • i = (0, 1,… .)

Dublu hashing

Dacă are loc o coliziune după aplicarea unei funcții hash h(k), atunci se calculează o altă funcție hash pentru a găsi următorul slot.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplicații Hash Table

Hash tabele sunt implementate în cazul în care

  • este necesară căutarea și inserarea în timp constant
  • aplicații criptografice
  • sunt necesare date de indexare

Articole interesante...