Hash táblázat

Ebben az oktatóanyagban megtudhatja, mi a hash tábla. A hash tábla műveleteinek működő példáit is megtalálja C, C ++, Java és Python nyelven.

A hash tábla egy adatstruktúra, amely kulcs-érték párok formájában ábrázolja az adatokat . Minden kulcs egy hash tábla értékéhez van hozzárendelve. A kulcsok az értékek / adatok indexelésére szolgálnak. Hasonló megközelítést alkalmaz egy asszociatív tömb.

Az adatokat kulcsérték párban ábrázoljuk a kulcsok segítségével, az alábbi ábrán látható módon. Minden adat társítva van egy kulccsal. A kulcs egy egész szám, amely az adatokra mutat.

1. Közvetlen címtábla

A közvetlen címtáblát akkor használják, ha a táblázat által használt hely nagysága nem jelent problémát a program számára. Itt ezt feltételezzük

  • a kulcsok kis egész számok
  • a billentyűk száma nem túl nagy, és
  • nincs két azonos kulcs kulcsa

Az egészek halmazát univerzumnak nevezzük U = (0, 1,… ., n-1).
A közvetlen címtábla minden nyílása T(0… n-1)tartalmaz egy mutatót az elemnek, amely megfelel az adatoknak.
A tömb indexe Tmaga a kulcs, a tartalma pedig Ta halmaz mutatója (key, element). Ha akkor nincs elem egy kulcshoz, akkor az marad NULL.

Néha maga a kulcs az adat.

Pszeudokód műveletekhez

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

A közvetlen címtábla korlátai

  • A kulcs értékének kicsinek kell lennie.
  • A kulcsok számának elég kicsinek kell lennie ahhoz, hogy ne lépje át egy tömb méretkorlátját.

2. Hash táblázat

A hash táblában a kulcsok feldolgozásával új index jön létre, amely leképezi a kívánt elemet. Ezt a folyamatot hash-nak hívják.

Legyen h(x)hash függvény és klegyen kulcs.
h(k)kiszámításra kerül, és indexként használják az elemhez.

Hash táblázat korlátai

  • Ha ugyanazt az indexet több kulcs kulcsának hash függvénye hozza létre, akkor konfliktus keletkezik. Ezt a helyzetet ütközésnek nevezzük.
    Ennek elkerülése érdekében egy megfelelő kivonatolási funkciót választanak. De lehetetlen minden egyedi kulcsot előállítani, mert |U|>m. Így a jó hash funkció nem biztos, hogy teljesen megakadályozza az ütközéseket, ugyanakkor csökkentheti az ütközések számát.

Az ütközés feloldására azonban más technikáink is vannak.

A hash-tábla előnyei a közvetlen címtáblával szemben:

A közvetlen címtábla fő kérdései a tömb mérete és egy kulcs esetleg nagy értéke. A hash függvény csökkenti az index tartományát, és így a tömb mérete is csökken.
Például az If k = 9845648451321, akkor h(k) = 11(valamilyen kivonatolási funkció használatával). Ez segít az elpazarolt memória megtakarításában, miközben megadja 9845648451321a tömb indexét

Ütközés feloldása láncolással

Ebben a technikában, ha egy hash függvény ugyanazt az indexet hozza létre több elem számára, akkor ezeket az elemeket ugyanabban az indexben tárolják egy kétszeresen összekapcsolt lista használatával.

Ha ja rés több elemre vonatkozik, akkor mutatót tartalmaz az elemek listájának fejlécére. Ha nincs elem, akkor jtartalmaz NIL.

Pszeudokód műveletekhez

 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 és C ++ megvalósítás

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

Jó hash funkciók

A jó hash függvény a következő jellemzőkkel rendelkezik.

  1. Nem szabad túl nagy kulcsokat generálnia, és a tárterület kicsi. Hely elpazarolt.
  2. A létrehozott kulcsoknak nem lehetnek sem nagyon közeli, sem pedig túl távoli tartományban.
  3. Az ütközést a lehető legkisebbre kell csökkenteni.

A kivonatolásra használt néhány módszer a következő:

Osztási módszer

Ha kkulcs és ma hash tábla mérete, akkor a hash függvény h()kiszámítása a következő:

h(k) = k mod m

Például, ha akkora, mint egy hash tábla 10és k = 112ezután h(k) = 112mod 10 = 2. A értéke mnem lehet a hatásköre 2. Ez azért van, mert a 2bináris formátumban szereplő hatáskörök 10, 100, 1000,… . Ha megtaláljuk k mod m, mindig megkapjuk az alacsonyabb rendű p-biteket.

 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,

  • c1és pozitív segédállandók,c2
  • i = (0, 1,… .)

Dupla hash

Ha ütközés történik egy kivonatolási funkció alkalmazása után h(k), akkor egy újabb kivonatolási funkciót számolnak ki a következő rés megtalálásához.
h(k, i) = (h1(k) + ih2(k)) mod m

Hash Table alkalmazások

A hash táblákat ott valósítják meg, ahol

  • állandó idejű keresésre és beillesztésre van szükség
  • kriptográfiai alkalmazások
  • indexelési adatokra van szükség

érdekes cikkek...