Hash-taulukko

Tässä opetusohjelmassa opit, mikä hash-taulukko on. Löydät myös toimivia esimerkkejä hash-taulukon toiminnoista C-, C ++ -, Java- ja Python-versioissa.

Hash-taulukko on tietorakenne, joka edustaa tietoja avainarvoparien muodossa . Jokainen avain on yhdistetty hash-taulukon arvoon. Näppäimiä käytetään arvojen / tietojen indeksointiin. Samanlaista lähestymistapaa soveltaa assosiatiivinen taulukko.

Tiedot esitetään avainarvoparissa avainten avulla alla olevan kuvan mukaisesti. Jokainen data liittyy avain. Avain on kokonaisluku, joka osoittaa tietoihin.

1. Suora osoitetaulukko

Suoraa osoitetaulukkoa käytetään, kun taulukon käyttämä tila ei ole ongelma ohjelmalle. Tässä oletamme sen

  • avaimet ovat pieniä kokonaislukuja
  • näppäinten lukumäärä ei ole liian suuri ja
  • kahdella tiedolla ei ole samaa avainta

Kokonaislukujen joukkoa kutsutaan universumiksi U = (0, 1,… ., n-1).
Suoran osoitetaulukon jokainen paikka T(0… n-1)sisältää osoittimen tietoja vastaavalle elementille.
Taulukon hakemisto Ton itse avain ja sen sisältö on osoitus Tjoukolle (key, element). Jos avaimelle ei ole elementtiä, se jätetään nimellä NULL.

Joskus avain itsessään on data.

Pseudokoodi toiminnoille

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

Suoran osoitetaulukon rajoitukset

  • Avaimen arvon tulisi olla pieni.
  • Avainten lukumäärän on oltava riittävän pieni, jotta se ei ylitä matriisin kokorajoitusta.

2. Hash-taulukko

Hajautustaulukossa avaimet käsitellään tuottamaan uusi hakemisto, joka kartoittaa vaaditun elementin. Tätä prosessia kutsutaan hajautukseksi.

Antaa h(x)olla hash-funktio ja kolla avain.
h(k)lasketaan ja sitä käytetään elementin indeksinä.

Hash-taulukon rajoitukset

  • Jos saman indeksin tuottaa hash-toiminto useille avaimille, syntyy ristiriita. Tätä tilannetta kutsutaan törmäykseksi.
    Tämän välttämiseksi valitaan sopiva hajautusfunktio. Mutta on mahdotonta tuottaa kaikkia ainutlaatuisia avaimia, koska |U|>m. Siksi hyvä hash-toiminto ei välttämättä estä törmäyksiä kokonaan, mutta se voi kuitenkin vähentää törmäysten määrää.

Meillä on kuitenkin muita tekniikoita törmäyksen ratkaisemiseksi.

Hajataulukon edut suoraan osoitetaulukkoon nähden:

Suoran osoitetaulukon tärkeimmät kysymykset ovat taulukon koko ja avaimen mahdollisesti suuri arvo. Hajautusfunktio vähentää indeksin aluetta ja siten myös matriisin koko pienenee.
Esimerkiksi Jos k = 9845648451321, sitten h(k) = 11(käyttämällä jotakin hajautusfunktiota). Tämä auttaa säästämään hukkaan menevää muistia ja tarjoaa samalla 9845648451321taulukon indeksin

Törmäyksen ratkaisu ketjuamalla

Tässä tekniikassa, jos hash-funktio tuottaa saman indeksin useille elementeille, nämä elementit tallennetaan samaan hakemistoon käyttämällä kaksinkertaisesti linkitettyä luetteloa.

Jos jon paikka useille elementeille, se sisältää osoittimen elementtiluettelon päähän. Jos elementtiä ei ole, jsisältää NIL.

Pseudokoodi toiminnoille

 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 ja C ++ -toteutus

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

Hyvät hash-toiminnot

Hyvällä hash-toiminnolla on seuraavat ominaisuudet.

  1. Se ei saa luoda avaimia, jotka ovat liian suuria ja ämpäritila on pieni. Tila on hukkaan.
  2. Luotujen avainten ei tulisi olla hyvin lähellä tai liian kaukana.
  3. Törmäys on minimoitava mahdollisimman paljon.

Jotkut hajautusmenetelmistä ovat:

Jaottomenetelmä

Jos kon avain ja mhash-taulukon koko, hash-funktio h()lasketaan seuraavasti:

h(k) = k mod m

Esimerkiksi, jos hash-taulukon koko on 10ja k = 112sitten h(k) = 112mod 10 = 2. Arvon arvo mei saa olla 2. Tämä johtuu siitä, että 2binäärimuodossa olevat valtuudet ovat 10, 100, 1000,… . Kun löydämme k mod m, saamme aina alemman asteen p-bitit.

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

Kaksinkertainen hajautus

Jos törmäys tapahtuu hajautusfunktion soveltamisen jälkeen h(k), lasketaan toinen hajautusfunktio seuraavan paikan löytämiseksi.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash-taulukon sovellukset

Hash-taulukot toteutetaan missä

  • jatkuva haku ja lisäys vaaditaan
  • salaussovellukset
  • indeksointitiedot vaaditaan

Mielenkiintoisia artikkeleita...