Ποια είναι η διαφορά μεταξύ ενός πίνακα και ενός πίνακα κατακερματισμού σε μια γλώσσα προγραμματισμού;


Απάντηση 1:

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

Μπορείτε να χρησιμοποιήσετε συστοιχίες για κουβάδες. Ας υποθέσουμε ότι ήθελε να υπολογίζετε πόσες από κάθε γράμμα σε ένα κείμενο, για παράδειγμα, για το σχεδιασμό κάτι σαν τον κώδικα Morse. Κάνετε μια σειρά με 26 καταχωρήσεις (για το απλό μη αφοσιωμένο ρωμαϊκό αλφάβητο). Κάθε φορά που βλέπετε ένα γράμμα, υπολογίζετε τον δείκτη και πηγαίνετε στην εν λόγω καταχώρηση στον πίνακα.

Οι πίνακες Hash επεκτείνουν αυτό για αυθαίρετα μεγάλα πλήκτρα. Υπολογίζετε ένα hash του κλειδιού και πηγαίνετε στο δείκτη. Το πρόβλημα είναι όταν πολλαπλά κλειδιά έχουν το ίδιο hash. Υπάρχουν διάφοροι τρόποι αντιμετώπισης αυτού, μερικοί από τους οποίους αποτυγχάνουν τον σκοπό του κατακερματισμού (αλλά είναι εύκολο να εφαρμοστούν). Κάποιοι από αυτούς δεν διατηρούν και διατηρούν την ιδιοκτησία σταθερού χρόνου, τουλάχιστον κατά μέσο όρο.

Το καλύτερο που έχω δει είναι ότι το addhash hash rehash, το οποίο αν η μνήμη εξυπηρετεί πριν από δεκαετίες, οι Gonnet και Munroe απέδειξαν ότι κατά μέσο όρο λίγο περισσότερο από 4 προσβάσεις με συντελεστή φορτίου 50%, ανεξαρτήτως μεγέθους hash table. Αυτό, ωστόσο, απαιτεί τη χρήση πρωτευόντων αριθμών, και αυτό καθιστά δύσκολη την εφαρμογή. Πρέπει να βρεις τους πρωταρχικούς αριθμούς με κάποιο τρόπο. Ευτυχώς, τα τραπέζια κατακερματισμού δεν γίνονται τόσο μεγάλα που γίνονται γελοία.