Πίνακας κατακερματισμού στη δομή δεδομένων: Παράδειγμα Python

Τι είναι το Hashing;

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

Η συνάρτηση κατακερματισμού χρησιμοποιεί έναν μαθηματικό αλγόριθμο για τη μετατροπή του κλειδιού σε κατακερματισμό. Μια σύγκρουση συμβαίνει όταν μια συνάρτηση κατακερματισμού παράγει την ίδια τιμή κατακερματισμού για περισσότερα από ένα κλειδιά.

Σε αυτό το σεμινάριο Αλγόριθμου, θα μάθετε:

• Τι είναι το Hashing;
• Τι είναι ένας πίνακας Hash;
• Λειτουργίες κατακερματισμού
• Ποιότητες μιας καλής λειτουργίας κατακερματισμού
• Σύγκρουση
• Λειτουργίες κατακερματισμού πίνακα
• Παράδειγμα Hash Table Python
• Επεξήγηση κωδικού πίνακα
• Παράδειγμα λεξικού Python
• Ανάλυση πολυπλοκότητας
• Εφαρμογές πραγματικού κόσμου
• Πλεονεκτήματα κατακερματισμού
• Μειονεκτήματα κατακερματισμού πινάκων

Τι είναι ένας πίνακας Hash;

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

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

Λειτουργίες κατακερματισμού

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

Μπορούμε να χρησιμοποιήσουμε τον αριθμό υπαλλήλου ως κλειδί και να αντιστοιχίσουμε τα δεδομένα των υπαλλήλων ως αξία.

Η παραπάνω προσέγγιση απαιτεί επιπλέον ελεύθερο χώρο της τάξης του (m * n ² ) όπου η μεταβλητή m είναι το μέγεθος του πίνακα και η μεταβλητή n είναι ο αριθμός των ψηφίων για τον αριθμό υπαλλήλου. Αυτή η προσέγγιση εισάγει πρόβλημα χώρου αποθήκευσης

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

Το παρακάτω είναι ένα παράδειγμα μιας απλής συνάρτησης κατακερματισμού

h(k) = k1 % m

ΕΔΩ,

• h (k) είναι η συνάρτηση κατακερματισμού που δέχεται μια παράμετρο k. Η παράμετρος k είναι η τιμή για την οποία θέλουμε να υπολογίσουμε το κλειδί.
• Το k ₁ % m είναι ο αλγόριθμος για τη συνάρτηση κατακερματισμού όπου k1 είναι η τιμή που θέλουμε να αποθηκεύσουμε και το m είναι το μέγεθος της λίστας. Χρησιμοποιούμε τον τελεστή modulus για τον υπολογισμό του κλειδιού.

Παράδειγμα

Ας υποθέσουμε ότι έχουμε μια λίστα με σταθερό μέγεθος 3 και τις ακόλουθες τιμές

[1,2,3]

Μπορούμε να χρησιμοποιήσουμε τον παραπάνω τύπο για να υπολογίσουμε τις θέσεις που πρέπει να καταλαμβάνει κάθε τιμή.

Η παρακάτω εικόνα δείχνει τα διαθέσιμα ευρετήρια στον πίνακα κατακερματισμού μας.

Βήμα 1)

Υπολογίστε τη θέση που θα καταληφθεί από την πρώτη τιμή όπως έτσι

h (1) = 1% 3

= 1

Η τιμή 1 θα καταλάβει το διάστημα στο ευρετήριο 1

Βήμα 2)

Υπολογίστε τη θέση που θα καταληφθεί από τη δεύτερη τιμή

h (2) = 2% 3

= 2

Η τιμή 2 θα καταλάβει το διάστημα στο ευρετήριο 2

Βήμα 3)

Υπολογίστε τη θέση που θα καταληφθεί από την τρίτη τιμή.

h (3) = 3% 3

= 0

Η τιμή 3 θα καταλάβει το διάστημα στο ευρετήριο 0

Τελικό αποτέλεσμα

Ο γεμισμένος πίνακας κατακερματισμού θα είναι τώρα ο εξής

Ποιότητες μιας καλής λειτουργίας κατακερματισμού

