Hash tabuľka

V tomto tutoriále sa dozviete, čo je hash tabuľka. Nájdete tiež pracovné príklady operácií s hash tabuľkou v jazykoch C, C ++, Java a Python.

Hash tabuľka je dátová štruktúra, ktorá predstavuje údaje vo forme párov kľúč - hodnota . Každý kľúč je namapovaný na hodnotu v hashovacej tabuľke. Kľúče sa používajú na indexovanie hodnôt / údajov. Podobný prístup uplatňuje aj asociatívne pole.

Dáta sú reprezentované v páre kľúč - hodnota pomocou kláves, ako je znázornené na obrázku nižšie. Ku každému údaju je priradený kľúč. Kľúč je celé číslo, ktoré ukazuje na údaje.

1. Tabuľka priamych adries

Tabuľka s priamymi adresami sa používa, keď program nezaberie dostatok miesta v tabuľke. Tu to predpokladáme

  • klávesy sú malé celé čísla
  • počet klávesov nie je príliš veľký a
  • žiadne dve dáta nemajú rovnaký kľúč

Skupina celých čísel sa nazýva vesmír U = (0, 1,… ., n-1).
Každý slot tabuľky s priamymi adresami T(0… n-1)obsahuje ukazovateľ na prvok, ktorý zodpovedá údajom.
Index poľa Tje samotný kľúč a obsah Tje smerníkom na množinu (key, element). Ak pre kľúč neexistuje žiadny prvok, ponechá sa ako NULL.

Kľúčom sú niekedy údaje.

Pseudokód pre operácie

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

Obmedzenia tabuľky priamych adries

  • Hodnota kľúča by mala byť malá.
  • Počet kľúčov musí byť dostatočne malý, aby neprekročil limit veľkosti poľa.

2. Tabuľka hash

V hashovacej tabuľke sú kľúče spracované tak, aby vytvorili nový index, ktorý sa mapuje na požadovaný prvok. Tento proces sa nazýva hash.

Nech h(x)je hashovacia funkcia a kje kľúčom.
h(k)sa vypočíta a použije sa ako index prvku.

Obmedzenia tabuľky hash

  • Ak je hashovou funkciou pre viac kľúčov vytvorený rovnaký index, dôjde ku konfliktu. Táto situácia sa nazýva kolízia.
    Aby sa tomu zabránilo, je zvolená vhodná hashovacia funkcia. Nie je však možné vyrobiť všetky jedinečné kľúče, pretože |U|>m. Dobrá hashovacia funkcia teda nemusí úplne zabrániť kolíziám, môže však znížiť počet kolízií.

Máme však aj iné techniky, ako kolíziu vyriešiť.

Výhody hashovacej tabuľky oproti tabuľke priamych adries:

Hlavné problémy s tabuľkou priamych adries sú veľkosť poľa a pravdepodobne veľká hodnota kľúča. Hašovacia funkcia zmenšuje rozsah indexu a tým sa zmenšuje aj veľkosť poľa.
Napríklad If k = 9845648451321if h(k) = 11( potom pomocou nejakej hashovacej funkcie). To pomáha pri ukladaní zbytočnej pamäte a zároveň poskytuje index 9845648451321poľa

Riešenie kolízie pomocou reťazenia

Ak v tejto technike vytvorí hash funkcia rovnaký index pre viac prvkov, tieto prvky sa uložia do rovnakého indexu pomocou zoznamu, ktorý je dvojnásobne prepojený.

Ak jje slot pre viac prvkov, obsahuje ukazovateľ na záhlavie zoznamu prvkov. Ak nie je prítomný žiadny prvok, jobsahuje NIL.

Pseudokód pre operácie

 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

Implementácia Python, Java, C a 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(); )

Dobré hashovacie funkcie

Dobrá funkcia hash má nasledujúce vlastnosti.

  1. Nemal by generovať príliš veľké kľúče a malý priestor vedra. Priestor je zbytočný.
  2. Vygenerované kľúče by nemali byť ani veľmi blízko, ani príliš ďaleko v dosahu.
  3. Zrážka musí byť čo najviac minimalizovaná.

Niektoré z metód používaných na hašovanie sú:

Metóda delenia

Ak kje kľúč a mmá veľkosť hashovacej tabuľky, hašovacia funkcia h()sa počíta ako:

h(k) = k mod m

Napríklad ak je veľkosť hashovacej tabuľky 10a k = 112potom h(k) = 112mod 10 = 2. Hodnota mnesmie byť v moci 2. Je to tak preto, lebo právomoci 2v binárnom formáte sú 10, 100, 1000,… . Keď nájdeme k mod m, vždy dostaneme p-bity nižšieho rádu.

 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,

  • c1a sú kladné pomocné konštanty,c2
  • i = (0, 1,… .)

Dvojitý hash

Ak po použití hashovacej funkcie dôjde ku kolízii h(k), potom sa pre nájdenie ďalšieho slotu vypočíta ďalšia hashovacia funkcia.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplikácia Hash Table

Hash tabuľky sú implementované kde

  • je potrebné neustále vyhľadávanie a vkladanie
  • kryptografické aplikácie
  • Vyžadujú sa indexovacie údaje

Zaujímavé články...