Posso dipendere dai valori di GetHashCode() per essere coerenti?
https://stackoverflow.com/questions/53086
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Il valore restituito di GetHashCode() è garantito per essere coerente presupponendo che venga utilizzato lo stesso valore di stringa?(C#/ASP.NET)
Oggi ho caricato il mio codice su un server e con mia sorpresa ho dovuto reindicizzare alcuni dati perché il mio server (win2008 a 64 bit) restituiva valori diversi rispetto al mio computer desktop.
Soluzione
Se non sbaglio, GetHashCode è coerente dato lo stesso valore, ma NON è garantito che sia coerente tra le diverse versioni del framework.
Dai documenti MSDN su String.GetHashCode():
Il comportamento di GetHashCode dipende dalla sua implementazione, che potrebbe cambiare da una versione di Common Language Runtime a un'altra.Un motivo per cui ciò potrebbe accadere è migliorare le prestazioni di GetHashCode.
Altri suggerimenti
Ho avuto un problema simile in cui ho riempito una tabella del database con informazioni che dipendevano da String.GetHashCode (non è l'idea migliore) e quando ho aggiornato il server su cui stavo lavorando a x64 ho notato che i valori che stavo ottenendo da String.GetHashCode erano incompatibile con quanto già presente in tabella.La mia soluzione era utilizzare la mia versione di GetHashCode che restituisce lo stesso valore di String.GetHashCode su un framework x86.
Ecco il codice, non dimenticare di compilare con "Consenti codice non sicuro":
/// <summary>
/// Similar to String.GetHashCode but returns the same as the x86 version of String.GetHashCode for x64 and x86 frameworks.
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static unsafe int GetHashCode32(string s)
{
fixed (char* str = s.ToCharArray())
{
char* chPtr = str;
int num = 0x15051505;
int num2 = num;
int* numPtr = (int*)chPtr;
for (int i = s.Length; i > 0; i -= 4)
{
num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
if (i <= 2)
{
break;
}
num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
numPtr += 2;
}
return (num + (num2 * 0x5d588b65));
}
}
L'implementazione dipende dalla versione del framework ma dipende anche da architettura.L'implementazione di string.GetHashCode() è diversa nelle versioni x86 e x64 del framework anche se hanno lo stesso numero di versione.
Mi chiedo se ci siano differenze tra i sistemi operativi a 32 e 64 bit, perché sono certo che sia il mio server che il computer di casa eseguano la stessa versione di .NET
Sono sempre stato stanco di usare GetHashCode(), potrebbe essere una buona idea per me semplicemente interpretare il mio algoritmo hash.Beh, almeno ho finito per scrivere una rapida pagina .aspx reindicizzata per questo motivo.
Utilizzi Win2008 x86 come desktop?Perché Win2008 include la versione 2.0.50727.1434, che è una versione aggiornata della 2.0 inclusa in Vista RTM.
Ciò che abbiamo notato tuttavia, quando un oggetto è in un oggetto di raccolta hash (un hashtable, un dizionario ecc.), Quando 2 oggetti non sono unici ma i loro hashcodi lo sono, l'hashcode è usato solo come una prima ricerca di opzione, se non ci sono non -Code uniche di hash utilizzate, l'operatore di uguaglianza viene sempre utilizzato come fallimento per la determa dell'uguaglianza.
Questo è il modo in cui funzionano le ricerche di hash, giusto?Ogni bucket contiene un elenco di elementi con lo stesso codice hash.
Quindi, per trovare l'elemento corretto in queste condizioni, viene eseguita una ricerca lineare utilizzando il confronto dell'uguaglianza dei valori.
E se l'implementazione dell'hashing raggiunge una buona distribuzione, questa ricerca non è richiesta, ovvero un elemento per bucket.
La mia comprensione è corretta?
Non è una risposta diretta alla tua domanda, a cui Jonas ha risposto bene, tuttavia potrebbe essere utile se sei preoccupato per i test di uguaglianza negli hash
Dai nostri test, a seconda di ciò che richiedi con gli hashcode, in C#, gli hashcode non devono essere univoci per le operazioni di uguaglianza.Ad esempio, considera quanto segue:
Avevamo l'esigenza di sovraccaricare l'operatore equals, e quindi la funzione GetHashCode dei nostri oggetti poiché erano diventati volatili e senza stato e si ricavavano direttamente dai dati, quindi in un punto dell'applicazione dovevamo garantire che un oggetto fosse visualizzato come uguale ad un altro oggetto se provenisse dagli stessi dati, non solo se fosse lo stesso riferimento.I nostri identificatori di dati univoci sono Guid.
È stato facile gestire l'operatore uguale poiché abbiamo appena controllato il Guid del record (dopo aver verificato la presenza di null).
Sfortunatamente la dimensione dei dati HashCode (essendo un int) dipende dal sistema operativo e, nel nostro sistema a 32 bit, l'hashcode sarebbe a 32 bit.Matematicamente, quando sovrascriviamo la funzione GetHashCode, è impossibile generare un hashcode univoco da un guid maggiore di 32 bit (guardalo dal contrario, come tradurresti un intero a 32 bit in un guid?).
Abbiamo poi fatto alcuni test in cui abbiamo preso il Guid come stringa e restituito l'HashCode del Guid, che quasi sempre restituisce un identificatore univoco nei nostri test, ma non sempre.
Ciò che abbiamo notato, tuttavia, quando un oggetto si trova in un oggetto di raccolta con hash (una tabella hash, un dizionario ecc.), quando 2 oggetti non sono univoci ma i loro hashcode lo sono, l'hashcode viene utilizzato solo come prima opzione di ricerca, se non sono presenti -codici hash univoci utilizzati, l'operatore di uguaglianza viene sempre utilizzato come ripiego per determinare l'uguaglianza.
Come ho detto, questo potrebbe essere rilevante o meno per la tua situazione, ma se lo è è un consiglio utile.
AGGIORNAMENTO
Per dimostrarlo, abbiamo una Hashtable:
Chiave: Oggetto A (Hashcode 1), valore Oggetto A1
Chiave: Oggetto B (Codice Hash 1), valore Oggetto B1
Chiave: Oggetto C (Hashcode 1), valore Oggetto C1
Chiave: Oggetto D (Hashcode 2), valore Oggetto D1
Chiave: Oggetto E (Hashcode 3), valore Oggetto E1
Quando chiamo la tabella hash per l'oggetto con la chiave dell'oggetto A, l'oggetto A1 verrà restituito dopo 2 passaggi, una chiamata per l'hashcode 1, quindi un controllo di uguaglianza sull'oggetto chiave poiché non esiste una chiave univoca con l'hashcode 1
Quando chiamo la tabella hash per l'oggetto con la chiave dell'oggetto D, l'oggetto D1 verrà restituito dopo 1 passaggio, una ricerca hash
/// <summary>
/// Default implementation of string.GetHashCode is not consistent on different platforms (x32/x64 which is our case) and frameworks.
/// FNV-1a - (Fowler/Noll/Vo) is a fast, consistent, non-cryptographic hash algorithm with good dispersion. (see http://isthe.com/chongo/tech/comp/fnv/#FNV-1a)
/// </summary>
private static int GetFNV1aHashCode(string str)
{
if (str == null)
return 0;
var length = str.Length;
// original FNV-1a has 32 bit offset_basis = 2166136261 but length gives a bit better dispersion (2%) for our case where all the strings are equal length, for example: "3EC0FFFF01ECD9C4001B01E2A707"
int hash = length;
for (int i = 0; i != length; ++i)
hash = (hash ^ str[i]) * 16777619;
return hash;
}
Questa implementazione può essere più lenta di quella non sicura pubblicata in precedenza.Ma molto più semplice e sicuro.
Dovrei dire... non puoi fare affidamento su di esso.Ad esempio, se eseguo file1 tramite il codice hash md5 di C# e copio e incollo lo stesso file in una nuova directory... il codice hash risulta diverso anche se è lo stesso file.Ovviamente è la stessa versione .net, stesso tutto.L’unica cosa che è cambiata è stato il percorso.
