Hash tabel

Selles õpetuses saate teada, mis on räsitabel. Samuti leiate toimivaid näiteid räsitabeli toimingutest C, C ++, Java ja Pythonis.

Räsi tabel on andmestruktuur, mis esindab andmeid võtmeväärtuste paaridena. Iga võti on kaardistatud räsitabeli väärtusega. Klahve kasutatakse väärtuste / andmete indekseerimiseks. Sarnast lähenemist rakendab assotsiatiivne massiiv.

Andmed esitatakse võtmete väärtuste paaris võtmete abil, nagu on näidatud alloleval joonisel. Kõik andmed on seotud võtmega. Võti on täisarv, mis osutab andmetele.

1. Otsene aadressitabel

Otseaadressi tabelit kasutatakse siis, kui tabeli kasutatav ruumihulk pole programmi jaoks probleem. Eeldame seda siin

  • võtmed on väikesed täisarvud
  • võtmete arv ei ole liiga suur ja
  • kahel andmel pole sama võtit

Täisarvude kogumit nimetatakse universumiks U = (0, 1,… ., n-1).
Otseaadressi tabeli iga pesa T(0… n-1)sisaldab kursorit andmetele vastava elemendi kohta.
Massiivi indeks Ton võti ise ja sisu Tosutab komplektile (key, element). Kui võtme jaoks pole elementi, siis jäetakse see nimeks NULL.

Mõnikord on võtmeks ise andmed.

Operatsioonide pseudokood

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

Otse aadressitabeli piirangud

  • Võtme väärtus peaks olema väike.
  • Klahvide arv peab olema piisavalt väike, et see ei ületaks massiivi suuruse piiri.

2. Hash tabel

Räsitabelis töödeldakse võtmeid uue indeksi loomiseks, mis kaardistab vajaliku elemendi. Seda protsessi nimetatakse räsimiseks.

Laskma h(x)olema räsifunktsioon ja kolema võti.
h(k)arvutatakse ja seda kasutatakse elemendi indeksina.

Hash tabeli piirangud

  • Kui sama indeksi tekitab mitme võtme räsifunktsioon, siis tekib konflikt. Seda olukorda nimetatakse kokkupõrkeks.
    Selle vältimiseks valitakse sobiv räsifunktsioon. Kuid kõiki unikaalseid võtmeid on võimatu toota, sest |U|>m. Seega ei pruugi hea räsifunktsioon kokkupõrkeid täielikult takistada, kuid see võib vähendada kokkupõrgete arvu.

Siiski on meil kokkupõrke lahendamiseks muid tehnikaid.

Räsitabeli eelised otseaadressitabeli ees:

Otseaadressitabeli peamised probleemid on massiivi suurus ja võtme võimalik suur väärtus. Räsifunktsioon vähendab indeksi ulatust ja seega väheneb ka massiivi suurus.
Näiteks kui k = 9845648451321, siis h(k) = 11(mõne räsimisfunktsiooni abil). See aitab raisatud mälu kokku hoida, pakkudes 9845648451321massiivi indeksit

Kokkupõrke lahendamine aheldamise teel

Selles tehnikas, kui räsifunktsioon loob sama elemendi mitme elemendi jaoks, salvestatakse need elemendid topeltlingitud loendi abil samasse indeksisse.

Kui see jon mitme elemendi pesa, sisaldab see viidet elementide loendi pealkirjale. Kui ühtegi elementi pole, jsisaldab NIL.

Operatsioonide pseudokood

 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

Pythoni, Java, C ja C ++ juurutamine

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

Head räsifunktsioonid

Hea räsifunktsioonil on järgmised omadused.

  1. See ei tohiks genereerida liiga suuri võtmeid ja ruumi on vähe. Ruumi raisatakse.
  2. Loodavad võtmed ei tohiks olla väga lähedal ega liiga kaugel.
  3. Kokkupõrge tuleb minimeerida nii palju kui võimalik.

Mõned räsimiseks kasutatavad meetodid on:

Jagamismeetod

Kui kon võti ja mräsitabeli suurus, arvutatakse räsifunktsioon h()järgmiselt:

h(k) = k mod m

Näiteks kui räsitabeli suurus on 10ja k = 112siis h(k) = 112mod 10 = 2. Väärtus mei tohi olla 2. Selle põhjuseks on asjaolu, et 2binaarses vormingus volitused on 10, 100, 1000,… . Kui leiame k mod m, saame alati madalama järgu p-bitid.

 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,

  • c1ja on positiivsed abikonstandid,c2
  • i = (0, 1,… .)

Topelt räsimine

Kui kokkupõrge toimub pärast räsifunktsiooni rakendamist h(k), arvutatakse järgmise pilu leidmiseks veel üks räsifunktsioon.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash tabeli rakendused

Hash tabelid on rakendatud kus

  • vaja on pidevat ajaotsingut ja sisestamist
  • krüptograafilised rakendused
  • andmete indekseerimine on vajalik

Huvitavad Artiklid...