è java's hashCode() deterministico?Deterministic hashCode() di java?
Cerco di implementare un motore di ricerca di documenti che utilizza l'algoritmo di minhashing e io uso hashCode per le parole pre-hash. La stessa parola otterrà lo stesso hash ogni volta che la eseguo?
Sta per ottenere lo stesso hash anche se lo eseguo da una macchina diversa (32 bit contro 64 bit)?
Essa dipende dalla classe a cui ti riferisci. Base Object.hashCode implementazione non è, dal momento che, come stated in the documentation:
Per quanto è ragionevolmente possibile, il metodo hashCode definito dalla classe Object fa ritorno interi distinti per oggetti distinti. (Questo è tipicamente implementato convertendo l'indirizzo interno dell'oggetto in numero intero, ma questa tecnica attuazione non è richiesta dal linguaggio di programmazione JavaTM.)
indirizzi non sono deterministici, considerare che a volte sono addirittura usato come fonte di entropia.
Ma, per esempio, String ha un codice hash deterministico determinato come segue:
(immagine tratta da Wikipedia)
In alcuni casi non c'è nemmeno una definizione deterministica ragionevole per il codice hash.
+1 ma dovresti usare [il javadoc] (http://docs.oracle.com/javase/7/docs/api/java/lang/String.html#hashCode%28%29) come riferimento piuttosto che Wikipedia . – assylias
Ho solo affermato che l'immagine della formula è stata copiata da Wikipedia, non che l'ho usata come riferimento. Chiarito. –
Il contratto generale di hashCode è come Javadoc dice:
Ogni volta che viene richiamato sullo stesso oggetto più di una volta nel corso di un'esecuzione di un'applicazione Java, il metodo hashCode deve sempre restituire lo stesso numero intero, a condizione no le informazioni utilizzate nei confronti di pari merito sull'oggetto sono modificate. Questo numero intero non deve rimanere coerente da un'esecuzione di un'applicazione a un'altra esecuzione della stessa applicazione.
Is the same word going to get the same hash every time that I run it?
Durante l'esecuzione dell'applicazione, invocando hashCode() di parole uguali (assumo la parola è un'istanza String e equals() è stato sostituito in String) deve restituire lo stesso numero intero.
EDIT Dal momento che la javadoc per String.hashCode() specifica come viene calcolato il codice hash di una stringa, è deterministica.
Returns a hash code for this string. The hash code for a String object is computed as : s[0]*31^(n-1) + s 1 *31^(n-2) + ... + s[n-1]
La tua risposta è confusa. 'hashcode' è ben definito e deterministico per le stringhe, sia che la macchina sia 32 o 64 bit – assylias
Modificato !!!!!!!!!! – NINCOMPOOP
@assylias Sì, che può effettivamente essere un rischio DoS! Un utente malintenzionato può costruire una richiesta HTTP con un gruppo di stringhe (env vars e parametri di query) intenzionalmente progettate per avere lo stesso valore hash, trasformando una mappa di hash ~ O (1) in una lista collegata a O (N). Womp womp. – yshavit
Parlando di oggetti in generale: non è così.
Tuttavia, se si sta parlando specificially su String, quindi il calcolo codice hash è espressamente specificato nella API di String.hashCode():
restituisce un codice hash per questa stringa.Il codice hash per un oggetto String viene calcolato come
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]utilizzando int aritmetica, dove s [i] è il carattere esimo della stringa, n è la lunghezza della stringa, e^indica l'elevamento a potenza. (Il valore hash della stringa vuota è zero)
In altre parole: si dovrebbe poter dipendere dal fatto che l'hashCode è stabile per le stringhe.
Non ci scommetterò ... Potrebbe anche accadere che l'hash possa essere correlato all'indirizzo dell'indirizzo, e quindi potrebbe cambiare anche da una corsa a quella successiva ... –
Vedere http: //stackoverflow.com/questions/1516843/java-object-hashcode-result-constant-across-all-jvms-systems – Annabelle
Perché non chiedere ad un amico di eseguire un esempio di codice e vedere? Perché non pubblicare il suddetto piccolo pezzo di codice in modo che tutti possiamo farlo? :) Detto questo, io * non penso * che hashCode sia coerente tra più esecuzioni, solo per quello nella VM. – Shark