Πίνακας κατακερματισμού

Σε αυτό το σεμινάριο, θα μάθετε τι είναι ο πίνακας κατακερματισμού. Επίσης, θα βρείτε λειτουργικά παραδείγματα λειτουργιών πίνακα κατακερματισμού σε C, C ++, Java και Python.

Ο πίνακας κατακερματισμού είναι μια δομή δεδομένων που αντιπροσωπεύει δεδομένα με τη μορφή ζευγών κλειδιών-τιμών . Κάθε κλειδί αντιστοιχεί σε μια τιμή στον πίνακα κατακερματισμού. Τα πλήκτρα χρησιμοποιούνται για την ευρετηρίαση των τιμών / δεδομένων. Μια παρόμοια προσέγγιση εφαρμόζεται από έναν συσχετιστικό πίνακα.

Τα δεδομένα παρουσιάζονται σε ένα ζεύγος τιμών κλειδιών με τη βοήθεια των πλήκτρων όπως φαίνεται στο παρακάτω σχήμα. Κάθε δεδομένα σχετίζεται με ένα κλειδί. Το κλειδί είναι ένας ακέραιος αριθμός που δείχνει τα δεδομένα.

1. Πίνακας άμεσων διευθύνσεων

Ο πίνακας άμεσων διευθύνσεων χρησιμοποιείται όταν το μέγεθος του χώρου που χρησιμοποιείται από τον πίνακα δεν αποτελεί πρόβλημα για το πρόγραμμα. Εδώ, υποθέτουμε ότι

  • τα πλήκτρα είναι μικροί ακέραιοι
  • ο αριθμός των κλειδιών δεν είναι πολύ μεγάλος και
  • δεν έχουν δύο δεδομένα το ίδιο κλειδί

Λαμβάνεται μια ομάδα ακεραίων που ονομάζεται σύμπαν U = (0, 1,… ., n-1).
Κάθε υποδοχή πίνακα άμεσων διευθύνσεων T(0… n-1)περιέχει δείκτη στο στοιχείο που αντιστοιχεί στα δεδομένα.
Το ευρετήριο του πίνακα Tείναι το ίδιο το κλειδί και το περιεχόμενο Tείναι ένας δείκτης του συνόλου (key, element). Εάν δεν υπάρχει κανένα στοιχείο για ένα κλειδί τότε, παραμένει ως NULL.

Μερικές φορές, το ίδιο το κλειδί είναι τα δεδομένα.

Ψευδοκώδικας για λειτουργίες

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

Περιορισμοί ενός πίνακα άμεσων διευθύνσεων

  • Η τιμή του κλειδιού πρέπει να είναι μικρή.
  • Ο αριθμός των πλήκτρων πρέπει να είναι αρκετά μικρός, ώστε να μην υπερβαίνει το όριο μεγέθους ενός πίνακα.

2. Πίνακας Hash

Σε έναν πίνακα κατακερματισμού, τα κλειδιά επεξεργάζονται για να παράγουν ένα νέο ευρετήριο που αντιστοιχεί στο απαιτούμενο στοιχείο. Αυτή η διαδικασία ονομάζεται κατακερματισμός.

Ας h(x)είναι μια συνάρτηση κατακερματισμού και kγίνετε κλειδί.
h(k)υπολογίζεται και χρησιμοποιείται ως ευρετήριο για το στοιχείο.

Περιορισμοί ενός πίνακα Hash

  • Εάν το ίδιο ευρετήριο παράγεται από τη συνάρτηση κατακερματισμού για πολλαπλά πλήκτρα τότε, προκύπτει διένεξη. Αυτή η κατάσταση ονομάζεται σύγκρουση.
    Για να αποφευχθεί αυτό, επιλέγεται μια κατάλληλη λειτουργία κατακερματισμού. Όμως, είναι αδύνατο να παραχθούν όλα τα μοναδικά κλειδιά γιατί |U|>m. Έτσι, μια καλή λειτουργία κατακερματισμού μπορεί να μην εμποδίζει εντελώς τις συγκρούσεις, αλλά μπορεί να μειώσει τον αριθμό των συγκρούσεων.

Ωστόσο, έχουμε άλλες τεχνικές για την επίλυση της σύγκρουσης.

Πλεονεκτήματα του πίνακα κατακερματισμού έναντι του πίνακα άμεσων διευθύνσεων:

Τα κύρια προβλήματα με τον πίνακα διευθύνσεων είναι το μέγεθος του πίνακα και η πιθανώς μεγάλη τιμή ενός κλειδιού. Η συνάρτηση κατακερματισμού μειώνει το εύρος του ευρετηρίου και έτσι το μέγεθος του πίνακα μειώνεται επίσης.
Για παράδειγμα, Εάν k = 9845648451321, τότε h(k) = 11(χρησιμοποιώντας κάποια λειτουργία κατακερματισμού). Αυτό βοηθά στην εξοικονόμηση της σπατάλης μνήμης παρέχοντας παράλληλα το ευρετήριο του 9845648451321πίνακα

Ανάλυση σύγκρουσης με αλυσίδα

Σε αυτήν την τεχνική, εάν μια συνάρτηση κατακερματισμού παράγει τον ίδιο δείκτη για πολλά στοιχεία, αυτά τα στοιχεία αποθηκεύονται στον ίδιο ευρετήριο χρησιμοποιώντας μια λίστα διπλής σύνδεσης.

Εάν jείναι η υποδοχή για πολλά στοιχεία, περιέχει ένα δείκτη στην κεφαλή της λίστας στοιχείων. Εάν δεν υπάρχει στοιχείο, jπεριέχει NIL.

Ψευδοκώδικας για λειτουργίες

 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 και C ++

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

Good Hash Functions

A good hash function has the following characteristics.

  1. It should not generate keys that are too large and the bucket space is small. Space is wasted.
  2. The keys generated should be neither very close nor too far in range.
  3. The collision must be minimized as much as possible.

Some of the methods used for hashing are:

Division Method

If k is a key and m is the size of the hash table, the hash function h() is calculated as:

h(k) = k mod m

For example, If the size of a hash table is 10 and k = 112 then h(k) = 112 mod 10 = 2. The value of m must not be the powers of 2. This is because the powers of 2 in binary format are 10, 100, 1000,… . When we find k mod m, we will always get the lower order p-bits.

 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και είναι θετικές βοηθητικές σταθερές,c2
  • i = (0, 1,… .)

Διπλό κατακερματισμό

Εάν προκύψει σύγκρουση μετά την εφαρμογή συνάρτησης κατακερματισμού h(k), τότε υπολογίζεται μια άλλη συνάρτηση κατακερματισμού για την εύρεση της επόμενης υποδοχής.
h(k, i) = (h1(k) + ih2(k)) mod m

Εφαρμογές πίνακα Hash

Οι πίνακες Hash εφαρμόζονται όπου

  • απαιτείται συνεχής αναζήτηση και εισαγωγή
  • κρυπτογραφικές εφαρμογές
  • Απαιτούνται δεδομένα ευρετηρίου

ενδιαφέροντα άρθρα...