Ο οδηγός χωρίς κωδικούς για πίνακες κατακερματισμού και κατακερματισμού

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

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

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

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

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

Λοιπόν, τι είναι μια λειτουργία Hash ούτως ή άλλως;

Πριν μπείτε σε όλα τα φανταχτερά πράγματα, επιτρέψτε μου να σας πω τι είναι ο κατακερματισμός. Για να το καταστήσουμε εύκολο ας φανταστούμε ότι έχουμε ένα μαύρο κουτί:

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

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

Το κουτί λειτουργίας μας θα λάβει ένα γράμμα από το AJ στην είσοδο και θα εξάγει έναν αντίστοιχο αριθμό από 0 έως 9 στην έξοδο. Έτσι, εάν εισάγουμε C, θα πάρουμε 2 στην έξοδο.

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

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

Τι γίνεται με τα Hash Tables;

Έτσι σε αυτό το σημείο μπορεί να αναρωτιέστε τι είναι ένας πίνακας κατακερματισμού. Οι πίνακες Hash χρησιμοποιούν κατακερματισμό για να σχηματίσουν μια δομή δεδομένων.

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

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

Οι πίνακες κατακερματισμού είναι εξαιρετικά γρήγοροι, έχοντας μια πολυπλοκότητα χρόνου που είναι της τάξης του O (1).

Ταραγμένος? Ρίξτε μια ματιά σε αυτό το διάγραμμα, όπου έχουμε πολλά πλαίσια λειτουργιών που δημιουργούν τιμές κατακερματισμού.

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

Η προκύπτουσα δομή θα μοιάζει με αυτήν:

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

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

Μια συνάρτηση στα μαθηματικά είναι ιδανική στο ότι ένα στοιχείο στην είσοδο χαρτογραφείται σε ακριβώς ένα στοιχείο στην έξοδο.

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

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

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

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

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

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

Είναι το Hashing το ίδιο με την κρυπτογράφηση ή την κωδικοποίηση;

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

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

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

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

Τι μπορώ να κάνω με το Hashing;

Οι πίνακες κατακερματισμού και κατακερματισμού έχουν πολλές χρήσεις! Αυτά περιλαμβάνουν:

  1. Κρυπτοσυστήματα
  2. Κυκλικοί έλεγχοι πλεονασμού
  3. Μηχανές αναζήτησης
  4. Βάσεις δεδομένων
  5. Μεταγλωττιστές

Ή οποιοδήποτε σύστημα έχει μια περίπλοκη διαδικασία αναζήτησης.

Τυλίγοντας

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

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

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

Σας άρεσε η προσέγγιση χωρίς κωδικοποίηση; Θέλετε να προχωρήσετε περισσότερο;

Μάθετε για κατακερματισμούς και άλλες δομές δεδομένων και αλγόριθμους στο βιβλίο "Codeless Data Structures and Algorithms". Θα λάβετε μια επέκταση αυτού που καλύπτεται σε αυτήν την ανάρτηση και θα μάθετε για πολλά περισσότερα θέματα, όλα χωρίς να γράψετε ούτε μια γραμμή κώδικα!

Δομές και αλγόριθμοι δεδομένων χωρίς κωδικούς - Μάθετε το DSA χωρίς να γράψετε μία γραμμή κώδικα | Άρμστρονγκ Σουμπέρο | Apress Αυτό το βιβλίο σας προσφέρει μια νέα προοπτική για αλγόριθμους και δομές δεδομένων, εντελώς δωρεάν. Μάθετε σχετικά με τους αλγόριθμους δομής δεδομένων (DSA) χωρίς να χρειάζεται να ανοίξετε ποτέ τον επεξεργαστή κώδικα, να χρησιμοποιήσετε έναν μεταγλωττιστή ή να δείτε ένα ενσωματωμένο περιβάλλον ανάπτυξης (IDE) .... Armstrong Subero Search Menu Καλάθι V Το καλάθι σας είναι προς το παρόν κενό. Είσοδος Λογαριασμός Ράφι Είσοδος Apress Access