Consistenza del hashCode () su una stringa Java

StackOverflow https://stackoverflow.com/questions/785091

  •  16-09-2019
  •  | 
  •  

Domanda

Il valore hashCode di una stringa Java viene calcolata come ( String.hashCode () ): 

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Ci sono circostanze (ad esempio la versione JVM, fornitore, etc.) in base al quale la seguente espressione valuterà a false? 

boolean expression = "This is a Java string".hashCode() == 586653468

Aggiornamento # 1: Se si sostiene che la risposta è "sì, ci sono queste circostanze" - quindi si prega di dare un esempio concreto di quando "Questa è una stringa Java" .hashCode ()! = 586653468. Cercate di essere il più specifici / concreto possibile.

Aggiornamento # 2: Sappiamo tutti che fare affidamento sui dettagli di implementazione di hashCode () è un male in generale. Comunque, sto parlando specificamente String.hashCode () - quindi si prega di tenere la risposta concentrati per String.hashCode (). Object.hashCode () è del tutto irrilevante nel contesto di questa domanda.

È stato utile?

Soluzione

Posso vedere che la documentazione fin da Java 1.2.

Mentre è vero che in generale non si dovrebbe fare affidamento su un'implementazione codice hash rimanendo la stessa, è ora documentato il comportamento per java.lang.String, quindi cambiarla conterebbe come la rottura dei contratti esistenti.

Per quanto possibile, non si dovrebbe fare affidamento su codici hash che soggiornano nello stesso tra le versioni, ecc - ma nella mia mente java.lang.String è un caso particolare, semplicemente perché l'algoritmo di ha è specificato ... fintanto siete disposti ad abbandonare la compatibilità con le versioni prima che è stato specificato l'algoritmo, ovviamente.

Altri suggerimenti

Ho trovato qualcosa su JDK 1.0 e 1.1 e> = 1,2:

  

In JDK 1.0.x e 1.1.x il hashCode   funzione per lunghi Corde lavorate dai   campionamento ogni personaggio all'ennesima potenza. Questo   abbastanza bene garantito che avrebbe dovuto   molte stringhe hashing allo stesso   valore, rallentando così Hashtable   consultare. In JDK 1.2 la funzione ha   stato migliorato per moltiplicare il risultato   finora da 31 quindi aggiungere il successivo   carattere in sequenza. Questo è un   po 'più lento, ma è molto meglio a   evitare le collisioni.   Fonte: http://mindprod.com/jgloss/hashcode.html

Qualcosa di diverso, perché ti sembra di avere bisogno di un numero: ne dite di usare CRC32 o MD5 invece di codice hash e vi sono buone per andare - discussioni e nessuna preoccupazione a tutti ...

Non si dovrebbe fare affidamento su un codice hash è uguale a un valore specifico. Basta che restituisca risultati coerenti all'interno della stessa esecuzione. La documentazione API dire quanto segue:

  

Il contratto generale di hashCode è:

     
      
  • 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 tornare sempre lo stesso intero, non ha fornito alcuna informazione utilizzata in uguale confronti sul oggetto viene modificato. Questo numero intero non deve rimanere costante da un'esecuzione di un'applicazione ad un'altra esecuzione della stessa applicazione.
    •   

Modifica Dal momento che il Javadoc per String.hashCode () specifica come codice hash di una stringa viene calcolato, ogni violazione di questo violerebbe le specifiche API pubblica.

Come detto sopra, in generale, non si dovrebbe fare affidamento sul codice hash di una classe rimanendo lo stesso. Si noti che anche le successive esecuzioni del stessa applicazione su stessi possono produrre diversi valori di hash VM. AFAIK funzione hash del Sun JVM calcola lo stesso hash su ogni corsa, ma che non è garantito.

Si noti che questo non è teorica. La funzione di hash per java.lang.String è stato cambiato in JDK1. 2 (il vecchio hash ha avuto problemi con le stringhe gerarchici come gli URL o nomi di file, come si tendeva a produrre lo stesso hash per le stringhe che differivano solo alla fine).

java.lang.String è un caso particolare, come l'algoritmo del suo hashCode () è (ora) documentato, quindi probabilmente si può fare affidamento su questo. Sarei ancora considero cattiva pratica. Se avete bisogno di un algoritmo di hash con particolari proprietà, documentate, basta scrivere un: -).

Un altro (!) Problema di cui preoccuparsi è il possibile cambio di realizzazione tra le prime versioni / ritardo di Java. Non credo che i dettagli di implementazione sono scolpiti nella pietra, e così potenzialmente un aggiornamento a una versione futuro Java potrebbe causare problemi.

Linea di fondo è, non vorrei contare sulla realizzazione di hashCode().

Forse si può evidenziare che problema si sta effettivamente cercando di risolvere utilizzando questo meccanismo, e che metterà in evidenza un approccio più adatto.

Se siete preoccupati per i cambiamenti ed eventualmente incompatili VM, basta copiare l'attuazione codice hash esistente nella propria classe di utilità, e l'uso che per generare i codici hash.

Proprio per rispondere alla tua domanda e di non continuare a nessuna discussione. L'implementazione di Apache Harmony JDK sembra usare un algoritmo diverso, almeno sembra completamente diverso:

Sun JDK 

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Apache Harmony 

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

Sentiti libero di controllare voi stessi ...

Il codice hash sarà calcolato in base ai valori ASCII dei caratteri nella stringa.

Questa è l'implementazione della classe String è la seguente 

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

Le collisioni in codice hash sono inevitabili. Ad esempio, le stringhe "EA" e "FB" danno lo stesso codice hash di 2236

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top