Niemutowalny klucz w mapie, jakie korzyści?

Witam. Ostatnio zastanawiam się jakie korzyści daje nam niemutowalność klucza w mapie. Wszędzie zaleca się aby klucz w mapie był niemutowalny, aby ustrzec się przed błędami. Napisałem taki prosty programik:

class HashKey {

    private int keyPartOne;
    private int KeyPartTwo;

    public HashKey(int keyPartOne, int keyPartTwo) {
        this.keyPartOne = keyPartOne;
        KeyPartTwo = keyPartTwo;
    }

    public int getKeyPartOne() {
        return keyPartOne;
    }

    public void setKeyPartOne(int keyPartOne) {
        this.keyPartOne = keyPartOne;
    }

    public int getKeyPartTwo() {
        return KeyPartTwo;
    }

    public void setKeyPartTwo(int keyPartTwo) {
        KeyPartTwo = keyPartTwo;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        HashKey hashKey = (HashKey) o;

        if (keyPartOne != hashKey.keyPartOne) return false;
        return KeyPartTwo == hashKey.KeyPartTwo;
    }

    @Override
    public int hashCode() {
        int result = keyPartOne;
        result = 31 * result + KeyPartTwo;
        return result;
    }
}

public class Main {

    public static void main(String[] args) {
        HashMap<HashKey, String> firstMap = new HashMap<>();
        HashKey firstHashKey = new HashKey(1, 1);
        firstMap.put(firstHashKey, "text 1");
        HashKey secondHashKey = new HashKey(1, 2);
        firstMap.put(secondHashKey, "text 2");
        System.out.println(firstMap.get(firstHashKey));
        secondHashKey.setKeyPartTwo(1);
        System.out.println(firstMap.get(secondHashKey));

        HashMap<String, String> secondMap = new HashMap<>();
        String firstMapElem = "firstKey";
        secondMap.put(firstMapElem, "string 1");
        String secondMapElem = "secondKey";
        secondMap.put(secondMapElem, "string 2");
        System.out.println(secondMap.get(firstMapElem));
        secondMapElem = "firstKey";
        System.out.println(secondMap.get(secondMapElem));
    }
}

Jak widać w pierwszym przypadku korzystam z mutowalnego klucza w mapie, czyli obiektu utworzonego przeze mnie na potrzeby przykładu: HashKey. Tworze sobie dwa obiekty, jeden z parametrami 1,1 i tekstem "text 1" a drugi z 1,2 i tekstem "text 2". Wynik uruchomiania programu daje mi:

text 1
text 1

Ponieważ w międzyczasie przed wypisaniem zmodyfikowałem drugi klucz:

HashKey secondHashKey = new HashKey(1, 2);

W drugim przykładzie robię podobnie z tym, że korzystam z niemutowalnego Stringa i dostaję wyniki:

string 1
string 1

W międzyczasie dokonałem przypisania:

secondHashKey.setKeyPartTwo(1);

I tutaj moje pytanie jaką mamy tutaj faktycznie korzyść z niemutowalności tych obiektów? W obu przypadkach możemy zmodyfikować zmienną, którą użyjemy potem do pobrania wartośći z mapy. Jaką robi to nam różnicę czy zrobimy set na mutowalnym obiekcie:

 secondMap.put(firstMapElem, "string 1");

czy przypisanie na niemutowalnym stringu:

secondMapElem = "firstKey";

Swoją drogą podobnie można by zrobić jak ze Stringiem jeśli obiekt HashMapKey byłby niemutowalny.

Jaką mamy tutaj korzyść z niemutowalności obiektu skoro wartość zmiennej możemy tak czy inaczej zmodyfikować, czy to przez przypisane nowego obiektu, czy set na mutowalnym obiekcie. Jedyne co mi przychodzi do głowy to to, że przypisanie jawnie nam pokazuje w kodzie, że mamy do czynienia z nowym obiektem klucza, a set robi to w trudniejszy do wychwycenia sposób i przez to łatwiej o późniejsze błędy. Czy mógłby mi ktoś wyjaśnić czy dobrze rozumuję i jakie są prawdziwe zalety takiego niemutowalnego klucza?

Korzyści z immutable key to np. ten sam hashcode
http://javarevisited.blogspot.sg/2011/02/how-hashmap-works-in-java.html

Złamanie kontraktu mapy spowoduje jej błędne działanie. Chyba potrafię to pokazać w ten sposób:

    secondHashKey.setKeyPartTwo(3);
    HashKey newKey = new HashKey(1, 3);
    System.out.println("new: " + firstMap.get(newKey));

W mapie mamy obiekt (1,3), bo jest to secondHashKey. Jednak haszmapa go nie znajdzie. Ma w pamięci poprzedni hashcode. Program wypisze null.

Widać, że ogólnie mapa działa dobrze, bo poniższy fragment znajdzie element:

    newKey.setKeyPartTwo(1);
    System.out.println("new 1: " + firstMap.get(newKey));

