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

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

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

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

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

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

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

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

Βήμα 1: Ξεκινήστε με μια βάση (Offset Basis)

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

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

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

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

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

Βήμα 4: Προσθήκη μιας Πινελιάς Μαγείας (Λειτουργία XOR)

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

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

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

Βήμα 6: Τελικό Smoothie (Αξία Hash)

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

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

Περαιτέρω ανάγνωση

Αν σας άρεσε αυτή η ανάρτηση, ίσως σας αρέσουν και αυτές οι προτάσεις:

• SHA3-384 Υπολογιστής κωδικού κατακερματισμού
• XXH-32 Υπολογιστής κωδικού κατακερματισμού
• Υπολογιστής κώδικα κατακερματισμού HAVAL-224/4