Cosa c'è dietro il metodo hashCode() per String in Java?

Question

Ho studiato i metodi hashCode() in java e ho trovato quello strano per la classe String. Il codice sorgente è il seguente:

public int hashCode() { 
    int h = hash; 
    if (h == 0 && value.length > 0) { 
     char val[] = value; 

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

Il codice stesso è abbastanza semplice. Ma mi chiedo quale sia la ragione per calcolare il codice hash in questo modo?
Perché scegliere 31?
Perché iniziare da 0 anziché value.length - 1?
Qualsiasi garanzia che ciò renderebbe hashcodes meno possibile collidere tra loro?

Answer 1

Sì, la probabilità di collisione hashcode è molto bassa, ad esempio in caso di stringa dipende dal valore di stringa. Se non stiamo creando alcuna stringa con un nuovo operatore, se la nuova stringa ha lo stesso valore già presente, allora il nuovo oggetto String non viene creato, si riferisce al vecchio valore dall'heap e in questo caso solo il valore di hashCode sii come previsto

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 numero intero, a condizione alcuna informazione utilizzata in pari i confronti sull'oggetto sono modificati. Questo numero intero non deve rimanere coerente da un'esecuzione di un'applicazione a un'altra esecuzione della stessa applicazione.

Da Java 1.2, la classe java.lang.String implementa il suo hashCode() utilizzando un algoritmo sum del prodotto sull'intero testo della stringa. [2] Dato un'istanza s della classe java.lang.String, per esempio, avrebbe un codice hash h (s) definita da

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

cui termini sono sommati utilizzando Java 32 bit int Inoltre, s [i] denota il carattere ith della stringa, e n è la lunghezza di s.

Per il vostro riferimento in Apache Harmony metodo hashCode è:

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; 
}