Hash-bord

I denna handledning lär du dig vad hash-tabell är. Du hittar också arbetsexempel på hash-tabellåtgärder i C, C ++, Java och Python.

Hash-tabell är en datastruktur som representerar data i form av nyckel-värdepar . Varje nyckel mappas till ett värde i hashtabellen. Nycklarna används för att indexera värden / data. Ett liknande tillvägagångssätt tillämpas av en associativ array.

Data representeras i ett nyckelvärdepar med hjälp av tangenter som visas i figuren nedan. Varje data är associerad med en nyckel. Nyckeln är ett heltal som pekar på data.

1. Direkt adressbord

Direktadresstabell används när mängden utrymme som används av tabellen inte är ett problem för programmet. Här antar vi att

  • nycklarna är små heltal
  • antalet nycklar är inte för stort, och
  • inga två data har samma nyckel

En pool av heltal tas som kallas universum U = (0, 1,… ., n-1).
Varje plats i en direkt adresstabell T(0… n-1)innehåller en pekare till det element som motsvarar data.
Matrisens index Tär själva nyckeln och innehållet i Tär en pekare till uppsättningen (key, element). Om det inte finns något element för en nyckel, lämnas den som NULL.

Ibland är själva nyckeln data.

Pseudokod för operationer

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

Begränsningar av en direkt adresstabell

  • Nyckelns värde bör vara litet.
  • Antalet nycklar måste vara tillräckligt små så att det inte passerar storleksgränsen för en matris.

2. Hash-tabell

I en hash-tabell bearbetas nycklarna för att producera ett nytt index som mappar till önskat element. Denna process kallas hashing.

Låt h(x)vara en hash-funktion och kvara en nyckel.
h(k)beräknas och det används som ett index för elementet.

Begränsningar av en Hash-tabell

  • Om samma index produceras av hash-funktionen för flera tangenter uppstår konflikt. Denna situation kallas kollision.
    För att undvika detta väljs en lämplig hashfunktion. Men det är omöjligt att producera alla unika nycklar för |U|>m. Således kan en bra hashfunktion inte förhindra kollisionerna helt, men det kan minska antalet kollisioner.

Vi har dock andra tekniker för att lösa kollision.

Fördelar med hash-tabell jämfört med direkt adresstabell:

De viktigaste problemen med direktadresstabellen är storleken på matrisen och det möjliga stora värdet på en nyckel. Hashfunktionen minskar indexområdet och därmed minskar också arrayens storlek.
Till exempel Om k = 9845648451321, då h(k) = 11(med någon hash-funktion). Detta hjälper till att spara minnet som går till spillo samtidigt som det ger indexet 9845648451321till arrayen

Kollisionsupplösning genom kedjning

I den här tekniken, om en hash-funktion ger samma index för flera element, lagras dessa element i samma index med hjälp av en dubbelt länkad lista.

Om jär platsen för flera element, innehåller den en pekare till huvudet på listan över element. Om inget element finns, jinnehåller NIL.

Pseudokod för operationer

 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

Python, Java, C och C ++ Implementering

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(); )

Good Hash Functions

A good hash function has the following characteristics.

  1. It should not generate keys that are too large and the bucket space is small. Space is wasted.
  2. The keys generated should be neither very close nor too far in range.
  3. The collision must be minimized as much as possible.

Some of the methods used for hashing are:

Division Method

If k is a key and m is the size of the hash table, the hash function h() is calculated as:

h(k) = k mod m

For example, If the size of a hash table is 10 and k = 112 then h(k) = 112 mod 10 = 2. The value of m must not be the powers of 2. This is because the powers of 2 in binary format are 10, 100, 1000,… . When we find k mod m, we will always get the lower order p-bits.

 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,

  • c1och är positiva hjälpkonstanter,c2
  • i = (0, 1,… .)

Dubbel hasning

Om en kollision inträffar efter applicering av en hash-funktion h(k)beräknas en annan hash-funktion för att hitta nästa plats.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash-tabellapplikationer

Hash-tabeller implementeras var

  • konstant tidsuppsläckning och insättning krävs
  • kryptografiska applikationer
  • indexeringsdata krävs

Intressanta artiklar...