Typowe użycie mapy jest takie, że klucze są tworzone od nowa bądź wydobywane z różnych miejsc. W twoim przykładzie popsułeś drugi klucz. Spróbuj go teraz stworzyć od nowa i znaleźć odpowiadającą mu wartość w mapie - raczej nie znajdziesz.

import java.util.HashMap;
import java.util.Map;

public class HashMapTest {
    static class Key {
        int value;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Key key = (Key) o;
            return value == key.value;
        }

        @Override
        public int hashCode() {
            return value;
        }
    }


    public static void main(String[] args) {
        Key key1 = new Key();
        key1.value = 1;

        Map<Key, String> mapa = new HashMap<>();
        mapa.put(key1, "hello");
        System.out.println(mapa.get(key1));
        key1.value = 2; // teraz oba klucze mają value == 2
        Key key2 = new Key();
        key2.value = 2;
        System.out.println(mapa.get(key2));
    }
}

Ten kod wypisuje:

hello
null

Mapa nie znajduje więc klucza w drugim szukaniu mimo iż oba klucze mają taką samą wartość hashCode.

Dlaczego? Wytłumaczenie zależy od rodzaju HashMapy.
Zakładając, że HashMapa używa metody łańcuchowej to sprawa jest taka, że klucz przy wrzucaniu do HashMapy ląduje w jednej liście, a potem jest szukany w innej. Jest tak dlatego, że to która lista będzie przeszukiwana zależy od hashCode.
Zakładając, że HashMapa używa adresowania otwartego to sprawa jest taka, że przy wrzucaniu element wylądował na jednej pozycji, a szukanie zaczynamy od innej pozycji i szybko przerywamy, bo trafiamy na puste elementy tablicy. Przeszukiwane pozycje zależą od hashCode.

W przypadku TreeMapy klucz także musi być niemutowalny, gdyż TreeMapa to posortowane drzewo. Sortowanie odbywa się w momencie wrzucania elementu do drzewa. Jeśli zmienisz wartość elementu to drzewo nagle stanie się nieposortowane, a TreeMapa nie będzie o tym wiedzieć i zacznie się po prostu źle zachowywać - nie będzie znajdować części elementów.

@olek1 to porównaj sobie swoją klasę w wersji niemutowalnej

public final class ImmutableKey {

        private final int keyPartOne;
        private final int KeyPartTwo;

        public ImmutableKey(int keyPartOne, int keyPartTwo) {
            this.keyPartOne = keyPartOne;
            KeyPartTwo = keyPartTwo;

//cd... settery wywalone
        }

co sprawi , że ustawienie secondHashKey.setKeyPartTwo(1); będzie po prostu niemożliwe - to zabezpiecza przed przypadkową zmianą wartości klucza - i dobrze bo to klucz - nie powinien się zmieniać.

Ok @Wibowit dzięki za odpowiedź mam jeszcze jedno pytanie. Załóżmy, że przerobiłem swój przykład:

        HashMap<HashKey, String> firstMap = new HashMap<>();
        HashKey firstHashKey = new HashKey(1, 1);
        firstMap.put(firstHashKey, "text 1");
        HashKey secondHashKey = new HashKey(1, 2);
        firstMap.put(secondHashKey, "text 2");
        System.out.println(firstMap.get(firstHashKey));
        secondHashKey.setKeyPartTwo(3);
        System.out.println(firstMap.get(secondHashKey));
        System.out.println(firstMap.get(new HashKey(1, 2)));

Na wyjściu dostaję:

text 1
null
null

Oznacza to, że wartość "text2" została dodana do kubełka z hashem dla kombinacji wartości 1,2. Potem zmieniamy wartość klucza secondHashKey i jego hashCode to kombinacja 1,3.
Przy próbie pobrania

firstMap.get(secondHashKey));

Szukamy kubełka dla kombinacji 1,3 i nie znajdujemy nic bo "text2" znajduje się pod kubełkiem z kombinacją 1,2 i dlatego dostajemy null.

Przy drugim wywołaniu:

firstMap.get(new HashKey(1, 2));

Szukamy kubełka dla kombinacji 1,2 i znajdujemy tam jeden element, ale hashCode tego elementu jest dla kombinacji 1,3 i zwracany jest null, ponieważ hash obiektu jest niezgodny z kubełkiem, w którym się on znajduje.
Tutaj moje pytanie czy w momencie próby wyszukania kubełka dla kombinacji 1,2 i znalezienia elementu nie powinien on nam go od razu zwrócić, jeśli jest on jedynym elementem w liście? Z zachowania programu wynika, że przy wyszukaniu kubełka i znalezieniu elementu sprawdza on jeszcze dodatkowo po raz kolejny wartość hashCode tego elementu. Czy dobrze rozumuję? Sorry za używanie określenia "kubełek" nie wiem czy ono jest poprawne ale nie chciałem pisać lista lista bo by się mogło pomieszać.

HashMapa z Javy zawiera taki komentarz:

