Hash Table

W tym samouczku dowiesz się, czym jest tabela skrótów. Znajdziesz również działające przykłady operacji na tablicy skrótów w językach C, C ++, Java i Python.

Tabela skrótów to struktura danych reprezentująca dane w postaci par klucz-wartość . Każdy klucz jest mapowany na wartość w tablicy skrótów. Klucze służą do indeksowania wartości / danych. Podobne podejście stosuje tablica asocjacyjna.

Dane są przedstawiane w parze klucz-wartość za pomocą kluczy, jak pokazano na poniższym rysunku. Każde dane jest powiązane z kluczem. Klucz jest liczbą całkowitą wskazującą na dane.

1. Tabela adresów bezpośrednich

Tablica adresów bezpośrednich jest używana, gdy ilość miejsca zajmowanego przez tablicę nie stanowi problemu dla programu. Tutaj zakładamy, że

  • klucze to małe liczby całkowite
  • liczba kluczy nie jest zbyt duża, i
  • żadne dwa dane nie mają tego samego klucza

Pula liczb całkowitych jest nazywana wszechświatem U = (0, 1,… ., n-1).
Każda pozycja tabeli adresów bezpośrednich T(0… n-1)zawiera wskaźnik do elementu, który odpowiada danym.
Indeks tablicy Tto sam klucz, a zawartość Tto wskaźnik do zbioru (key, element). Jeśli nie ma elementu dla klucza, pozostaje on jako NULL.

Czasami sam klucz to dane.

Pseudokod operacji

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

Ograniczenia tabeli adresów bezpośrednich

  • Wartość klucza powinna być mała.
  • Liczba kluczy musi być na tyle mała, aby nie przekraczała limitu rozmiaru tablicy.

2. Hash Table

W tabeli skrótów klucze są przetwarzane w celu utworzenia nowego indeksu, który jest mapowany na wymagany element. Ten proces nazywa się haszowaniem.

Niech h(x)będzie funkcją skrótu i kkluczem.
h(k)jest obliczana i używana jako indeks elementu.

Ograniczenia tabeli skrótów

  • Jeśli ten sam indeks jest tworzony przez funkcję skrótu dla wielu kluczy, powstaje konflikt. Ta sytuacja nazywa się kolizją.
    Aby tego uniknąć, wybierana jest odpowiednia funkcja skrótu. Ale nie można wyprodukować wszystkich unikalnych kluczy, ponieważ |U|>m. Dlatego dobra funkcja skrótu może nie zapobiec całkowicie kolizjom, ale może zmniejszyć liczbę kolizji.

Mamy jednak inne techniki rozwiązywania kolizji.

Zalety tabeli skrótów w porównaniu z tabelą adresów bezpośrednich:

Główne problemy z tabelą adresów bezpośrednich to rozmiar tablicy i możliwie duża wartość klucza. Funkcja skrótu zmniejsza zakres indeksu, a tym samym rozmiar tablicy jest również zmniejszony.
Na przykład If k = 9845648451321, then h(k) = 11(używając funkcji skrótu). Pomaga to w oszczędzaniu zmarnowanej pamięci podczas dostarczania indeksu 9845648451321do tablicy

Rozwiązywanie kolizji przez tworzenie łańcuchów

W tej technice, jeśli funkcja skrótu generuje ten sam indeks dla wielu elementów, elementy te są przechowywane w tym samym indeksie przy użyciu podwójnie połączonej listy.

Jeśli jjest to miejsce na wiele elementów, zawiera wskaźnik do początku listy elementów. Jeśli nie ma elementu, jzawiera NIL.

Pseudokod operacji

 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

Implementacja w Pythonie, Javie, 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 funkcje skrótu

Dobra funkcja skrótu ma następujące cechy.

  1. Nie powinien generować kluczy, które są zbyt duże, a miejsce w zasobniku jest małe. Przestrzeń jest zmarnowana.
  2. Wygenerowane klucze nie powinny znajdować się ani zbyt blisko, ani za daleko.
  3. Kolizję należy maksymalnie zminimalizować.

Niektóre metody używane do haszowania to:

Metoda podziału

Jeśli kjest kluczem i mma rozmiar tabeli skrótów, funkcja skrótu h()jest obliczana jako:

h(k) = k mod m

Na przykład, jeśli rozmiar tablicy skrótów to, 10a k = 112następnie h(k) = 112mod 10 = 2. Wartość mnie może być uprawnieniami 2. Dzieje się tak, ponieważ uprawnienia 2w formacie binarnym są 10, 100, 1000,… . Kiedy znajdziemy k mod m, zawsze otrzymamy bity p niższego rzędu.

 jeśli m = 22, k = 17, to h (k) = 17 mod 22 = 10001 mod 100 = 01 jeśli m = 23, k = 17, to h (k) = 17 mod 22 = 10001 mod 100 = 001 jeśli m = 24, k = 17, to h (k) = 17 mod 22 = 10001 mod 100 = 0001 jeśli m = 2p, to h (k) = p niższe bity m

Metoda mnożenia

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

  • kA mod 1daje część ułamkową kA,
  • ⌊ ⌋ podaje wartość minimalną
  • Ajest jakąkolwiek stałą. Wartość Amieści się w przedziale od 0 do 1. Jednak ≈ (√5-1)/2Knuth zasugeruje optymalny wybór .

Universal Hashing

W haszowaniu uniwersalnym funkcja skrótu jest wybierana losowo niezależnie od kluczy.

Otwórz adresowanie

Wiele wartości może być przechowywanych w pojedynczym gnieździe w normalnej tablicy skrótów.

Korzystając z otwartego adresowania, każda szczelina jest wypełniona jednym klawiszem lub lewą NIL. Wszystkie elementy są przechowywane w samej tablicy skrótów.

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 są dodatnimi stałymi pomocniczymi,c2
  • i = (0, 1,… .)

Podwójne haszowanie

Jeśli kolizja występuje po zastosowaniu funkcji skrótu h(k), obliczana jest kolejna funkcja skrótu w celu znalezienia następnego gniazda.
h(k, i) = (h1(k) + ih2(k)) mod m

Aplikacje tablic skrótów

Tabele skrótów są implementowane tam, gdzie

  • wymagane jest stałe wyszukiwanie i wstawianie
  • aplikacje kryptograficzne
  • wymagane jest indeksowanie danych

Interesujące artykuły...