Ποιος αλγόριθμος κατακερματισμού είναι ο καλύτερος για μοναδικότητα και ταχύτητα; Παραδείγματα (καλών) χρήσεων περιλαμβάνουν λεξικά κατακερματισμού.
Ξέρω ότι υπάρχουν πράγματα όπως ο SHA-256 και τέτοια, αλλά αυτοί οι αλγόριθμοι είναι σχεδιασμένοι για να είναι ασφαλείς, πράγμα που συνήθως σημαίνει ότι είναι πιο αργοί από αλγόριθμους που είναι λιγότερο μοναδικοί. Θέλω έναν αλγόριθμο κατακερματισμού σχεδιασμένο να είναι γρήγορος, αλλά να παραμένει αρκετά μοναδικός για την αποφυγή συγκρούσεων.
Εδώ είναι ένας κατάλογος συναρτήσεων κατακερματισμού, αλλά η σύντομη εκδοχή είναι:
Αν απλά θέλετε να έχετε μια καλή συνάρτηση κατακερματισμού και δεν μπορείτε να περιμένετε, η
djb2
είναι μια από τις καλύτερες συναρτήσεις κατακερματισμού συμβολοσειρών που γνωρίζω. Έχει εξαιρετική κατανομή και ταχύτητα σε πολλά διαφορετικά σύνολα κλειδιών και μεγέθη πινάκων
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
Οι αλγόριθμοι SHA (συμπεριλαμβανομένου του SHA-256) είναι σχεδιασμένοι για να είναι γρήγοροι.
Στην πραγματικότητα, η ταχύτητά τους μπορεί να αποτελέσει πρόβλημα μερικές φορές. Συγκεκριμένα, μια κοινή τεχνική για την αποθήκευση ενός token που προέρχεται από κωδικό πρόσβασης είναι η εκτέλεση ενός τυπικού γρήγορου αλγορίθμου κατακερματισμού 10.000 φορές (αποθήκευση του κατακερματισμού του κατακερματισμού του κατακερματισμού του κατακερματισμού του ... κωδικού πρόσβασης).
#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'
def run_random_digest(digest, count)
v = SecureRandom.random_bytes(digest.block_length)
count.times { v = digest.digest(v) }
v
end
Benchmark.bmbm do |x|
x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end
Έξοδος:
Rehearsal ------------------------------------
1.480000 0.000000 1.480000 ( 1.391229)
--------------------------- total: 1.480000sec
user system total real
1.400000 0.000000 1.400000 ( 1.382016)
Η Java χρησιμοποιεί τον αυτό απλό αλγόριθμο πολλαπλασιασμού και πρόσθεσης:
Ο κωδικός κατακερματισμού για ένα αντικείμενο String υπολογίζεται ως εξής
>,
s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]
>,
χρησιμοποιώντας την αριθμητική int, όπου s[i]
είναι ο i-οστός χαρακτήρας της συμβολοσειράς, n
είναι το μήκος της συμβολοσειράς και ^
υποδηλώνει τον πολλαπλασιασμό. (Η τιμή κατακερματισμού της κενής συμβολοσειράς είναι μηδέν).
Πιθανόν να υπάρχουν πολύ καλύτεροι, αλλά αυτός είναι αρκετά διαδεδομένος και φαίνεται να είναι ένας καλός συμβιβασμός μεταξύ ταχύτητας και μοναδικότητας.