* Implementation notes. * * This map usually acts as a binned (bucketed) hash table, but * when bins get too large, they are transformed into bins of * TreeNodes, each structured similarly to those in * java.util.TreeMap. Most methods try to use normal bins, but * relay to TreeNode methods when applicable (simply by checking * instanceof a node). Bins of TreeNodes may be traversed and * used like any others, but additionally support faster lookup * when overpopulated. However, since the vast majority of bins in * normal use are not overpopulated, checking for existence of * tree bins may be delayed in the course of table methods. * * Tree bins (i.e., bins whose elements are all TreeNodes) are * ordered primarily by hashCode, but in the case of ties, if two * elements are of the same "class C implements Comparable<c>", * type then their compareTo method is used for ordering. (We * conservatively check generic types via reflection to validate * this -- see method comparableClassFor). The added complexity * of tree bins is worthwhile in providing worst-case O(log n) * operations when keys either have distinct hashes or are * orderable, Thus, performance degrades gracefully under * accidental or malicious usages in which hashCode() methods * return values that are poorly distributed, as well as those in * which many keys share a hashCode, so long as they are also * Comparable. (If neither of these apply, we may waste about a * factor of two in time and space compared to taking no * precautions. But the only known cases stem from poor user * programming practices that are already so slow that this makes * little difference.)

Można więc w sumie użyć określenia kubełek. Da się też zauważyć, że HashMapa Javowa może tworzyć w środku TreeMapy korzystające z compareTo z interfejsu Comparable.

Tutaj moje pytanie czy w momencie próby wyszukania kubełka dla kombinacji 1,2 i znalezienia elementu nie powinien on nam go od razu zwrócić, jeśli jest on jedynym elementem w liście? Z zachowania programu wynika, że przy wyszukaniu kubełka i znalezieniu elementu sprawdza on jeszcze dodatkowo po raz kolejny wartość hashCode tego elementu. Czy dobrze rozumuję?

hashCode jest wykorzystywany do wyboru kubełka/ listy. Do znalezienia elementu w kubełku/ liście wykorzystywany jest przede wszystkim equals - aczkolwiek przy przepełnionych kubełkach może być wykorzystywany hashCode oraz compareTo jeżeli element implementuje interfejs Comparable.

Equals jest wykonywany zawsze - nie ma znaczenia rozmiar kubełka. Możesz przecież najpierw wstawić klucz A o hashCode == 1, a potem szukać klucza B (innego od A), który też ma hashCode == 1.

TL;DR

Nie chodzi o to żeby "ustrzec się przed błędami". To nie są jakieś "potencjalne błędy" tylko konkretne i realne.

Pierwszy przykład który podałeś to właśnie dowód na to jak łatwo zrobić błąd.
Mapa zawiera dwa elementy, ale Ty już możesz dostać się przez klucz tylko do jednego.

Jeśli zrobisz taki main do swojego HashKey:

public static void main (String[] args) throws java.lang.Exception
{
        HashMap<HashKey, String> firstMap = new HashMap<>();
        HashKey firstHashKey = new HashKey(1, 1);
        firstMap.put(firstHashKey, "text 1");
        HashKey secondHashKey = new HashKey(1, 2);
        firstMap.put(secondHashKey, "text 2");
        System.out.println(firstMap.get(firstHashKey));
        secondHashKey.setKeyPartTwo(1);
        System.out.println(firstMap.get(secondHashKey));
        
        System.out.printf("Map size: %d%n", firstMap.size());
        System.out.printf("First entry value: %s%n", firstMap.get(new HashKey(1, 1)));
        System.out.printf("Second entry value: %s%n", firstMap.get(new HashKey(1, 2)));
        
        for(Map.Entry<HashKey, String> entry: firstMap.entrySet()) {
        	System.out.printf("Key: %s, value: %s%n", entry.getKey(), entry.getValue());
        }
}

To dostaniesz:

text 1
text 1
Map size: 2
First entry value: text 1
Second entry value: null
Key: HashKey@20, value: text 1
Key: HashKey@20, value: text 2

http://ideone.com/pynBzV

Drugi przykład jest poprawny, ponieważ nie zmieniłeś obiektu klucza - po prostu używasz innego do pobrania wartości.

Patrz tutaj:
http://www.java-fries.com/2014/09/mutable-keys-in-hashmap-dangerous-practice/

Kontrakt na hashCode:

1. Jeżeli hash(o1) != hasho(o2) => na pewno o1 != o2
2. Jeżeli hash(o1) == hash(o2) => duża szansa, że o1 == o2, ale pewności nie ma

W niektórych zastosowaniach funkcji mieszającej uznaje się, że prawdopodobieństwo jest wystarczająco duże, żeby uznać równość obiektów za pewnik, ale nie tutaj. Ktoś oszacował, że przy dobrej funkcji mieszającej prawdopodobieństwo kolizji klucza jest takie jak to, że trafi Cię meteoryt. Ale to było przed deszczem w Czelabińsku :)