Listopad 7, 2018

10 faktów o HashMapie, które musi znać każdy Java developer

HashMap…

…w ostatnim artykule pisałem o tym jak korzystać z interfejsu Map w Javie przy użyciu implementacji HashMapy. Ze względu, że jest to najczęściej wykorzystywana implementacja mapy – z pewnością na samym początku przygody z programowaniem – to przyjrzymy się jej bliżej. Pokażę Ci 10 faktów dotyczących HashMapy, o których powinien wiedzieć każdy Java Developer.

1. Immutable keys

Niezmienialne klucze – wspominałem już trochę o tym. Tym razem wytłumaczę czemu to jest takie ważne.

Dodając nowy obiekt do mapy na początku każdy klucz jest hashowany przy użyciu metody hashCode, na podstawie tego hashu wrzucany jest do odpowiedniego wiaderka (bucket) i tam właśnie zajmuje swoje miejsce.

Założmy, że zmienimy lekko wartość naszego klucza, co wtedy?

Hash obiektu zmieni się co prawdopodobnie wiąże się również ze zmianą wiaderka w mapie – teoretycznie, w końcu mapa nic o tym nie wie.

Przeanalizujmy przykład, przygotujmy sobie klasę na klucz:

package pl.maniaq;

import java.util.Objects;

public class Key {
    private long id;

