Πίνακας Hash εξήγησε: Τι είναι και πώς να το εφαρμόσετε

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

Μερικές σημαντικές σημειώσεις για πίνακες κατακερματισμού:

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

Υλοποίηση πίνακα κατακερματισμού

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

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

index = f(key, array_size)

Αυτό γίνεται συχνά σε δύο βήματα:

hash = hashfunc(key) index = hash % array_size

Η χρήση αυτής της μεθόδου, hashείναι ανεξάρτητη από το μέγεθος του πίνακα κατακερματισμού. hashμειώνεται σε ευρετήριο - ένας αριθμός μεταξύ 0, η αρχή του πίνακα και array_size - 1, το τέλος του πίνακα - χρησιμοποιώντας τον τελεστή modulo (%).

Εξετάστε την ακόλουθη συμβολοσειρά S:

string S = “ababcd”

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

Αυτό λειτουργεί, αλλά είναι αργό - η χρονική πολυπλοκότητα μιας τέτοιας προσέγγισης είναι O (26 * N), με Nτο μέγεθος της συμβολοσειράς Sπολλαπλασιασμένη επί 26 πιθανούς χαρακτήρες από το AZ.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Παραγωγή:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Ας ρίξουμε μια ματιά σε μια λύση που χρησιμοποιεί κατακερματισμό.

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

Η πολυπλοκότητα αυτής της προσέγγισης κατακερματισμού είναι O (N), όπου N είναι το μέγεθος της συμβολοσειράς.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Παραγωγή

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Hash συγκρούσεις

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

Αλυσίδα

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

Για παράδειγμα, φανταστείτε ότι το κλειδί 152 κρατά την τιμή "John Smith". Εάν η τιμή "Sandra Dee" προστίθεται στο ίδιο κλειδί, το "Sandra Dee" προστίθεται ως άλλο στοιχείο στο κλειδί 152, αμέσως μετά το "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

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

Ανοιχτή διεύθυνση

Η ανοιχτή διεύθυνση σημαίνει ότι, μόλις αντιστοιχιστεί μια τιμή σε ένα κλειδί που έχει ήδη καταληφθεί, μετακινείτε τα πλήκτρα του πίνακα κατακερματισμού μέχρι να βρείτε ένα κενό. Για παράδειγμα, εάν το "John Smith" αντιστοιχίστηκε στο 152, το "Sandra Dee" θα αντιστοιχιστεί στον επόμενο ανοιχτό δείκτη:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Το βασικό μειονέκτημα της ανοιχτής διεύθυνσης είναι ότι, όταν αναζητάτε τιμές, ενδέχεται να μην βρίσκονται στον βασικό χάρτη που περιμένετε. Αντ 'αυτού, πρέπει να διασχίσετε διαφορετικά μέρη του πίνακα κατακερματισμού για να βρείτε την τιμή που ψάχνετε.