Hash tabela

V tej vadnici boste izvedeli, kaj je hash tabela. Prav tako boste našli delovne primere operacij hash tabel v C, C ++, Java in Python.

Hash tabela je podatkovna struktura, ki predstavlja podatke v obliki parov ključ-vrednost . Vsak ključ je preslikan na vrednost v razpršeni tabeli. Tipke se uporabljajo za indeksiranje vrednosti / podatkov. Podoben pristop uporablja asociativna matrika.

Podatki so predstavljeni v paru vrednosti ključev s pomočjo tipk, kot je prikazano na spodnji sliki. Vsak podatek je povezan s ključem. Ključ je celo število, ki kaže na podatke.

1. Tabela neposrednih naslovov

Tabela z neposrednimi naslovi se uporablja, če količina prostora, ki ga tabela uporablja, za program ni težava. Tu predpostavljamo

  • tipke so majhna cela števila
  • število tipk ni preveliko in
  • dva podatka nimata istega ključa

Skupina celih števil se imenuje vesolje U = (0, 1,… ., n-1).
Vsaka reža tabele z neposrednimi naslovi T(0… n-1)vsebuje kazalec na element, ki ustreza podatkom.
Indeks matrike Tje sam ključ, vsebina Tpa je kazalec na niz (key, element). Če za ključ potem ni elementa, ostane kot NULL.

Včasih so ključ sami podatki.

Psevkodo za operacije

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

Omejitve tabele z neposrednimi naslovi

  • Vrednost ključa mora biti majhna.
  • Število ključev mora biti dovolj majhno, da ne presega meje velikosti matrike.

2. Hash tabela

V razpršeni tabeli se ključi obdelajo, da se ustvari nov indeks, ki se preslika v zahtevani element. Ta postopek se imenuje razprševanje.

Naj h(x)bo zgoščevalna funkcija in kključ.
h(k)se izračuna in se uporablja kot indeks za element.

Omejitve zgoščenke

  • Če potem indeks ustvari zgoščevalna funkcija za več ključev, pride do konflikta. Ta situacija se imenuje trk.
    Da bi se temu izognili, je izbrana ustrezna zgoščevalna funkcija. Ampak nemogoče je izdelati vse unikatne ključe, ker |U|>m. Tako dobra zgoščevalna funkcija morda ne bo popolnoma preprečila trkov, lahko pa zmanjša število trkov.

Vendar imamo druge tehnike za reševanje trka.

Prednosti hash tabele pred tabelo z neposrednimi naslovi:

Glavni problemi s tabelo z neposrednimi naslovi so velikost matrike in morda velika vrednost ključa. Funkcija zgoščevanja zmanjša obseg indeksa in s tem se zmanjša tudi velikost matrike.
Na primer, če k = 9845648451321, potem h(k) = 11(z uporabo neke zgoščevalne funkcije). To pomaga pri varčevanju zapravljenega pomnilnika, hkrati pa zagotavlja indeks 9845648451321polja

Rešitev trka z veriženjem

Če pri tej tehniki hash-funkcija ustvari enak indeks za več elementov, se ti elementi shranijo v isti indeks z uporabo dvojno povezanega seznama.

Če jje reža za več elementov, vsebuje kazalec na glavo seznama elementov. Če element ni prisoten, jvsebuje NIL.

Psevkodo 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

Izvajanje Pythona, Java, C in 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 funkcije razpršitve

Dobra zgoščevalna funkcija ima naslednje značilnosti.

  1. Ne sme ustvarjati prevelikih ključev in majhnega prostora v vedrih. Prostor je zapravljen.
  2. Ustvarjeni ključi ne smejo biti niti zelo blizu niti predaleč.
  3. Trčenje je treba čim bolj zmanjšati.

Nekatere metode, ki se uporabljajo za zgoščevanje, so:

Metoda delitve

Če kje ključ in mje velikost razpredelnice, se funkcija razpršitve h()izračuna kot:

h(k) = k mod m

Na primer, če je velikost hash tabele 10in k = 112potem h(k) = 112mod 10 = 2. Vrednost mne sme biti v pristojnosti 2. To je zato, ker so pooblastila 2v binarni obliki 10, 100, 1000,… . Ko najdemo k mod m, bomo vedno dobili p-bitov nižjega 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,

  • c1in so pozitivne pomožne konstante,c2
  • i = (0, 1,… .)

Dvojno razprševanje

Če pride do trčenja po uporabi zgoščevalne funkcije h(k), se za iskanje naslednje reže izračuna druga zgoščevalna funkcija.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplikacije za razpršeno tabelo

Hash tabele se izvajajo tam, kjer

  • zahteva se stalno iskanje in vstavljanje
  • kriptografske aplikacije
  • potrebni so podatki za indeksiranje

Zanimive Članki...