Perché sono i codici hash generati da questa funzione, non è unico?
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto testando la funzione VB sotto che ho avuto da una ricerca su Google.Ho intenzione di utilizzare per generare i codici hash per un rapido confronto tra stringhe.Tuttavia, ci sono occasioni in cui due stringhe diverse, hanno lo stesso codice hash.Per esempio, queste stringhe
"122Gen 1 dimensione heap (.NET CLR Memoria w3wp):mccsmtpteweb025.20833333333333E-02"
"122Gen 2 dimensione heap (.NET CLR Memoria w3wp):mccsmtpteweb015.20833333333333E-02"
hanno lo stesso codice hash di 237117279.
La prego di dirmi:- Cosa c'è di sbagliato con la funzione?- Come posso risolvere il problema?
Grazie
martin
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Soluzione
Sono le scommesse non ci sono solo i "occasioni" quando due stringhe di generare lo stesso hash usando la funzione.Infatti, probabilmente succede più spesso di quanto si pensi.
Un paio di cose per rendersi conto di:
Primo, ci sarà hash collisioni.Succede.Anche con veramente grandi spazi come MD5 (128 bit) ci sono ancora due stringhe che possono generare lo stesso hash risultante.Hai a che fare con quelle collisioni con la creazione di secchi.
Secondo, un valore long integer non è davvero un grande hash spazio.Si sta andando ad ottenere collisioni più di quanto sarebbe se si è utilizzato più bit.
In terzo luogo, ci sono le librerie disponibili in Visual Basic (come .NET System.Security.Cryptography spazio dei nomi) che fanno un lavoro molto migliore di hashing che la maggior parte dei comuni mortali.
Altri suggerimenti
Le due Stringhe hanno gli stessi caratteri.(Nota il " 2 " e " 1 " che sono i flip-flop)
Che è il motivo per cui il valore di hash è lo stesso.
Assicurarsi che la funzione di hash è di prendere in considerazione l'ordine dei caratteri.
Funzioni di Hash non sono una garanzia di unicità di valori hash.Se il valore di input range (a giudicare il vostro campione stringhe) è più grande di quello di uscita intervallo di valori (ad esempio numero intero a 32 bit), quindi l'unicità è fisicamente impossibile.
Se il problema più grande è che non tiene conto della posizione del byte, si potrebbe risolvere così:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
L'unica differenza è che aggiunge i caratteri posizione del byte di valore prima di XOR.
Nessuna funzione di hash può garantire l'unicità.Ci sono ~4 miliardi di interi a 32 bit, quindi, anche la migliore funzione di hash genera duplicati, quando sono presentati con ~4 miliardi e 1 stringhe (e probabilmente molto prima).
Movimento a 64-bit hash o anche 128-bit hash non è davvero la soluzione, anche se riduce la probabilità di una collisione.
Se si desidera una migliore funzione di hash si potrebbe guardare le hash crittografici, ma sarebbe meglio riconsiderare si algoritmo per decidere se si può fare con le collisioni in qualche altro modo.
Il Sistema.Di sicurezza.Crittografia spazio dei nomi contiene più classi che possono fare di hashing per voi (come MD5) che probabilmente hash meglio di quanto si potrebbe se stessi e richiede molto meno sforzo.
Non sempre è necessario reinventare la ruota.
Semplice XOR è un bad hash:troverete un sacco di stringhe che si scontrano.L'hash non dipende dall'ordine di lettere di una stringa, per una cosa.
Provare a utilizzare l'hash FNV http://isthe.com/chongo/tech/comp/fnv/
Questo è molto semplice da implementare.Sposta il codice hash dopo ogni XOR, in modo che le stesse lettere in un ordine diverso da produrre un hash diverso.
Funzioni di Hash non sono destinati a restituire valori distinti per le diverse stringhe.Tuttavia, una buona funzione hash deve restituire valori diversi per le stringhe che si assomigliano.Le funzioni Hash sono usate per la ricerca per molti motivi, tra cui la ricerca in una grande collezione.Se la funzione hash è buona e se si restituisce i valori nell'intervallo [0,N-1], quindi con una grande collezione di M oggetti si divide in N collezioni, ognuna con su M/N elementi.In questo modo, è necessario cercare solo in una matrice di M/N elementi invece che la ricerca in un array di M elementi.
Ma, se si hanno solo 2 stringhe, non è non più veloce per calcolare il valore hash per quelli!È meglio basta confrontare le due stringhe.
Un interresing funzione di hash potrebbe essere:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
Ho fissato l'evidenziazione della sintassi per lui.
Inoltre, per coloro che non sono sicuri per l'ambiente o sono stati suggerendo una più-secure hash:e ' il Classico (pre-.Net) VB, perché .Net sono necessarie le parentesi per la chiamata a CopyMemory.
IIRC, non sono sicuro di hash per il VB Classico.Non c'è molto là fuori sul web, quindi questo potrebbe essere il suo migliore scommessa.
Io piuttosto non vedere l'ambiente in cui si lavora.È questo .Net code?Se si vuole veramente buoni codici hash, vorrei raccomandare cercando in hash crittografici (provata algoritmi), invece di provare a scrivere il proprio.
Btw, potresti modificare il tuo post il codice e incollarlo nel Codice di Esempio (vedi barra degli strumenti)?Questo renderebbe più facile la lettura.
"Non farlo."
Scrivendo la propria funzione di hash è un grande errore, perché il tuo linguaggio certamente ha già un'implementazione di SHA-1, che è una perfettamente buona funzione di hash.Se avete solo bisogno di 32 bit (invece di 160 che SHA-1 fornisce), basta usare l'ultimo a 32 bit SHA-1.
Questo particolare funzioni di hash XORs tutti i caratteri in una stringa.Purtroppo XOR è associativa:
(a XOR b) XOR c = a XOR (b XOR c)
Così tutte le stringhe con lo stesso input di caratteri; lo stesso codice hash.Le due stringhe fornite sono le stesse, tranne che per la posizione dei due personaggi, quindi, dovrebbero avere lo stesso hashcode.
Potrebbe essere necessario trovare un migliore algoritmo MD5 sarebbe una buona scelta.
L'operazione di XOR è commutativa;che è, quando uno xor di tutti i caratteri in una stringa, l'ordine dei caratteri non importa.Tutti gli anagrammi di una stringa di produrre la stessa XOR hash.
Nel tuo esempio, la tua seconda stringa può essere generato dal suo primo scambio l' "1" dopo "...Gen " con il primo "2" dopo di esso.
Non c'è niente di sbagliato con la vostra funzione.Tutte le utili funzioni di hashing a volte generare collisioni, e il programma deve essere preparato per risolvere il problema.
Si verifica una collisione di ingresso, quando gli hash per un valore già identificato con un precedente di ingresso.Se un algoritmo di hashing non potrebbero generare collisioni, i valori hash avrebbe bisogno di essere grandi come i valori di input.Ad un algoritmo di hashing servirebbe solo rispetto a memorizzare i valori di input.
-Al.
C'è un visual basic attuazione di hash MD5 qui