Μια καλή λειτουργία κατακερματισμού πρέπει να έχει τις ακόλουθες ιδιότητες.

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

Σύγκρουση

Μια σύγκρουση συμβαίνει όταν ο αλγόριθμος δημιουργεί τον ίδιο κατακερματισμό για περισσότερες από μία τιμές.

Ας δούμε ένα παράδειγμα.

Ας υποθέσουμε ότι έχουμε την ακόλουθη λίστα τιμών

[3,2,9,11,7]

Ας υποθέσουμε ότι το μέγεθος του πίνακα κατακερματισμού είναι 7 και θα χρησιμοποιήσουμε τον τύπο (k ₁ % m) όπου m είναι το μέγεθος του πίνακα κατακερματισμού.

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

Κλειδί	Αλγόριθμος κατακερματισμού (k 1 % m)	Τιμή κατακερματισμού
3	3% 7	3
2	3% 7	2
9	3% 7	2
11	3% 7	4
7	3% 7	0

Όπως μπορούμε να δούμε από τα παραπάνω αποτελέσματα, οι τιμές 2 και 9 έχουν την ίδια τιμή κατακερματισμού και δεν μπορούμε να αποθηκεύσουμε περισσότερες από μία τιμές σε κάθε θέση.

Το δεδομένο πρόβλημα μπορεί να λυθεί είτε χρησιμοποιώντας αλυσίδα είτε με διερεύνηση. Οι ακόλουθες ενότητες συζητούν λεπτομερώς την αλυσίδα και την έρευνα.

Αλυσίδα

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

Η παρακάτω εικόνα απεικονίζει πώς φαίνεται μια αλυσοδεμένη λίστα

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

Οφέλη των αλυσοδεμένων λιστών

Τα ακόλουθα είναι τα οφέλη των αλυσοδεμένων λιστών:

• Οι αλυσοδεμένες λίστες έχουν καλύτερη απόδοση κατά την εισαγωγή δεδομένων επειδή η σειρά εισαγωγής είναι O (1).
• Δεν είναι απαραίτητο να αλλάξετε το μέγεθος ενός πίνακα κατακερματισμού που χρησιμοποιεί μια αλυσοδεμένη λίστα.
• Μπορεί εύκολα να φιλοξενήσει μεγάλο αριθμό τιμών εφόσον υπάρχει ελεύθερος χώρος.

Έρευνα

Η άλλη τεχνική που χρησιμοποιείται για την επίλυση της σύγκρουσης είναι η ανίχνευση. Όταν χρησιμοποιείτε τη μέθοδο ανίχνευσης, εάν προκύψει σύγκρουση, μπορούμε απλά να προχωρήσουμε και να βρούμε μια κενή υποδοχή για να αποθηκεύσουμε την αξία μας.

Οι ακόλουθες είναι οι μέθοδοι διερεύνησης:

Μέθοδος	Περιγραφή
Γραμμική διερεύνηση	Ακριβώς όπως υποδηλώνει το όνομα, αυτή η μέθοδος αναζητά γραμμικά κενά slots ξεκινώντας από τη θέση όπου συνέβη η σύγκρουση και προχωρούσε προς τα εμπρός. Εάν φτάσει το τέλος της λίστας και δεν υπάρχει κενή υποδοχή. Η διερεύνηση ξεκινά στην αρχή της λίστας.
Τετραγωνική ανίχνευση	Αυτή η μέθοδος χρησιμοποιεί τετραγωνικές πολυωνυμικές εκφράσεις για να βρει την επόμενη διαθέσιμη δωρεάν υποδοχή.
Διπλό κατακερματισμό	Αυτή η τεχνική χρησιμοποιεί έναν δευτερεύοντα αλγόριθμο λειτουργίας κατακερματισμού για να βρει την επόμενη δωρεάν διαθέσιμη υποδοχή.

Χρησιμοποιώντας το παραπάνω παράδειγμα, ο πίνακας κατακερματισμού μετά τη χρήση της ανίχνευσης θα εμφανιστεί ως εξής:

Λειτουργίες κατακερματισμού πίνακα

