Hash tablica

U ovom uputstvu naučit ćete što je hash tablica. Također ćete naći radne primjere operacija hash tablice na C, C ++, Java i Python.

Hash tablica je struktura podataka koja predstavlja podatke u obliku parova ključ / vrijednost . Svaki se ključ preslikava na vrijednost u hash tablici. Tipke se koriste za indeksiranje vrijednosti / podataka. Sličan pristup primjenjuje asocijativni niz.

Podaci su predstavljeni u paru vrijednosti ključeva uz pomoć tipki kao što je prikazano na donjoj slici. Svaki je podatak povezan s ključem. Ključ je cijeli broj koji upućuje na podatke.

1. Tablica izravnih adresa

Tablica izravnih adresa koristi se kada količina prostora koju tablica ne predstavlja problem za program. Ovdje to pretpostavljamo

  • tipke su male cijele brojeve
  • broj tipki nije prevelik, i
  • niti jedan podatak nema isti ključ

Skup cjelih brojeva uzima se kao svemir U = (0, 1,… ., n-1).
Svaki utor tablice izravnih adresa T(0… n-1)sadrži pokazivač na element koji odgovara podacima.
Indeks niza Tje sam ključ, a sadržaj Tpokazivača na skup (key, element). Ako tada nema elementa za ključ, ostaje kao NULL.

Ponekad su ključ sami podaci.

Pseudokod za operacije

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

Ograničenja tablice izravnih adresa

  • Vrijednost ključa trebala bi biti mala.
  • Broj tipki mora biti dovoljno mali da ne prijeđe ograničenje veličine polja.

2. Hash tablica

U hash tablici tipke se obrađuju kako bi se dobio novi indeks koji se preslikava na traženi element. Taj se postupak naziva raspršivanje.

Dopustiti h(x)biti hash funkcija i kbiti ključ.
h(k)izračunava se i koristi se kao indeks za element.

Ograničenja hash tablice

  • Ako isti indeks proizvodi hash funkcija za više ključeva, tada dolazi do sukoba. Ta se situacija naziva sudarom.
    Da bi se to izbjeglo, odabire se prikladna hash funkcija. Ali, nemoguće je proizvesti sve jedinstvene ključeve jer |U|>m. Stoga dobra hash funkcija možda neće u potpunosti spriječiti sudare, ali može smanjiti broj sudara.

Međutim, imamo i druge tehnike za rješavanje sudara.

Prednosti hash tablice nad tablicom izravnih adresa:

Glavni problemi s tablicom izravnih adresa su veličina polja i moguće velika vrijednost ključa. Hash funkcija smanjuje raspon indeksa, a time se smanjuje i veličina polja.
Na primjer, ako k = 9845648451321, tada h(k) = 11(pomoću neke hash funkcije). To pomaže u spremanju izgubljene memorije uz istovremeno davanje indeksa 9845648451321nizu

Rješavanje sudara lančanim postupkom

U ovoj tehnici, ako hash funkcija stvara isti indeks za više elemenata, ti se elementi pohranjuju u isti indeks pomoću dvostruko povezane liste.

Ako jje utor za više elemenata, sadrži pokazivač na glavu popisa elemenata. Ako nije prisutan nijedan element, jsadrži NIL.

Pseudokod za operacije

 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

Implementacija Pythona, 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(); )

Dobre hash funkcije

Dobra hash funkcija ima sljedeće značajke.

  1. Ne bi trebao generirati prevelike ključeve, a prostora u segmentu je malo. Prostor se troši.
  2. Generirani ključevi ne smiju biti niti vrlo blizu niti predaleko u dometu.
  3. Sudar mora biti što je moguće manji.

Neke od metoda koje se koriste za raspršivanje su:

Metoda podjele

Ako kje ključ i mveličina je hash tablice, hash funkcija h()izračunava se kao:

h(k) = k mod m

Na primjer, Ako je veličina hash tablice, 10a k = 112zatim h(k) = 112mod 10 = 2. Vrijednost mne smije biti moć 2. To je zato što su moći 2u binarnom formatu 10, 100, 1000,… . Kad pronađemo k mod m, uvijek ćemo dobiti p-bitove nižeg reda.

 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,

  • c1i pozitivne su pomoćne konstante,c2
  • i = (0, 1,… .)

Dvostruko raspršivanje

Ako se sudar dogodi nakon primjene hash funkcije h(k), tada se izračuna druga hash funkcija za pronalaženje sljedećeg utora.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplikacije hash tablice

Hash tablice se implementiraju tamo gdje

  • potrebno je stalno traženje i umetanje vremena
  • kriptografske primjene
  • podaci o indeksiranju su potrebni

Zanimljivi članci...