Co kryje się za metodą hashCode() dla String w Javie?

Question

Badałem metody hashCode() w java i znalazłem ten dla klasy String dziwne. Kod źródłowy jest następujący:

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

Sam kod jest dość prosty. Ale zastanawiam się, jaki jest powód do obliczania kodu skrótu w ten sposób?
Dlaczego warto wybrać 31?
Dlaczego zacząć od 0 zamiast value.length - 1?
Jakąkolwiek gwarancję, że spowoduje to, że kody skrótu będą mniej podatne na kolizję ze sobą?

Answer 1

Tak, prawdopodobieństwo kolizji hashcode jest bardzo niskie, jak na przykład w przypadku String, zależy to od wartości ciągu. Jeśli nie tworzymy żadnego ciągu z nowym operatorem, to jeśli nowy ciąg ma tę samą wartość, która już jest obecna, to nowy obiekt String nie jest tworzony, odnosi się do starej wartości ze sterty iw tym przypadku tylko wartość hashCode będzie być tak samo, jak się spodziewano.

umowy generalnej z hashcode jest:

Ilekroć jest wywoływane na tym samym obiekcie więcej niż jeden raz w trakcie wykonywania aplikacji Java, metoda hashCode musi konsekwentnie zwracają taką samą liczbą całkowitą, nie dostarczyły żadnych informacji wykorzystywanych w równych porównania w obiekcie są modyfikowane. Ta liczba całkowita nie musi pozostawać spójna od jednego wykonania aplikacji do innego wykonania tej samej aplikacji.

Z Java 1.2 klasa java.lang.String implementuje swój hashCode() używając algorytmu sumy produktów w całym tekście ciągu. [2] Biorąc pod uwagę przykład s klasy java.labg.String, na przykład, mogą mieć h (i) kod skrótu zdefiniowany przez

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

którym warunki są sumowane z wykorzystaniem Java 32-bitowy Int Ponadto, y [i] oznacza I-ty znak łańcucha, a n - długość s.

Dla odniesienia w Apache Harmony metoda hashCode jest:

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