Εδώ είναι οι λειτουργίες που υποστηρίζονται από πίνακες Hash:

• Εισαγωγή - αυτή η λειτουργία χρησιμοποιείται για την προσθήκη ενός στοιχείου στον πίνακα κατακερματισμού
• Αναζήτηση - αυτή η λειτουργία χρησιμοποιείται για την αναζήτηση στοιχείων στον πίνακα κατακερματισμού χρησιμοποιώντας το κλειδί
• Διαγραφή - αυτή η λειτουργία χρησιμοποιείται για τη διαγραφή στοιχείων από τον πίνακα κατακερματισμού

Εισαγωγή λειτουργίας δεδομένων

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

Αναζήτηση για λειτουργία δεδομένων

Η λειτουργία αναζήτησης χρησιμοποιείται για την αναζήτηση τιμών στον πίνακα κατακερματισμού χρησιμοποιώντας τον αριθμό ευρετηρίου. Η λειτουργία αναζήτησης επιστρέφει την τιμή που συνδέεται με τον αριθμό ευρετηρίου αναζήτησης. Για παράδειγμα, εάν αποθηκεύσουμε την τιμή 6 στο ευρετήριο 2, η λειτουργία αναζήτησης με τον αριθμό ευρετηρίου 2 θα επιστρέψει την τιμή 6.

Διαγραφή λειτουργίας δεδομένων

Η λειτουργία διαγραφής χρησιμοποιείται για την κατάργηση μιας τιμής από έναν πίνακα κατακερματισμού. Για να διαγράψετε τη λειτουργία γίνεται χρησιμοποιώντας τον αριθμό ευρετηρίου. Μόλις διαγραφεί μια τιμή, ο αριθμός ευρετηρίου γίνεται δωρεάν. Μπορεί να χρησιμοποιηθεί για την αποθήκευση άλλων τιμών χρησιμοποιώντας τη λειτουργία εισαγωγής.

Εφαρμογή Hash πίνακα με παράδειγμα Python

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

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Επεξήγηση κωδικού πίνακα

ΕΔΩ,

1. Ορίζει μια συνάρτηση hash_key που δέχεται το πλήκτρο παραμέτρων και m.
2. Χρησιμοποιεί μια απλή λειτουργία συντελεστή για τον προσδιορισμό της τιμής κατακερματισμού
3. Ορίζει μια μεταβλητή m που έχει αρχικοποιηθεί στην τιμή 7. Αυτό είναι το μέγεθος του πίνακα κατακερματισμού μας
4. Υπολογίζει και εκτυπώνει την τιμή κατακερματισμού 3
5. Υπολογίζει και εκτυπώνει την τιμή κατακερματισμού 2
6. Υπολογίζει και εκτυπώνει την τιμή κατακερματισμού 9
7. Υπολογίζει και εκτυπώνει την τιμή κατακερματισμού 11
8. Υπολογίζει και εκτυπώνει την τιμή κατακερματισμού 7

Η εκτέλεση του παραπάνω κώδικα παράγει τα ακόλουθα αποτελέσματα.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Παράδειγμα λεξικού Python

Το Python διαθέτει έναν ενσωματωμένο τύπο δεδομένων που ονομάζεται Λεξικό. Το λεξικό είναι ένα παράδειγμα πίνακα κατακερματισμού. Αποθηκεύει τιμές χρησιμοποιώντας ένα ζευγάρι κλειδιών και τιμών. Οι τιμές κατακερματισμού δημιουργούνται αυτόματα για εμάς και τυχόν συγκρούσεις επιλύονται για εμάς στο παρασκήνιο.

Το παρακάτω παράδειγμα δείχνει πώς μπορείτε να χρησιμοποιήσετε έναν τύπο δεδομένων λεξικού στο python 3

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

ΕΔΩ,