    public Key(long id) {
        this.id = id;
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

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

    @Override
    public int hashCode() {

        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Key{" +
                "id=" + id +
                '}';
    }
}

Oraz klasę Usera:

package pl.maniaq;

public class User {
    private String login;

    public User(String login) {
        this.login = login;
    }

    @Override
    public String toString() {
        return "User{" +
                "login='" + login + '\'' +
                '}';
    }

    public String getLogin() {
        return login;
    }

    public void setLogin(String login) {
        this.login = login;
    }
}

Stwórzmy sobie na początek dwa klucze oraz dwóch userów, dwie mapy i dodajmy do niej te dwie pary.

User user1 = new User("Pablo");
User user2 = new User("Ugot");

Key key1 = new Key(1);
Key key2 = new Key(2);

Map<Key, User> users = new HashMap<>();
users.put(key1, user1);
users.put(key2, user2);

Następnie sprawdźmy jak zachowa się mapa po zmianie klucza:

System.out.println("Przed zmiana - klucz: " + key1 + ", user: " + users.get(key1));
key1.setId(3);
System.out.println("Po zmianie - klucz: " + key1 + ", user: " + users.get(key1));
Przed zmiana - klucz: Key{id=1}, user: User{login='Pablo'}
Po zmianie - klucz: Key{id=3}, user: null

Niestety przez to, że hash obiektu key1 się zmienił to mapa nie może znależć żadnego obiektu przypisanego do tego obiektu.

Wniosek jest prosty: klucz musi być obiektem immutable – więcej o immutable napiszę w innym artykule.

2. Unikalne klucze

Wielokrotne użycie metody put z istniejącym kluczem powoduje nadpisanie poprzedniej wartości.

Map<Long, String> names = new HashMap<>();
names.put(1l, "Kamil");

System.out.println("Mapa przed nadpisaniem: " + names);

names.put(1l, "Pablo");
System.out.println("Mapa po nadpisaniu: " + names);

I po uruchomieniu otrzymamy:

Mapa przed nadpisaniem: {1=Kamil}
Mapa po nadpisaniu: {1=Pablo}

Wniosek jest prosty: klucze w mapie są unikalne!

3. Wielowątkowość

Wielowątkowość jest dosyć specyficznym i skomplikowanym tematem, nie ma co się w nią zagłębiać w tym artykule. Warto wspomnieć o jednej ważnej rzeczy – nie używaj HashMapy w aplikacjach wielowątkowych.

Najlepiej skorzystać m.in z implementacji ConcurrentHashMap:

Map<String, String> countries = new ConcurrentHashMap<>();
countries.put("PL", "Poland");
countries.put("FR", "France");
countries.put("IT", "Italy");
System.out.println("Concurrent map: " + countries);

4. Enum

Jak wiesz enum jest klasą, a jego obiekty są singletonami – skoro są obiektami to mogą być używane w typach generycznych. Co powoduje, że mogą zostać również kluczami mapy.

Mając taki enum:

package pl.maniaq;

public enum Color {
    BLUE, RED, GREEN;
}

Tworzymy mapę na kolory:

Map<Color, String> colors = new HashMap<>();
colors.put(Color.BLUE, "niebieski");

I choć jest to prawidłowe rozwiązanie to lepiej skorzystać z dedykowanej do tego implementacji – EnumMap, którą można zainicjalizować i użyć w ten sposób:

Map<Color, String> enumColors = new EnumMap<>(Color.class);
enumColors.put(Color.RED, "czerwony");

Jako konstruktor podajemy nazwę klasę enuma.

5. Mapa list

Często trzeba wykorzystać mapę nie tylko do przechowywanie pojedyńczych obiektów, ale całych kolekcji np. mapa list. Nie jest to problemem, w końcu każda kolekcja jest obiektem jak każdy inny element, który dodawaliśmy wcześniej.

Stwórzmy sobie dwie listy osób studiujących konkretny kierunek oraz mapę, w której będziemy przechowywać listy:

List<String> mathStudents = new LinkedList<>(Arrays.asList("Pablo", "Escabo"));
List<String> physStudents = new LinkedList<>(Arrays.asList("Horty", "Tero", "Pelo"));

Map<String, List<String>> university = new HashMap<>();

I dodajmy obie listy do mapy:

university.put("Matematyka", mathStudents);
university.put("Fizyka", physStudents);

Jak widać wszystko działa poprawnie. 😉

6. Iterowanie po mapie

Iterować po mapie można na pewno na dwa sposoby – możliwe, że znasz jeszcze jakiś inny. 😉

Pierwszy przykład jest tzw. anty-wzorcem, czyli nie rób tak:

for(String key : countries.keySet()) {
    System.out.println("Key: " + key + ", value: " + countries.get(key));
}

Na początku wyciągamy zbiór kluczy i dopiero na podstawie kluczy wyciągamy obiekt. Nie rób tak, po co tyle zbędnych operacji?

Nie lepiej wszystko zrobić za jednym zamachem?

for(Map.Entry<String, String> entry : countries.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", value: " + entry.getValue());
}

Oczywiście drugie rozwiązanie jest lepsze i czytelniejsze. 😉

7. LoadFactory

W implementacji mapy znajdziemy takie pole jak loadFactory:

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

Które jest inicjalizowane podczas tworzenia mapy na wartość 0.75 – co to oznacza?

Oznacza to jeśli mapa zostanie zapełniona w 75% to zostanie utworzona nowa mapa, do której będą przekopiowane elementy.

8. Powiększanie mapy

Mapa niestety co jakiś czas musi się powiększać, w końcu na początku mapa może pomieścić maksymalnie 16 elementów. Mapa za każdy razem, gdy osiągnie określony loadFactory zostaje utworzona nowa mapa dwukrotnie większa od poprzedniej.

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold

Nie pamiętam czemu, ale podobno dwukrotne zwiększanie rozmiaru struktury jest często stosowane w przeróżnych językach programowania. Tak po prostu jest optymalnie. 😉

9. Kolejność elementów

Czasami potrzebujemy przechowywać dane w kolejności w jakiej zostały dodane. Dlatego trzeba pamiętać, że HashMapa nie oferuje nam takiej możliwości.

Zróbmy mały test, niech kluczem będzie chociażby User – nie może to być obiekt np. Long, który składa się z prymitywu, ponieważ nie zauważymy tego błędu.

Map<User, Integer> orderMap = new HashMap<>();
for(int i=0;i<20;i++) {
    orderMap.put(new User("Test" + String.valueOf(i)), i);
}

System.out.println("Order map: " + orderMap);

Spórz, że do mapy dodałem elementy od do 20 o kluczach od Test0 do Test20 – oznacza, to że standardowy rozmiar mapy (16) został już przekroczony, dlatego mapa „pod spodem” została przekopiowana do nowej mapy”

Rezultat działania takiego programu możemy zaobserwować tutaj:

Order map: {User{login='Test18'}=18, User{login='Test7'}=7, User{login='Test10'}=10, User{login='Test14'}=14, User{login='Test6'}=6, User{login='Test19'}=19, User{login='Test5'}=5, User{login='Test16'}=16, User{login='Test1'}=1, User{login='Test4'}=4, User{login='Test17'}=17, User{login='Test8'}=8, User{login='Test3'}=3, User{login='Test11'}=11, User{login='Test9'}=9, User{login='Test13'}=13, User{login='Test0'}=0, User{login='Test12'}=12, User{login='Test15'}=15, User{login='Test2'}=2}

Spójrz, że liczby nie są w odpowiedniej kolejności.

Jeśli zależy Ci kolejności dodawanych elementów to możesz skorzystać z LinkedHashMap.

10. Kolizje

Ze względu, że mapa operuje na kategoryzowaniu obiektu na podstawie hashCode to powoduje to występowanie konfliktów. Do tego samego obiektu może trafić wiele obiektów, a nawet wszystkie – jeśli metoda hashCode w obiekcie jest stworzona źle np. zwraca zawsze tą samą wartość.

Jak hashMap radzi sobie z kolizjami?

Na podstawie hashu znajduje odpowiedni bucket, jeśli jest tam jeden element to go zwraca – w przeciwnym wypadku wyszukuje odpowiedniego elementu przy użyciu metody equals, która sprawdza element po elemencie czy obiekty są sobie równe. Jeśli equals zwróci true to po prostu oznacza, że obiekt został odnaleziony. 😉

Wniosek: implementuj metody equals i hashCode dla swoich klas używanych w kolekcjach.

Podsumowanie

Jak widać jest sporo rzeczy, o których warto wiedzieć podczas korzystania z hashMap. O ile niektóre zagadnienia możemy traktować jako ciekawostki lub świadomie modyfikować – o ile takie jak: immutable keys, konflikty lub kolejność elementów powinny być znane każdemu programiście. 😉

Kod używany podczas artykułu możesz znaleźć tutaj.