Hash-bord

I denne opplæringen lærer du hva hash-tabellen er. Du vil også finne eksempler på hash-tabelloperasjoner i C, C ++, Java og Python.

Hash-tabell er en datastruktur som representerer data i form av nøkkelverdipar . Hver nøkkel tilordnes til en verdi i hashtabellen. Tastene brukes til å indeksere verdiene / dataene. En lignende tilnærming brukes av en assosiativ matrise.

Data er representert i et nøkkelverdipar ved hjelp av nøkler som vist i figuren nedenfor. Hver data er tilknyttet en nøkkel. Nøkkelen er et helt tall som peker på dataene.

1. Direkte adressetabell

Direkte adressetabell brukes når mengden plass som brukes av tabellen ikke er et problem for programmet. Her antar vi det

  • tastene er små heltall
  • antall nøkler er ikke for stort, og
  • ingen data har samme nøkkel

En gruppe med heltall er tatt kalt univers U = (0, 1,… ., n-1).
Hvert spor i en direkte adressetabell T(0… n-1)inneholder en peker til elementet som tilsvarer dataene.
Indeksen til matrisen Ter selve nøkkelen, og innholdet Ter en peker til settet (key, element). Hvis det ikke er noe element for en nøkkel, blir den igjen som NULL.

Noen ganger er selve nøkkelen dataene.

Pseudokode for operasjoner

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

Begrensninger for en direkte adressetabell

  • Verdien på nøkkelen skal være liten.
  • Antall nøkler må være lite nok til at den ikke krysser størrelsesgrensen for en matrise.

2. Hash-bord

I en hash-tabell blir tastene behandlet for å produsere en ny indeks som tilordnes til ønsket element. Denne prosessen kalles hashing.

La h(x)være en hash-funksjon og kvære en nøkkel.
h(k)beregnes og den brukes som en indeks for elementet.

Begrensninger av et Hash-bord

  • Hvis den samme indeksen produseres av hash-funksjonen for flere taster, oppstår konflikt. Denne situasjonen kalles kollisjon.
    For å unngå dette velges en passende hashfunksjon. Men det er umulig å produsere alle unike nøkler fordi |U|>m. En god hashfunksjon forhindrer kanskje ikke kollisjonene helt, men det kan redusere antall kollisjoner.

Imidlertid har vi andre teknikker for å løse kollisjon.

Fordeler med hasjbord over direkte adressetabell:

Hovedproblemene med direkte adressetabell er størrelsen på matrisen og den muligens store verdien til en nøkkel. Hashfunksjonen reduserer indeksområdet, og dermed reduseres også størrelsen på matrisen.
For eksempel Hvis k = 9845648451321, deretter h(k) = 11(ved å bruke en eller annen hashfunksjon). Dette hjelper til med å lagre minnet som er bortkastet mens du gir indeksen 9845648451321til matrisen

Kollisjonsoppløsning ved å lenke

I denne teknikken, hvis en hash-funksjon produserer den samme indeksen for flere elementer, lagres disse elementene i samme indeks ved å bruke en dobbeltkoblet liste.

Hvis jer spor for flere elementer, inneholder den en peker til hodet på listen over elementer. Hvis det ikke er noe element, jinneholder NIL.

Pseudokode for operasjoner

 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 ​​Hash-funksjoner

En god hashfunksjon har følgende egenskaper.

  1. Det skal ikke generere nøkler som er for store og bøtteplassen er liten. Plass er bortkastet.
  2. Tastene som genereres, bør ikke være veldig nærme eller for langt innen rekkevidde.
  3. Kollisjonen må minimeres så mye som mulig.

Noen av metodene som brukes til hashing er:

Inndelingsmetode

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

h(k) = k mod m

For eksempel Hvis størrelsen på en hash-tabell er 10og k = 112deretter h(k) = 112mod 10 = 2. Verdien av mmå ikke være kreftene til 2. Dette er fordi kreftene 2i binært format er 10, 100, 1000,… . Når vi finner k mod m, vil vi alltid få lavere ordens p-biter.

 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 hjelpekonstanter,c2
  • i = (0, 1,… .)

Dobbel hashing

Hvis det oppstår en kollisjon etter å ha brukt en hash-funksjon h(k), beregnes en annen hash-funksjon for å finne neste spor.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash-bord-applikasjoner

Hash-tabeller er implementert hvor

  • konstant tidssøking og innsetting er nødvendig
  • kryptografiske applikasjoner
  • indekseringsdata er påkrevd

Interessante artikler...