1. Ορίζει έναν μεταβλητό υπάλληλο λεξικού. Το όνομα κλειδιού χρησιμοποιείται για την αποθήκευση της τιμής John Doe, τα καταστήματα ηλικίας 36 και η θέση αποθηκεύει την τιμή Business Manager.
2. Ανακτά την τιμή του ονόματος κλειδιού και την εκτυπώνει στο τερματικό
3. Ενημερώνει την τιμή της θέσης κλειδιού στην τιμή Software Engineer
4. Εκτυπώνει τις τιμές του ονόματος και της θέσης των κλειδιών
5. Διαγράφει όλες τις τιμές που είναι αποθηκευμένες στο λεξικό μας μεταβλητή υπάλληλος
6. Εκτυπώνει την αξία του υπαλλήλου

Η εκτέλεση του παραπάνω κώδικα παράγει τα ακόλουθα αποτελέσματα.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Ανάλυση πολυπλοκότητας

Οι πίνακες κατακερματισμού έχουν μέση χρονική πολυπλοκότητα O (1) στο σενάριο με τις καλύτερες περιπτώσεις. Η χειρότερη περίπτωση πολυπλοκότητας είναι O (n). Το χειρότερο σενάριο συμβαίνει όταν πολλές τιμές δημιουργούν το ίδιο κλειδί κατακερματισμού και πρέπει να επιλύσουμε τη σύγκρουση με διερεύνηση.

Εφαρμογές πραγματικού κόσμου

Στον πραγματικό κόσμο, οι πίνακες κατακερματισμού χρησιμοποιούνται για την αποθήκευση δεδομένων

• Βάσεις δεδομένων
• Συσχετιστικοί πίνακες
• Σκηνικά
• Προσωρινή μνήμη

Πλεονεκτήματα κατακερματισμού

Εδώ, είναι τα πλεονεκτήματα / οφέλη από τη χρήση πινάκων κατακερματισμού:

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

Μειονεκτήματα κατακερματισμού πινάκων

Εδώ είναι τα μειονεκτήματα της χρήσης πινάκων κατακερματισμού:

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

Περίληψη:

• Οι πίνακες κατακερματισμού χρησιμοποιούνται για την αποθήκευση δεδομένων χρησιμοποιώντας ένα ζευγάρι κλειδιών και τιμών.
• Μια συνάρτηση κατακερματισμού χρησιμοποιεί έναν μαθηματικό αλγόριθμο για τον υπολογισμό της τιμής κατακερματισμού.
• Μια σύγκρουση συμβαίνει όταν δημιουργείται η ίδια τιμή κατακερματισμού για περισσότερες από μία τιμές.
• Η αλυσίδα επιλύει τη σύγκρουση δημιουργώντας συνδεδεμένες λίστες.
• Η ανίχνευση επιλύει τη σύγκρουση βρίσκοντας κενές θέσεις στον πίνακα κατακερματισμού.
• Η γραμμική διερεύνηση αναζητά την επόμενη δωρεάν υποδοχή για να αποθηκεύσει την τιμή ξεκινώντας από την υποδοχή όπου συνέβη η σύγκρουση.
• Το Quadratic probing χρησιμοποιεί πολυωνυμικές εκφράσεις για να βρει την επόμενη ελεύθερη υποδοχή όταν συμβαίνει σύγκρουση
• Το διπλό κατακερματισμό χρησιμοποιεί έναν δευτερεύοντα αλγόριθμο λειτουργίας κατακερματισμού για να βρει την επόμενη δωρεάν υποδοχή όταν συμβαίνει σύγκρουση.
• Οι πίνακες κατακερματισμού έχουν καλύτερη απόδοση σε σύγκριση με άλλες δομές δεδομένων.
• Ο μέσος χρόνος πολυπλοκότητας των πινάκων κατακερματισμού είναι Ο
• Ένας τύπος δεδομένων λεξικού στο python είναι ένα παράδειγμα πίνακα κατακερματισμού.
• Οι πίνακες Hash υποστηρίζουν τις ενέργειες εισαγωγής, αναζήτησης και διαγραφής.
• Μια τιμή null δεν μπορεί να χρησιμοποιηθεί ως τιμή ευρετηρίου.
• Οι συγκρούσεις δεν μπορούν να αποφευχθούν στις λειτουργίες κατακερματισμού. Μια καλή συνάρτηση κατακερματισμού ελαχιστοποιεί τον αριθμό των συγκρούσεων που συμβαίνουν για τη βελτίωση της απόδοσης.