Hash-bord

I denne vejledning lærer du, hvad hash-tabel er. Du finder også arbejdseksempler på hash-tabeloperationer i C, C ++, Java og Python.

Hash-tabel er en datastruktur, der repræsenterer data i form af nøgleværdipar . Hver nøgle kortlægges til en værdi i hash-tabellen. Tasterne bruges til indeksering af værdier / data. En lignende tilgang anvendes af et associerende array.

Data er repræsenteret i et nøgleværdipar ved hjælp af nøgler som vist i nedenstående figur. Hver data er knyttet til en nøgle. Nøglen er et heltal, der peger på dataene.

1. Direkte adressetabel

Direkte adressetabel bruges, når mængden af ​​plads, der bruges af tabellen, ikke er et problem for programmet. Her antager vi det

  • nøglerne er små heltal
  • antallet af taster er ikke for stort, og
  • ingen data har den samme nøgle

En pulje af heltal tages kaldet univers U = (0, 1,… ., n-1).
Hver slot i en direkte adressetabel T(0… n-1)indeholder en markør til det element, der svarer til dataene.
Indekset for arrayet Ter selve nøglen, og indholdet af Ter en markør til sættet (key, element). Hvis der ikke er noget element til en nøgle, efterlades det som NULL.

Nogle gange er selve nøglen dataene.

Pseudokode til operationer

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

Begrænsninger i en direkte adressetabel

  • Værdien af ​​nøglen skal være lille.
  • Antallet af nøgler skal være lille nok, så det ikke krydser størrelsesgrænsen for en matrix.

2. Hash-tabel

I en hash-tabel behandles tasterne for at producere et nyt indeks, der kortlægges til det krævede element. Denne proces kaldes hashing.

Lad h(x)være en hash-funktion og kvære en nøgle.
h(k)beregnes, og det bruges som et indeks for elementet.

Begrænsninger ved et Hash-bord

  • Hvis det samme indeks produceres af hash-funktionen til flere nøgler, opstår der konflikt. Denne situation kaldes kollision.
    For at undgå dette vælges en passende hash-funktion. Men det er umuligt at fremstille alle unikke nøgler, fordi |U|>m. Således forhindrer en god hash-funktion muligvis ikke kollisionerne fuldstændigt, men det kan reducere antallet af kollisioner.

Vi har dog andre teknikker til at løse kollision.

Fordele ved hash-tabel i forhold til direkte adressetabel:

De vigtigste problemer med direkte adressetabel er størrelsen på arrayet og den muligvis store værdi af en nøgle. Hashfunktionen reducerer indeksområdet, og dermed reduceres arrayets størrelse også.
For eksempel Hvis k = 9845648451321, så h(k) = 11(ved hjælp af en eller anden hash-funktion). Dette hjælper med at gemme spildt hukommelse, mens du giver indekset 9845648451321til arrayet

Kollisionsopløsning ved kæde

I denne teknik, hvis en hash-funktion producerer det samme indeks for flere elementer, gemmes disse elementer i det samme indeks ved hjælp af en dobbeltkoblet liste.

Hvis jer pladsen til flere elementer, indeholder den en markør til hovedet på listen over elementer. Hvis der ikke er noget element til stede, jindeholder NIL.

Pseudokode til 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 og 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(); )

Gode ​​hashfunktioner

En god hash-funktion har følgende egenskaber.

  1. Det skal ikke generere nøgler, der er for store, og skovlpladsen er lille. Plads er spildt.
  2. De genererede nøgler skal hverken være meget tætte eller for langt inden for rækkevidde.
  3. Kollisionen skal minimeres så meget som muligt.

Nogle af metoderne til hashing er:

Opdelingsmetode

Hvis ker en nøgle og mer størrelsen på hash-tabellen, h()beregnes hash-funktionen som:

h(k) = k mod m

For eksempel Hvis størrelsen på en hash-tabel er 10og k = 112derefter h(k) = 112mod 10 = 2. Værdien af mmå ikke være beføjelserne til 2. Dette skyldes, at beføjelserne 2i binært format er 10, 100, 1000,… . Når vi finder k mod m, får vi altid p-bits af lavere ordre.

 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,

  • c1og er positive hjælpekonstanter,c2
  • i = (0, 1,… .)

Dobbelt hashing

Hvis der opstår en kollision efter anvendelse af en hash-funktion h(k), beregnes en anden hash-funktion til at finde den næste plads.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash tabel applikationer

Hash-tabeller implementeres hvor

  • konstant tidsopslag og indsættelse er påkrævet
  • kryptografiske applikationer
  • indekseringsdata er påkrævet

Interessante artikler...