Zły pomysł, aby użyć klucza String w HashMap?

Programiści nie muszą zajmować się problemem kolizji hash w Hashmapie, aby uzyskać poprawność programu.

Jest tu kilka kluczowych rzeczy do zrozumienia:

Kolizje są nieodłączną cechą haszowania i muszą być. Liczba możliwych wartości (łańcuchów w Twoim przypadku, ale dotyczy również innych typów) jest znacznie większa niż zakres liczb całkowitych.
1. każde użycie hashingu ma sposób na kolizji, a Kolekcje Javy (w tym HashMap) nie są wyjątkiem.

2. hashowanie nie bierze udziału w testowaniu równości. Prawdą jest, że równe obiekty muszą mieć równe hashcody, ale odwrotność nie jest prawdziwa: wiele wartości będzie miało ten sam hashcode. Więc nie próbuj używać porównania hashcode jako substytutu równości. Kolekcje nie. używają hashowania, aby wybrać podzbiory (zwane bucketem w świecie kolekcji Java), ale używają .equals () to actually check dla równości.

3. nie tylko nie musisz się martwić o kolizje powodujące błędne wyniki w kolekcji, ale w większości aplikacji również * zwykle * nie musisz się martwić o wydajność-zbiory zaszyfrowane w Javie świetnie radzą sobie z zarządzaniem hashcodami.

4. Jeszcze lepiej, w przypadku, o którym pytałeś (ciągi jako klucze), nie musisz nawet martwić się o same hashcody, ponieważ Klasa String Javy generuje całkiem dobry hashcode. Podobnie jak większość dostarczonych klas Javy.

Trochę więcej szczegółów, jeśli chcesz:

Sposób, w jaki działa haszowanie (w szczególności w przypadku haszowanych kolekcji, takich jak HashMap Java, o co pytałeś) jest następujący:

• HashMap przechowuje podane wartości w kolekcji podzbiorów, zwanych buckets. Są one faktycznie realizowane jako listy połączone. Jest ich ograniczona liczba: iirc, domyślnie 16, A Liczba zwiększa się w miarę umieszczania kolejnych przedmiotów na mapie. Zawsze powinno być więcej wiader niż wartości. Aby podać jeden przykład, używając domyślnych wartości, jeśli dodasz 100 wpisów do Hashmapy, będzie 256 wiadrów.

• Każda wartość, która może być użyta jako klucz na mapie, musi być w stanie wygenerować wartość całkowitą, zwaną hashcode.

• HashMap używa tego hashcode, aby wybrać wiadro. Ostatecznie oznacza to przyjęcie wartości całkowitej modulo Liczby kubełków, ale wcześniej HashMap w Javie ma wewnętrzną metodę (o nazwie hash()), która poprawia hashcode, aby zmniejszyć niektóre znane źródła zlepiania.

• Podczas wyszukiwania wartości, HashMap wybiera wiadro, a następnie wyszukuje pojedynczy element za pomocą wyszukiwania liniowego połączonej listy, używając .equals().

Więc: nie musisz obejść kolizji dla poprawności i zwykle nie musisz się o nie martwić dla wydajności, a jeśli używasz natywnej Javy klasy (jak String), nie musisz się też martwić o generowanie wartości hashcode.

W przypadku, gdy musisz napisać własną metodę hashcode (co oznacza, że napisałeś klasę z wartością złożoną, jak para imię/nazwisko), sprawy stają się nieco bardziej skomplikowane. Jest całkiem możliwe, aby się pomylić tutaj, ale to nie jest rocket science. Po pierwsze, wiedz jedno: jedyną rzeczą, którą musisz zrobić, aby zapewnić poprawność, jest zapewnienie, że równe obiekty dają równe hashcodes. Więc jeśli piszesz metodę hashcode () dla swojej klasy, musisz również napisać metodę equals() i musisz sprawdzić te same wartości w każdej z nich.

Możliwe jest napisanie metody hashcode (), która jest zła, ale poprawna, przez co mam na myśli, że spełniałaby ograniczenie "równe obiekty muszą dawać równe hashcody" , ale nadal działa bardzo słabo, przez wiele kolizji.

Kanonicznym zwyrodnieniem byłoby napisanie metody, która po prostu zwraca wartość stała (np. 3) dla wszystkich przypadków. Oznaczałoby to, że każda wartość byłaby zahaszowana w tym samym koszyku.

To nadal działa , ale wydajność pogorszyłaby się do tej z połączonej listy.

Oczywiście nie napiszesz tak strasznej metody hashcode (). Jeśli używasz przyzwoitego IDE, jest w stanie wygenerować go dla Ciebie. Ponieważ StackOverflow kocha kod, oto kod dla klasy firstname/lastname powyżej.

public class SimpleName {
    private String firstName;
    private String lastName;
    public SimpleName(String firstName, String lastName) {
        super();
        this.firstName = firstName;
        this.lastName = lastName;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result
                + ((firstName == null) ? 0 : firstName.hashCode());
        result = prime * result
                + ((lastName == null) ? 0 : lastName.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SimpleName other = (SimpleName) obj;
        if (firstName == null) {
            if (other.firstName != null)
                return false;
        } else if (!firstName.equals(other.firstName))
            return false;
        if (lastName == null) {
            if (other.lastName != null)
                return false;
        } else if (!lastName.equals(other.lastName))
            return false;
        return true;
    }
}