Spójność hashCode () w ciągu Java

Wartość hashCode ciągu Java jest obliczana jako ( String.hashCode () ):

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

Czy są jakieś okoliczności (np. Wersja maszyny JVM, dostawca itp.), W których poniższe wyrażenie zostanie uznane za fałszywe?

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

Aktualizacja nr 1: Jeśli twierdzisz, że odpowiedź brzmi „tak, istnieją takie okoliczności” - podaj konkretny przykład, kiedy „To jest ciąg języka Java” .hashCode ()! = 586653468. Spróbuj być tak konkretny / konkretny jak to możliwe.

Aktualizacja # 2: Wszyscy wiemy, że poleganie na szczegółach implementacji funkcji hashCode () jest ogólnie złe. Jednak mówię konkretnie o String.hashCode () - więc proszę, skup się na odpowiedzi na String.hashCode (). Object.hashCode () jest całkowicie nieistotna w kontekście tego pytania.

Widzę tę dokumentację od czasów Java 1.2.

Chociaż prawdą jest, że generalnie nie powinieneś polegać na tym, że implementacja kodu skrótu pozostanie taka sama, jest to teraz udokumentowane zachowanie java.lang.String, więc zmiana będzie liczyła się jako zerwanie istniejących kontraktów.

O ile to możliwe, nie należy polegać na kody hash pobytu takie same w całej wersji itp - ale w moim umyśle java.lang.Stringjest szczególnym przypadkiem po prostu dlatego, że algorytm nie został określony ... tak długo, jak jesteś gotów porzucić zgodność z wersjami przed złożeniem oczywiście określono algorytm.

Znalazłem coś o JDK 1.0 i 1.1 i> = 1.2:

W JDK 1.0.x i 1.1.x funkcja hashCode dla długich ciągów działała na zasadzie próbkowania każdego n-tego znaku. To całkiem dobrze gwarantuje, że będziesz miał wiele ciągów haszujących do tej samej wartości, co spowolni wyszukiwanie Hashtable. W JDK 1.2 ulepszono funkcję polegającą na pomnożeniu wyniku przez 31, a następnie dodaniu kolejnego znaku w kolejności. Jest to trochę wolniejsze, ale znacznie lepsze w unikaniu kolizji. Źródło: http://mindprod.com/jgloss/hashcode.html

Coś innego, ponieważ wydaje się, że potrzebujesz numeru: Co powiesz na używanie CRC32 lub MD5 zamiast kodu skrótu i ​​jesteś gotowy - żadnych dyskusji i żadnych zmartwień ...

Nie należy polegać na tym, że kod skrótu jest równy określonej wartości. Po prostu zwróci spójne wyniki w ramach tego samego wykonania. Dokumentacja API zawiera następujące informacje:

Ogólna umowa dotycząca hashCode to:

• Za każdym razem, gdy jest wywoływana na tym samym obiekcie więcej niż jeden raz podczas wykonywania aplikacji Java, metoda hashCode musi konsekwentnie zwracać tę samą liczbę całkowitą, pod warunkiem, że żadne informacje użyte w porównaniach równości na obiekcie nie zostaną zmodyfikowane. Ta liczba całkowita nie musi pozostawać spójna od jednego wykonania aplikacji do innego wykonania tej samej aplikacji.

EDYCJA Ponieważ javadoc dla String.hashCode () określa, w jaki sposób obliczany jest kod skrótu String, każde naruszenie tego stanowiłoby naruszenie specyfikacji publicznego API.

Jak wspomniano powyżej, generalnie nie należy polegać na kodzie skrótu klasy, który pozostaje taki sam. Należy pamiętać, że nawet kolejne uruchomienia tej samej aplikacji na tej samej maszynie wirtualnej mogą generować różne wartości skrótu. AFAIK funkcja skrótu Sun JVM oblicza ten sam skrót przy każdym uruchomieniu, ale nie jest to gwarantowane.

Zauważ, że nie jest to teoretyczne. Funkcja skrótu dla java.lang.String została zmieniona w JDK1.2 (stary hash miał problemy z ciągami hierarchicznymi, takimi jak adresy URL lub nazwy plików, ponieważ miał tendencję do tworzenia tego samego skrótu dla łańcuchów, które różniły się tylko na końcu).

java.lang.String to szczególny przypadek, ponieważ algorytm jego hashCode () jest (teraz) udokumentowany, więc prawdopodobnie możesz na tym polegać. Nadal uważam to za złą praktykę. Jeśli potrzebujesz algorytmu haszującego ze specjalnymi, udokumentowanymi właściwościami, napisz go :-).

Kolejną (!) Kwestią, o którą należy się martwić, jest możliwa zmiana implementacji między wczesnymi a późnymi wersjami Javy. Nie wierzę, że szczegóły implementacji są nieodwracalne, więc potencjalnie aktualizacja do przyszłej wersji Java może spowodować problemy.

Podsumowując, nie polegałbym na implementacji hashCode().

Być może możesz wskazać problem, który faktycznie próbujesz rozwiązać za pomocą tego mechanizmu, a to podkreśli bardziej odpowiednie podejście.

Wystarczy odpowiedzieć na Twoje pytanie i nie kontynuować dyskusji. Wydaje się, że implementacja Apache Harmony JDK używa innego algorytmu, przynajmniej wygląda zupełnie inaczej:

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

Zapraszam do samodzielnego sprawdzenia ...

Jeśli martwisz się zmianami i prawdopodobnie niekompatybilnymi maszynami wirtualnymi, po prostu skopiuj istniejącą implementację kodu skrótu do własnej klasy narzędziowej i użyj jej do wygenerowania kodów skrótów.

Kod skrótu zostanie obliczony na podstawie wartości ASCII znaków w łańcuchu.

Oto implementacja w klasie String

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

Kolizje w hashcode są nieuniknione. Na przykład ciągi „Ea” i „FB” dają ten sam kod skrótu co 2236