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

Τι είναι το Hashing;

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

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

Τι είναι ένας πίνακας κατακερματισμού;

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

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

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

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

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

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

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

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

h(k) = k1 % m

ΕΔΩ,

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

Παράδειγμα

Ας υποθέσουμε ότι έχουμε μια λίστα με σταθερό μέγεθος 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 είναι το μέγεθος του πίνακα κατακερματισμού.

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

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

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

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

Αλυσίδα

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

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

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

Οφέλη από αλυσοδεμένες λίστες

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

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

Διερεύνηση

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

Ακολουθούν οι μέθοδοι ανίχνευσης:

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

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

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

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

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

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

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

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

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

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

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

Υλοποίηση πίνακα κατακερματισμού με Python Παράδειγμα

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

def hash_key( key, m):
    return key % m


m = 7

print(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 3
The hash value for 2 is 2
The hash value for 9 is 2
The hash value for 11 is 4
The 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). Το χειρότερο σενάριο συμβαίνει όταν πολλές τιμές δημιουργούν το ίδιο κλειδί κατακερματισμού και πρέπει να επιλύσουμε τη σύγκρουση με ανίχνευση.

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

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

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

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

Ακολουθούν τα πλεονεκτήματα/πλεονεκτήματα της χρήσης πινάκων κατακερματισμού:

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

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

Ακολουθούν τα μειονεκτήματα της χρήσης πινάκων κατακερματισμού:

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

Περίληψη

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