Σε αυτό το σεμινάριο, θα μάθετε τι είναι το Hashing.
Το κατακερματισμό είναι μια τεχνική χαρτογράφησης ενός μεγάλου συνόλου αυθαίρετων δεδομένων σε πίνακες ευρετηρίου χρησιμοποιώντας μια συνάρτηση κατακερματισμού. Είναι μια μέθοδος για την αναπαράσταση λεξικών για μεγάλα σύνολα δεδομένων.
Επιτρέπει την αναζήτηση, την ενημέρωση και τη λειτουργία ανάκτησης να συμβαίνει σε σταθερό χρόνο, δηλαδή O(1).
Γιατί απαιτείται κατακερματισμός;
Μετά την αποθήκευση μεγάλου όγκου δεδομένων, πρέπει να εκτελέσουμε διάφορες λειτουργίες σε αυτά τα δεδομένα. Οι αναζητήσεις είναι αναπόφευκτες για τα σύνολα δεδομένων. Η γραμμική αναζήτηση και η δυαδική αναζήτηση πραγματοποιούν αναζητήσεις / αναζήτηση με χρονική πολυπλοκότητα O(n)και O(log n)αντίστοιχα. Καθώς το μέγεθος του συνόλου δεδομένων αυξάνεται, αυτές οι πολυπλοκότητες γίνονται επίσης σημαντικά υψηλές που δεν είναι αποδεκτές.
Χρειαζόμαστε μια τεχνική που δεν εξαρτάται από το μέγεθος των δεδομένων. Το κατακερματισμό επιτρέπει την εμφάνιση αναζητήσεων σε σταθερό χρόνο, δηλαδή O(1).
Λειτουργία κατακερματισμού
Μια συνάρτηση κατακερματισμού χρησιμοποιείται για τη χαρτογράφηση κάθε στοιχείου ενός συνόλου δεδομένων σε ευρετήρια στον πίνακα.
Για περισσότερες πληροφορίες σχετικά με τον πίνακα κατακερματισμού, τις τεχνικές επίλυσης σύγκρουσης και τις λειτουργίες κατακερματισμού, επισκεφθείτε τον Πίνακα κατακερματισμού.
