Cercando di migliorare le prestazioni di una funzione che confronta le stringhe, ho deciso di confrontarle confrontandole con gli hash. Quindi c'è una garanzia se l'hash di 2 stringhe molto lunghe sono uguali tra loro quindi le stringhe sono uguali tra loro?Confronto di stringhe lunghe con i loro hash
Mentre è garantito che 2 stringhe identiche daranno uguali hash, viceversa non è vero: per un dato hash, ci sono sempre diverse stringhe possibili che producono lo stesso hash. Ciò è vero a causa dello PigeonHole principle.
Detto questo, le possibilità di 2 stringhe diverse che producono lo stesso hash possono essere rese infinitesime, al punto da essere considerate equivalenti a null.
Un esempio abbastanza classico di tale hash è MD5, che ha una distribuzione quasi perfetta a 128 bit. Il che significa che hai una possibilità in 2^128 che 2 stringhe diverse producano lo stesso hash. Beh, in pratica, quasi la stessa cosa impossibile.
È interessante notare che MD5 è stato interrotto: un utente malintenzionato può _intentionally_ creare una stringa che esegue l'hash su qualsiasi valore specificato. Semplicemente non ci sono abbastanza bit, ecco perché SHA è diventato lo standard corrente in crittografia. –
Sì, questa è la grande differenza tra ottenere una "collisione casuale" e ottenere una "collisione intenzionale". Sul fronte casuale, MD5 è ancora abbastanza buono. Ora, se il sistema deve prendere in considerazione il rischio di collisione intenzionale (che non è sempre necessario), allora sì, MD5 non è più abbastanza buono. – Cyan
in che modo la generazione e il confronto degli hash MD5 possono essere più veloci rispetto al confronto delle stringhe originali?!? – Aprillion
Non sono sicuro, se le prestazioni saranno migliorate. Entrambi: costruire hash + confrontare interi e semplicemente confrontare stringhe usando equals hanno la stessa complessità, che risiede in O (n), dove n è il numero di caratteri.
Nel semplice caso comune in cui due stringhe lunghe devono essere confrontate per determinare se sono identiche o meno, un semplice confronto sarebbe molto preferito su un hash, per due ragioni. Innanzitutto, come sottolineato da @wildplasser, l'hash richiede che tutti i byte di entrambe le stringhe debbano essere attraversati per calcolare i due valori hash, mentre il confronto semplice è veloce, e deve solo attraversare i byte fino a quando non viene trovata la prima differenza, che può essere molto inferiore all'intera lunghezza della corda. E in secondo luogo, è garantito un semplice confronto per rilevare eventuali differenze, mentre l'hash fornisce solo un'alta probabilità che siano identici, come sottolineato da @AdamLiss e @Cyan.
Esistono, tuttavia, diversi casi interessanti in cui il confronto dell'hash può essere utilizzato con grande vantaggio. Come menzionato da @Cyan se il confronto deve essere eseguito più di una volta, o deve essere memorizzato per un uso successivo, l'hash potrebbe essere più veloce. Un caso non menzionato da altri è se le stringhe si trovano su macchine diverse collegate tramite una rete locale o Internet. Passare una piccola quantità di dati tra le due macchine sarà generalmente molto più veloce. Il primo controllo più semplice è confrontare la dimensione dei due, se diverso, il gioco è fatto. Altrimenti, calcola l'hash, ognuno sulla propria macchina (supponendo che tu sia in grado di creare il processo sulla macchina remota) e di nuovo, se diverso, hai finito. Se i valori hash sono gli stessi, e se devi avere assoluta certezza, non esiste una scorciatoia facile a quella certezza. L'utilizzo della compressione senza perdita su entrambe le estremità consente di trasferire meno dati per il confronto. E infine, se le due stringhe sono separate dal tempo, come accennato da @Cyan, se vuoi sapere se un file è cambiato da ieri, e hai salvato l'hash dalla versione di ieri, allora puoi confrontare l'hash di oggi ad esso .
Spero che questo aiuti a stimolare alcune idee "out of the box" per qualcuno.
Credo di si. Gli hash sono rappresentazioni assolute dei dati che contengono. Quindi stringhe uguali dovrebbero avere gli stessi hash. – Jeremy1026
Perché non confrontare le stringhe in primo luogo. Calcolare gli hash ti costringerà a ispezionare ogni carattere di entrambe le stringhe. Così li confronta (ma potrebbe tornare "disuguale" alla prima mancata corrispondenza) – wildplasser
@ Jeremy1026: Semplicemente non è vero. Supponiamo che tu usi un hash a 4 bit. 4 bit possono contenere 2^4 = 16 valori diversi, quindi non è mai possibile distinguere tra più di 16 stringhe con quell'hash. In pratica, gli hash sono in genere centinaia di bit, ma c'è sempre un limite al numero di elementi che possono distinguere.Certo, le collisioni sono estremamente improbabili con un hash sufficientemente lungo, ma non c'è mai la garanzia che stringhe diverse abbiano hash differenti. –