Sto cercando una funzione hash speciale. Diciamo che ho una lunga lista di stringhe, se le ordino per i loro valori hash dovrebbero essere ordinate in modo quasi casuale.Alla ricerca di una funzione hash veloce
Il punto più importante è: deve essere super veloce. Ho provato md5 e sha1 e stanno usando molta potenza della cpu.
Gli scontri non sono un problema.
Sto usando javascript, quindi non dovrebbe essere troppo complicato da implementare.
Sembra che si desideri il tipo di funzione hash utilizzata in una tabella hash, non l'ordinamento utilizzato per rilevare duplicati o manomissioni.
Googling ti fornirà una grande quantità di informazioni sulle funzioni di hash alternative. Per cominciare, stare lontano dagli hash delle firme crittografiche (come MD-5 o SHA-1), risolvono un altro problema.
Dai un'occhiata all'hash di Murmur. Ha una bella spazio/scontro trade-off:
L'ho dimenticato. – bmargulies
Se la velocità è di primaria importanza, è possibile implementare un semplice hash ad-hoc, per esempio prendi la prima e l'ultima lettera e ordina la tua corda dall'ultima e prima lettera. Il risultato sembrerebbe, come dici tu, "quasi casuale" e sarebbe veloce. Per esempio, una parte della mia risposta allineati in questo modo sarebbe simile a questa:
ca ad-hoc
el like
es simple
gt taking
hh hash
nc can
ti implement
uy you
Se l'hash non fa un buon lavoro per evitare collisioni, allora qualsiasi velocità acquisita durante l'hashing andrà persa a causa delle collisioni. Il trucco è trovare un equilibrio tra i due. –
Julian ha detto esplicitamente nella sua domanda che gli scontri/le collisioni non sono un problema e posso capire perché. Un semplice hash come questo fornirà un ordine di parole quasi casuale non ovvio: se più parole hanno lo stesso valore di hash, potrebbe non preoccuparsi di ordinarle ulteriormente e semplicemente di prenderle così come vengono senza alcun impatto sulle prestazioni. Ovviamente, questa specifica funzione di hash non funzionerebbe bene con tutti i tipi di set di dati, ma non sembra che si parli di casi d'angolo. –
Hsieh, Murmur, Bob Jenkin's viene in mente.
A nice page about hash functions che ha alcuni test per la qualità e un semplice hash S-box pure.
Sembra che sia meglio allontanarsi da SuperFastHash. (1 ° link sopra) http://www.team5150.com/~andrew/blog/2007/03/breaking_superfasthash.html – Matt
@Matt Bene, in base a ciò, dovresti evitare tutti gli hash menzionati in questa pagina in una qualsiasi delle risposte , dal momento che non sono gli hash crittografici - in cambio, sono molto più veloci di eg SHA, e - proprio come ha chiesto l'OP - può essere implementato in JS con poco sforzo. ;-). Si prega di notare la differenza tra crypto vs hash "standard": http://security.stackexchange.com/questions/11839/what-is-the-difference-between-a-hash-function-and-a-cryptographic -hash funzione –
vedere anche http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is- best-for-uniqueness-and-speed – rogerdpack