Hash-tabel

In deze tutorial leer je wat hashtabel is. Ook vindt u werkende voorbeelden van hashtabelbewerkingen in C, C ++, Java en Python.

Hash-tabel is een gegevensstructuur die gegevens vertegenwoordigt in de vorm van sleutel-waardeparen . Elke sleutel is toegewezen aan een waarde in de hashtabel. De sleutels worden gebruikt voor het indexeren van de waarden / gegevens. Een vergelijkbare benadering wordt toegepast door een associatieve array.

Gegevens worden weergegeven in een sleutelwaardepaar met behulp van sleutels, zoals weergegeven in de onderstaande afbeelding. Elke data is gekoppeld aan een sleutel. De sleutel is een geheel getal dat naar de gegevens verwijst.

1. Directe adrestabel

Directe adrestabel wordt gebruikt wanneer de hoeveelheid ruimte die door de tabel wordt gebruikt, geen probleem is voor het programma. Hier nemen we dat aan

  • de sleutels zijn kleine gehele getallen
  • het aantal sleutels is niet te groot, en
  • geen twee gegevens hebben dezelfde sleutel

Een pool van gehele getallen wordt gebruikt, genaamd universe U = (0, 1,… ., n-1).
Elke sleuf van een directe adrestabel T(0… n-1)bevat een pointer naar het element dat overeenkomt met de gegevens.
De index van de array Tis de sleutel zelf en de inhoud van Tis een verwijzing naar de set (key, element). Als er geen element voor een sleutel is, wordt het gelaten als NULL.

Soms zijn de gegevens zelf de sleutel.

Pseudocode voor bewerkingen

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

Beperkingen van een directe adrestabel

  • De waarde van de sleutel moet klein zijn.
  • Het aantal sleutels moet klein genoeg zijn, zodat het de maximale grootte van een array niet overschrijdt.

2. Hash-tabel

In een hashtabel worden de sleutels verwerkt om een ​​nieuwe index te produceren die is toegewezen aan het vereiste element. Dit proces wordt hashing genoemd.

Laat h(x)een hash-functie zijn en keen sleutel zijn.
h(k)wordt berekend en wordt gebruikt als index voor het element.

Beperkingen van een hash-tabel

  • Als dezelfde index wordt geproduceerd door de hash-functie voor meerdere sleutels, ontstaat er een conflict. Deze situatie wordt botsing genoemd.
    Om dit te voorkomen wordt een geschikte hash-functie gekozen. Maar het is onmogelijk om alle unieke sleutels te produceren omdat |U|>m. Dus een goede hash-functie kan de botsingen niet volledig voorkomen, maar het kan het aantal botsingen verminderen.

We hebben echter andere technieken om een ​​botsing op te lossen.

Voordelen van hashtabel ten opzichte van directe adrestabel:

De belangrijkste problemen met de directe adrestabel zijn de grootte van de array en de mogelijk grote waarde van een sleutel. De hash-functie verkleint het bereik van de index en dus wordt ook de grootte van de array verkleind.
Bijvoorbeeld If k = 9845648451321, then h(k) = 11(door een hash-functie te gebruiken). Dit helpt bij het besparen van het verspilde geheugen terwijl de index van 9845648451321aan de array wordt verstrekt

Botsingsresolutie door kettingvorming

Als bij deze techniek een hash-functie dezelfde index produceert voor meerdere elementen, worden deze elementen in dezelfde index opgeslagen met behulp van een dubbel gekoppelde lijst.

Als het jde sleuf voor meerdere elementen is, bevat deze een verwijzing naar de kop van de lijst met elementen. Als er geen element aanwezig is, jbevat NIL.

Pseudocode voor bewerkingen

 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

Implementatie van Python, Java, C en 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(); )

Goede hash-functies

Een goede hashfunctie heeft de volgende kenmerken.

  1. Het mag geen sleutels genereren die te groot zijn en de bucketruimte is klein. Ruimte wordt verspild.
  2. De gegenereerde sleutels mogen niet erg dichtbij of te ver binnen bereik zijn.
  3. De botsing moet zoveel mogelijk worden geminimaliseerd.

Enkele van de methoden die worden gebruikt voor hashing zijn:

Afdelingsmethode

Als het keen sleutel is en mde grootte van de hashtabel is, wordt de hash-functie h()berekend als:

h(k) = k mod m

Als de grootte van een hashtabel bijvoorbeeld is 10en k = 112dan h(k) = 112mod 10 = 2. De waarde van mmag niet de macht zijn van 2. Dit komt doordat de bevoegdheden van 2in binair formaat zijn 10, 100, 1000,… . Als we vinden k mod m, krijgen we altijd de p-bits van lagere orde.

 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,

  • c1en zijn positieve hulpconstanten,c2
  • i = (0, 1,… .)

Dubbele hashing

Als er een botsing optreedt na het toepassen van een hash-functie h(k), wordt een andere hash-functie berekend om de volgende sleuf te vinden.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash Table-toepassingen

Hash-tabellen worden geïmplementeerd waar

  • constante tijd opzoeken en invoegen is vereist
  • cryptografische toepassingen
  • indexeringsgegevens zijn vereist

Interessante artikelen...