Α Για την Python. Να πάμε, ή σε JavaScript. Συνεργατικές σειρές σε PHP, σε C++. Οι χάρτες hash υλοποιούνται σχεδόν σε κάθε γλώσσα προγραμματισμού υψηλού επιπέδου. Και είναι καταπληκτικοί! Ποιος δεν θέλει να αποθηκεύσει και στη συνέχεια να έχει πρόσβαση στα δεδομένα σε συνεχή χρονική περίοδο; Είτε εργάζεστε με μεγάλα σύνολα δεδομένων είτε μασάζ προβλήματα Leetcode, πολύ συχνά αυτή η δομή δεδομένων έρχεται στη διάσωση. Αλλά τι ακριβώς είναι, και πώς λειτουργούν κάτω από το καπάκι; Σε αυτό το άρθρο, θα προσπαθήσουμε να απαντήσουμε σε αυτές τις ερωτήσεις. dict map Object Map Dictionary<TKey, TValue> Τι είναι ένας χάρτης hash; Σε υψηλό επίπεδο, ένας χάρτης hash ή πίνακας hash είναι μια δομή δεδομένων που εφαρμόζει έναν τύπο αφηρημένων δεδομένων συσχετιζόμενης σειράς, μια δομή που μπορεί να χαρτογραφήσει τα κλειδιά σε τιμές.Το κλειδί χρησιμοποιείται για να προσδιορίσει μοναδικά μια τιμή στο χάρτη και η τιμή είναι τα δεδομένα που αποθηκεύονται. Στην πραγματικότητα, η μέση χρονική πολυπλοκότητα αυτών των λειτουργιών είναι O(1), πράγμα που σημαίνει ότι μπορούν να εκτελεστούν σε σταθερό χρόνο!Αυτό το χαρακτηριστικό καθιστά τους χάρτες hash πιθανότατα την πιο χρησιμοποιούμενη δομή δεδομένων στον προγραμματισμό, ωστόσο, υπάρχουν κάποιες προειδοποιήσεις σε αυτό, όπως θα δούμε αργότερα. Η χειρότερη χρονική πολυπλοκότητα για αυτές τις λειτουργίες είναι O(n), η οποία μπορεί να συμβεί σε ορισμένα σενάρια, και όσο περισσότερο γνωρίζουμε για τα εσωτερικά, τόσο πιο πιθανό είναι να αποφύγουμε αυτά τα σενάρια. Σύμφωνα με την : Wikipedia άρθρο Ένας πίνακας hash είναι μια δομή δεδομένων που εφαρμόζει μια συσχετική σειρά, που ονομάζεται επίσης λεξικό ή απλά χάρτης. ένας συσχετικός πίνακας είναι ένας τύπος αφηρημένων δεδομένων που χαρτογραφεί τα κλειδιά σε τιμές. ένας πίνακας hash χρησιμοποιεί μια λειτουργία hash για να υπολογίσει έναν δείκτη, που ονομάζεται επίσης κωδικός hash, σε μια σειρά από δοχεία ή υποδοχές, από τις οποίες μπορεί να βρεθεί η επιθυμητή τιμή. Ένας πίνακας hash είναι μια δομή δεδομένων που εφαρμόζει μια συσχετική σειρά, που ονομάζεται επίσης λεξικό ή απλά χάρτης. ένας συσχετικός πίνακας είναι ένας τύπος αφηρημένων δεδομένων που χαρτογραφεί τα κλειδιά σε τιμές. ένας πίνακας hash χρησιμοποιεί μια λειτουργία hash για να υπολογίσει έναν δείκτη, που ονομάζεται επίσης κωδικός hash, σε μια σειρά από δοχεία ή υποδοχές, από τις οποίες μπορεί να βρεθεί η επιθυμητή τιμή. Ας κάνουμε λοιπόν ένα βήμα πίσω και ας δούμε τα συστατικά ενός χάρτη hash. Τι είναι μια λειτουργία hash; Μια συνάρτηση hash είναι μια συνάρτηση που παίρνει μια είσοδο (ή "κλειδί") και συνήθως επιστρέφει έναν ακέραιο αριθμό που χρησιμοποιείται για την ευρετηρίαση των δεδομένων στον χάρτη hash. Μια καλή λειτουργία hash έχει τις ακόλουθες ιδιότητες: Deterministic: Η ίδια είσοδος θα παράγει πάντα την ίδια έξοδο. Ενιαία κατανομή: Η συνάρτηση hash θα πρέπει να κατανέμει τα κλειδιά ομοιόμορφα σε όλο τον πίνακα hash για να ελαχιστοποιηθούν οι συγκρούσεις. Γρήγορος υπολογισμός: Η συνάρτηση hash θα πρέπει να είναι γρήγορη για υπολογισμό, ακόμη και για μεγάλες εισόδους. Ελαχιστοποίηση των συγκρούσεων: Ο χώρος των πιθανών κλειδιών είναι συνήθως πολύ μεγαλύτερος (συχνά άπειρος) από τον χώρο των κωδικών hash. Αυτό σημαίνει ότι διαφορετικά κλειδιά μπορούν να παράγουν τον ίδιο κωδικό hash. Ενώ αυτές οι συγκρούσεις είναι αναπόφευκτες, μια καλή λειτουργία hash ελαχιστοποιεί τις πιθανότητες δύο διαφορετικών κλειδιών να παράγουν τον ίδιο κωδικό hash. Ένα απλό παράδειγμα μιας συνάρτησης hash είναι η λειτουργία modulo, η οποία παίρνει ένα κλειδί και επιστρέφει το υπόλοιπο όταν διαιρείται από το μέγεθος του πίνακα hash. , που σημαίνει ότι η τιμή που σχετίζεται με το κλειδί 23 θα αποθηκευτεί στον δείκτη 3 στην υποκείμενη σειρά. και αν το κλειδί είναι 33, ο κωδικός hash θα Επίσης, αυτό σημαίνει ότι έχουμε μια σύγκρουση.Σε αυτή την περίπτωση, και τα δύο κλειδιά θα χαρτογραφούν τον ίδιο δείκτη στο φάσμα. 23 % 10 = 3 33 % 10 = 3 Τι είναι ένα bucket; Ένα bucket είναι μια υποδοχή στον πίνακα hash όπου αποθηκεύεται ένα ζεύγος τιμών-κλειδιών. Σε περίπτωση σύγκρουσης, όπου δύο διαφορετικά κλειδιά παράγουν τον ίδιο κωδικό hash, το bucket μπορεί να αποθηκεύσει πολλαπλά ζεύγη τιμών-κλειδιών. Αυτό γίνεται συχνά χρησιμοποιώντας μια συνδεδεμένη λίστα ή άλλη δομή δεδομένων για να χειριστεί τις συγκρούσεις. Αυτός ο πίνακας δείχνει πώς λειτουργεί όλο αυτό: Εδώ μπορούμε να δούμε πώς η λειτουργία hash χαρτογραφεί τα κλειδιά σε δείκτες στο υποκείμενο φάσμα. Τα κλειδιά 23 και 33 παράγουν και τα δύο τον ίδιο κωδικό hash του 3, πράγμα που σημαίνει ότι αποθηκεύονται στο ίδιο δοχείο. Το δοχείο μπορεί στη συνέχεια να αποθηκεύσει και τα δύο ζεύγη τιμών-κλειδιών, αλλά όταν ανακτούμε μια τιμή, πρέπει να ελέγξουμε τα κλειδιά στο δοχείο για να βρούμε το σωστό. Αυτό είναι όπου η πολυπλοκότητα του χρόνου μπορεί να αυξηθεί σε O(n) στην χειρότερη περίπτωση, αν πολλά (ή ακόμα και όλα) τα κλειδιά συγκρούονται και αποθηκεύονται στο ίδιο δοχείο. ΦΑΡΜΑΚΟΣ ΦΑΡΜΑΚΟΣ Ο συντελεστής φόρτωσης είναι ένα μέτρο του πόσο πλήρης είναι ο πίνακας hash. Υπολογίζεται ως ο αριθμός των στοιχείων στον πίνακα hash διαιρούμενος από τον αριθμό των δοκών (ή υποδοχών) στο υποκείμενο σύνολο. Ένας υψηλότερος συντελεστής φόρτωσης σημαίνει ότι υπάρχουν περισσότερα στοιχεία στον πίνακα hash σε σχέση με τον αριθμό των δοκών, γεγονός που μπορεί να οδηγήσει σε περισσότερες συγκρούσεις και βραδύτερη απόδοση. Ψήφισμα σύγκρουσης Όταν δύο κλειδιά παράγουν τον ίδιο κωδικό hash, έχουμε μια σύγκρουση. Υπάρχουν αρκετές στρατηγικές για τη διαχείριση των συγκρούσεων σε χάρτες hash: : In this method, each bucket contains a linked list (or another data structure) of all key-value pairs that hash to the same index. When a collision occurs, the new key-value pair is simply added to the list in the appropriate bucket. This is the most common method for handling collisions. Chaining : Average O(1) for all operations, worst-case O(n) if all keys hash to the same bucket Complexity : Simple to implement, handles high load factors well, deletion is straightforward Pros : Extra memory overhead for pointers, poor cache performance due to scattered memory access Cons Open Addressing: Σε αυτή τη μέθοδο, όταν συμβεί μια σύγκρουση, ο πίνακας hash αναζητά την επόμενη διαθέσιμη υποδοχή στο φάσμα για να αποθηκεύσει το νέο ζεύγος τιμών-κλειδιών. Εάν συμβεί σύγκρουση, ο αλγόριθμος ελέγχει την επόμενη υποδοχή στο φάσμα μέχρι να βρει μια κενή. Linear Probing Περίπλοκη κατάσταση: Μέσος όρος O(1), χειρότερη περίπτωση O(n) λόγω πρωτογενούς ομαδοποίησης Πλεονεκτήματα: Απλή εφαρμογή, καλή απόδοση cache για πρόσβαση σε κοντινή απόσταση Μειονεκτήματα: Πρωτογενής ομαδοποίηση (διαδοχικά καταλαμβανόμενα κουλοχέρηδες), υποβάθμιση της απόδοσης με ομαδοποίηση Αντί να ελέγχει την επόμενη υποδοχή, ελέγχει τις υποδοχές σε αυξανόμενες αποστάσεις (1, 4, 9, κ.λπ.) από τον αρχικό δείκτη. Quadratic Probing Πλήρης πολυπλοκότητα: Μέσος όρος O(1), καλύτερος από την γραμμική ανίχνευση λόγω της μειωμένης συσσώρευσης Πλεονεκτήματα: Μειώνει την πρωτογενή συσσωμάτωση σε σύγκριση με τη γραμμική ανίχνευση, εξακολουθεί να είναι φιλική προς την προσωρινή μνήμη Μειονεκτήματα: Δευτερογενής ομαδοποίηση (κλειδιά με το ίδιο hash ακολουθούν την ίδια ακολουθία δειγματοληψίας), μπορεί να μην επισκεφθείτε όλες τις υποδοχές Χρησιμοποιεί μια δεύτερη συνάρτηση hash για να καθορίσει το μέγεθος του βήματος για την ανίχνευση. Σε αντίθεση με τη γραμμική ανίχνευση που μετακινείται πάντα στην επόμενη υποδοχή, ή την τετραγωνική ανίχνευση που χρησιμοποιεί μια σταθερή ακολουθία, η διπλή ανίχνευση υπολογίζει ένα μοναδικό μέγεθος βήματος για κάθε κλειδί. Που Η δεύτερη συνάρτηση hash πρέπει να επιστρέψει μια τιμή που είναι σχετικά πρωτεύουσα για το μέγεθος του πίνακα για να εξασφαλιστεί ότι όλες οι υποδοχές μπορούν να επισκεφθούν. και , τότε θα ερευνήσουμε τους δείκτες 7, 10, 13, 16 κλπ. Double Hashing index = (hash1(key) + i * hash2(key)) % table_size i hash1(key) = 7 hash2(key) = 3 : Average O(1), best performance among open addressing methods Complexity : Minimizes clustering, uniform distribution of probe sequences, visits all slots when properly implemented Pros : More complex implementation, requires computing two hash functions, and slightly more overhead per operation Cons : If the load factor becomes too high, the hash table can be resized and all existing key-value pairs can be rehashed into the new table. This helps to maintain efficient performance as the number of elements grows. Rehashing : O(n) for the rehashing operation itself, but amortizes to O(1) per insertion over time Complexity : Maintains optimal performance by keeping the load factor low, prevents performance degradation Pros : Temporary performance spike during rehashing, requires additional memory during the resize operation Cons Κάθε μία από αυτές τις μεθόδους έχει το δικό της συμβιβασμό όσον αφορά την πολυπλοκότητα, την απόδοση και τη χρήση μνήμης.Η επιλογή της στρατηγικής επίλυσης σύγκρουσης μπορεί να έχει σημαντικό αντίκτυπο στη συνολική απόδοση του χάρτη hash. Εδώ είναι μια γρήγορη περίληψη των πλεονεκτημάτων και των μειονεκτημάτων κάθε μεθόδου επίλυσης σύγκρουσης: Feature Chaining Linear Probing Quadratic Probing Double Hashing Average Time Complexity O(1) O(1) O(1) O(1) Worst-case Time Complexity O(n) O(n) O(n) O(n) Memory Overhead High (pointers) Low Low Low Cache Performance Poor Good Good Moderate Implementation Complexity Simple Simple Moderate Complex Clustering Issues None Primary clustering Secondary clustering Minimal Load Factor Tolerance High (>1.0) Low (<0.7) Low-Medium (<0.7) Medium (<0.8) Deletion Complexity Simple Complex (tombstones) Complex (tombstones) Complex (tombstones) Space Efficiency Lower Higher Higher Higher Performance Degradation Gradual Rapid at high load Moderate at high load Slow at high load Hash Function Requirements One One One Two Best Use Cases Unknown load factors, frequent deletions Cache-friendly applications, low load Better than linear, moderate load High performance, predictable load Average Time Complexity Η(1) Η(1) Η(1) Η(1) Worst-case Time Complexity Ο (Ν) Ο (Ν) Ο (Ν) Ο (Ν) Memory Overhead Σημειώσεις (Σημειώσεις Σημειώσεις) Χαμηλή Χαμηλή Χαμηλή Cache Performance φτωχός Καλή Καλή μετριοπαθής Implementation Complexity Απλή Απλή μετριοπαθής Σύνθετα Clustering Issues Κανένα Πρωταρχικός Συγκεντρωτισμός δευτερογενής συσσώρευση Μίνιμουμ Load Factor Tolerance Μεγαλύτερη (>1.0) Μειωμένη (< 0,7 ) Χαμηλός μέσος όρος (<0.7) Μεσαίου μεγέθους (<0.8) Deletion Complexity Απλή Οι τάφοι (Tombstones) Οι τάφοι (Tombstones) Οι τάφοι (Tombstones) Space Efficiency Κάτω Υψηλότερη Υψηλότερη Υψηλότερη Performance Degradation βαθμιαία Γρήγορα σε υψηλό φορτίο Μετριοπαθής σε υψηλό φορτίο Αργή σε υψηλό φορτίο Hash Function Requirements Μια Μια Μια Δύο Best Use Cases Άγνωστοι παράγοντες φορτίου, συχνές διαγραφές Φιλικές εφαρμογές, χαμηλό φορτίο Καλύτερο από το γραμμικό, μέτριο φορτίο Υψηλή απόδοση, προβλέψιμο φορτίο Μερικά πραγματικά παραδείγματα Εφαρμογές Γλωσσών Προγραμματισμού Πολλές γλώσσες προγραμματισμού έχουν ενσωματωμένους χάρτες hash. Αυτές οι εφαρμογές συχνά χρησιμοποιούν έναν συνδυασμό των τεχνικών που περιγράφονται παραπάνω για να παρέχουν αποτελεσματική απόδοση και να χειρίζονται τις συγκρούσεις αποτελεσματικά. Το dict της Python χρησιμοποιεί ανοικτή διεύθυνση με τυχαιοποιημένη ανίχνευση, επανατοποθετώντας όταν ο συντελεστής φόρτωσης υπερβαίνει περίπου το 0,66. Το HashMap της Java χρησιμοποιεί την αλυσίδα με συνδεδεμένες λίστες (μετατροπή σε ισορροπημένα δέντρα για μεγάλα δοχεία στην Java 8+), επιταχύνεται με συντελεστή φόρτωσης 0,75. Το unordered_map του C++ χρησιμοποιεί συνήθως αλυσίδα, αλλά οι εφαρμογές μπορεί να διαφέρουν. Συστήματα βάσεων δεδομένων Οι χάρτες hash χρησιμοποιούνται επίσης ευρέως στην ευρετηρίαση βάσεων δεδομένων. Πολλά συστήματα βάσεων δεδομένων χρησιμοποιούν δείκτες hash για να επιταχύνουν την ανάκτηση δεδομένων. Αυτοί οι δείκτες επιτρέπουν γρήγορες αναζητήσεις με την ευρετηρίαση των ευρετηριωμένων στηλών και την αποθήκευση των προκύπτουσων ζευγαριών τιμών-κλειδιών σε έναν πίνακα hash. Όταν εκτελείται ένα ερώτημα, η βάση δεδομένων μπορεί να βρει γρήγορα τις σχετικές σειρές υπολογίζοντας το hash του κλειδιού ερωτήματος και αναζητώντας το στο δείκτη hash. Μερικά δημοφιλή συστήματα βάσεων δεδομένων που χρησιμοποιούν ευρετηρίαση hash περιλαμβάνουν: PostgreSQL: Υποστηρίζει δείκτες hash, αλλά δεν χρησιμοποιούνται τόσο συχνά όσο οι δείκτες B-tree. MongoDB: Χρησιμοποιεί δείκτες hash για sharding και για την υποστήριξη ερωτημάτων ισότητας σε πεδία hash. Redis: Εφαρμόζει χάρτες hash ως δομή βασικών δεδομένων, επιτρέποντας την αποτελεσματική αποθήκευση και ανάκτηση ζευγαριών βασικών τιμών. Αυτές οι εφαρμογές συχνά αξιοποιούν τις ίδιες βασικές αρχές hashing και επίλυσης συγκρούσεων που συζητήθηκαν προηγουμένως, αλλά ενδέχεται επίσης να ενσωματώσουν πρόσθετες βελτιστοποιήσεις ειδικά για το πλαίσιο της βάσης δεδομένων. Έλεγχος εκδόσεων Συστήματα ελέγχου εκδόσεων όπως το Git χρησιμοποιούν χάρτες hash για να διαχειρίζονται αποτελεσματικά τις αλλαγές αρχείων και να παρακολουθούν τις εκδόσεις. Κάθε δέσμευση στο Git προσδιορίζεται από ένα hash SHA-1 του περιεχομένου του, το οποίο χρησιμεύει ως μοναδικό κλειδί για το αντικείμενο δέσμευσης. Αυτό επιτρέπει στο Git να αναζητά γρήγορα δεσμεύσεις, κλάδους και άλλα αντικείμενα στο αποθετήριο. Βάζοντας όλα μαζί: Πώς η εφαρμογή της γνώσης έχει σημασία Η κατανόηση του πώς εφαρμόζονται οι χάρτες hash στη γλώσσα προγραμματισμού της επιλογής σας μπορεί να οδηγήσει σε σημαντικές βελτιώσεις στην απόδοση του κώδικα σας. Για παράδειγμα, από την εποχή του Python Χρησιμοποιεί ανοικτή διεύθυνση με βελτιστοποιημένη επεξεργασία γραμμών, η κατανόηση αυτού μπορεί να οδηγήσει σε πολύ καλύτερη απόδοση. dict Bad Implementation (Αντιμετωπίζει το Dict του Python) def count_words_bad(text): word_counts = {} words = text.split() for word in words: # This is inefficient with open addressing! if word in word_counts: # First lookup word_counts[word] += 1 # Second lookup + assignment else: word_counts[word] = 1 # Third lookup + assignment return word_counts Εισαγωγή πλήρους οθόνης Εισαγωγή πλήρους οθόνης Problems: Πολλαπλές αναζητήσεις hash ανά λέξη (έως 3!) Η ανοικτή διεύθυνση κάνει τους ελέγχους που λείπουν από κλειδιά δαπανηρούς Δεν αξιοποιεί τις βελτιστοποιήσεις dict της Python Καλή εφαρμογή (εργάζεται με το Python Dict) from collections import defaultdict, Counter def count_words_good_v1(text): # defaultdict eliminates key existence checks word_counts = defaultdict(int) words = text.split() for word in words: word_counts[word] += 1 # Single operation! return dict(word_counts) def count_words_good_v2(text): # Counter is optimized specifically for Python's dict implementation words = text.split() return Counter(words) def count_words_good_v3(text): # dict.get() with default avoids the membership test word_counts = {} words = text.split() for word in words: word_counts[word] = word_counts.get(word, 0) + 1 # Single lookup return word_counts Εισαγωγή πλήρους οθόνης Εισαγωγή πλήρους οθόνης Why These Are Better: Μία λειτουργία hash ανά λέξη αντί για πολλαπλές Εκμεταλλεύεται τη βελτιστοποίηση σειρών της Python - τα πλήκτρα σειράς χειρίζονται πολύ αποτελεσματικά Λειτουργεί με ανοικτές διευθύνσεις - απαιτούνται λιγότερες επιχειρήσεις ανίχνευσης Χρησιμοποιεί ενσωματωμένες βελτιστοποιήσεις όπως το Counter που είναι προσαρμοσμένο για την εφαρμογή του Python Διαφορά απόδοσης Η καλή εφαρμογή είναι συχνά 2-3 φορές ταχύτερη, απλά με την κατανόηση και την εργασία με την εφαρμογή dict της Python και όχι εναντίον της! Typical Results: Συμπέρασμα Οι χάρτες hash είναι από τις πιο θεμελιώδεις και ισχυρές δομές δεδομένων στην επιστήμη των υπολογιστών, παρέχοντας σχεδόν σταθερή χρονική πρόσβαση στα δεδομένα που τα καθιστά απαραίτητα στον σύγχρονο προγραμματισμό.Κατά τη διάρκεια αυτής της βαθιάς κατάδυσης, έχουμε διερευνήσει πώς επιτυγχάνουν την αξιοσημείωτη μέση απόδοση O(1) μέσω της έξυπνης χρήσης των λειτουργιών hash, της στρατηγικής επίλυσης συγκρούσεων και της προσεκτικής διαχείρισης του συντελεστή φορτίου. Η βασική γνώση είναι ότι η "μαγεία" των χαρτών hash δεν είναι πραγματικά μαγεία καθόλου - είναι το αποτέλεσμα καλά σχεδιασμένων αλγορίθμων και δομών δεδομένων που συνεργάζονται. Key Takeaways: Οι λειτουργίες hash αποτελούν τη βάση – καθορίζουν πώς τα δεδομένα κατανέμονται ομοιόμορφα και επηρεάζουν άμεσα τα ποσοστά σύγκρουσης Κάθε μια από τις στρατηγικές επίλυσης συγκρούσεων έχει ξεχωριστούς συμβιβασμούς: αλυσίδα για απλότητα και ανθεκτικότητα, ανοικτή αντιμετώπιση για αποδοτικότητα μνήμης και απόδοση cache. Η διαχείριση του συντελεστή φόρτωσης μέσω της επανατοποθέτησης αποτρέπει την υποβάθμιση της απόδοσης καθώς οι χάρτες hash αυξάνονται Η γνώση της εφαρμογής μεταφράζεται σε πραγματικά κέρδη απόδοσης - η κατανόηση του εάν η γλώσσα σας χρησιμοποιεί αλυσίδα ή ανοικτή διευθύνσεις μπορεί να κάνει τον κώδικα σας 2-3 φορές ταχύτερο Είτε βελτιστοποιείτε ένα σενάριο Python, ανακατεύετε προβλήματα απόδοσης στην Java ή λαμβάνετε αρχιτεκτονικές αποφάσεις για ένα σύστημα βάσεων δεδομένων, αυτή η κατανόηση των εσωτερικών του HashMap σας δίνει τα εργαλεία για να κάνετε τεκμηριωμένες επιλογές. , Ή Θα ξέρετε ακριβώς τι συμβαίνει κάτω από το καπάκι και πώς να αξιοποιήσετε στο έπακρο αυτές τις απίστευτες δομές δεδομένων. dict HashMap unordered_map Οι χάρτες hash είναι πραγματικά καταπληκτικοί – και τώρα ξέρετε γιατί!
