Υπολογιστής κατακερματισμού κώδικα Fowler-Noll-Vo FNV1-32

Η συνάρτηση κατακερματισμού 32-bit FNV-1 είναι μέρος της οικογένειας συναρτήσεων κατακερματισμού Fowler–Noll–Vo (FNV), σχεδιασμένη για γρήγορο κατακερματισμό διατηρώντας παράλληλα μια καλή κατανομή των τιμών κατακερματισμού. Χρησιμοποιείται συνήθως σε εφαρμογές όπως πίνακες κατακερματισμού, αθροίσματα ελέγχου και αναζητήσεις δεδομένων. Παράγει έναν κωδικό κατακερματισμού 32 bit (4 byte), που συχνά αντιπροσωπεύεται ως 8ψήφιος δεκαεξαδικός αριθμός.

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

Σχετικά με τον αλγόριθμο κατακερματισμού 32 bit Fowler-Noll-Vo FNV-1

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

Αρχικά, ας σκεφτούμε τον αλγόριθμο FNV-1 σαν μια συνταγή για την παρασκευή ενός ειδικού smoothie. Κάθε συστατικό που προσθέτετε (όπως φρούτα, γάλα ή μέλι) αντιπροσωπεύει ένα κομμάτι δεδομένων - όπως γράμματα, αριθμούς ή ακόμα και ένα ολόκληρο αρχείο.

Τώρα, ο στόχος είναι να αναμειχθούν αυτά τα συστατικά με έναν πολύ συγκεκριμένο τρόπο, ώστε ακόμη και η πιο μικρή αλλαγή στη συνταγή (όπως η προσθήκη ενός επιπλέον βατόμουρου) να κάνει το smoothie να έχει εντελώς διαφορετική γεύση. Έτσι λειτουργούν οι συναρτήσεις κατακερματισμού - δημιουργούν μια μοναδική "γεύση" (ή τιμή κατακερματισμού) για κάθε μοναδικό σύνολο συστατικών (ή δεδομένα εισόδου).

Ο τρόπος με τον οποίο ο αλγόριθμος FNV-1 το κάνει αυτό είναι μια διαδικασία πολλαπλών βημάτων:

Βήμα 1: Ξεκινήστε με μια βάση (Βάση μετατόπισης)

Σκεφτείτε το σαν να ρίχνετε μια ειδική βάση smoothie στο μπλέντερ σας. Αυτή η βάση είναι πάντα η ίδια, ανεξάρτητα από τα συστατικά που προσθέτετε. Στο FNV-1, αυτό ονομάζεται "βάση μετατόπισης" - απλώς ένας φανταχτερός αριθμός εκκίνησης.

Βήμα 2: Προσθέστε τα συστατικά ένα προς ένα (Επεξεργασία δεδομένων)

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

Βήμα 3: Ανάμειξη με μυστικό πολλαπλασιαστή (The FNV Prime)

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

Βήμα 4: Προσθέστε ένα Dash of Magic (Λειτουργία XOR)

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

Βήμα 5: Επαναλάβετε μέχρι να γίνει

Συνεχίζετε να ανακατεύετε και να πασπαλίζετε μαγικά μετά από κάθε νέο συστατικό μέχρι να τα επεξεργαστείτε όλα.

Βήμα 6: Τελικό Smoothie (Τιμή κατακερματισμού)

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

Η έκδοση που παρουσιάζεται εδώ είναι η αρχική έκδοση 32 bit FNV-1. Υπάρχει επίσης μια βελτιωμένη έκδοση FNV-1a 32 bit διαθέσιμη: Υπολογιστής κατακερματισμού κώδικα Fowler-Noll-Vo FNV1a-32