L'hash di un GUID è unico?

Question

Creo un GUID (come stringa) e ne ottengo l'hash. Posso considerare questo hash come unico?

Answer 1

Non univoco in modo affidabile come il GUID stesso, no.

Solo per espandere, stai riducendo la tua unicità di un fattore 4, passando da 16 byte a 4 byte di possibili combinazioni.

Come sottolineato nei commenti, la dimensione dell'hash farà la differenza. La cosa a 4 byte era un presupposto, per lo meno orribile, lo so, che potrebbe essere usato in .NET, dove la dimensione di hash predefinita è di 4 byte (int). Quindi puoi sostituire ciò che ho detto sopra con qualsiasi dimensione in byte che possa essere il tuo hash.

Answer 2

No.

Vedi qui, se vuoi un mini GUID: http: //blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Answer 3

In una parola, no.

Supponiamo che il tuo hash abbia meno bit del GUID, secondo il principio del buco del piccione, deve esistere più di una mappatura di alcuni GUID - > hash semplicemente perché ci sono meno hash dei GUID.

Se assumiamo che l'hash abbia un numero maggiore di bit rispetto al GUID, c'è una possibilità molto piccola, ma limitata, di una collisione, supponendo che tu stia usando una buona funzione hash.

Answer 4

Nessuna funzione hash che riduce un blocco di dati di dimensioni arbitrarie a un numero di bit di dimensioni fisse produrrà una mappatura da 1 a 1 tra i due. Esisterà sempre la possibilità di ridurre due blocchi di dati diversi alla stessa sequenza di bit nell'hash.

I buoni algoritmi di hash riducono al minimo la probabilità che ciò accada e, generalmente, più bit nell'hash, meno possibilità di una collisione.

Answer 5

È non garantito , a causa di collisioni di hash . Il GUID stesso è quasi garantito.

Per motivi pratici si può presumere che un hash sia unico, ma perché non usare il GUID stesso?

Answer 6

No, e non assumerei l'unicità di alcun valore hash. Non dovrebbe importare perché i valori di hash non devono essere univoci, devono solo essere distribuiti uniformemente su tutto il loro intervallo. Più uniforme è la distribuzione, minori sono le collisioni (nella tabella hash). Un minor numero di collisioni significa migliori prestazioni hashtable.

fyi Per una buona descrizione di come funzionano le tabelle hash, leggi la risposta accettata a Cosa sono gli hashtable e gli hashap e i loro casi d'uso tipici?

Answer 7

Se usi l'hash crittografico (MD5, SHA1, RIPEMD160), l'hash sarà unico (collisioni modulo che sono molto improbabili - SHA1 viene usato ad es. per firme digitali e MD5 è anche resistente alle collisioni su casuale ingressi ). Tuttavia, perché vuoi eseguire l'hashing di un GUID?

Answer 8

Vorrei eseguire l'hashing di un GUID di dimensioni X con la consapevolezza che a volte ho 10 o meno GUID nel set, quindi potrei cavarmela con un hash più corto senza collisioni che se avessi 10.000.000 GUID in un set. Vorrei solo essere in grado di specificare la dimensione dell'hash quando chiamo la funzione.