Java Academy · Lekcja

Jak działa HashMap

Koszyki, haszowanie i kolizje

Jak działa HashMap to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.

Co przechowuje HashMap

Obiekt HashMap przechowuje pary klucz–wartość i zapewnia średnio operacje wyszukiwania, wstawiania oraz usuwania o złożoności O(1).

Wewnętrznie przechowuje tablicę nazywaną table. Każdy element tej tablicy nazywa się bucketem.

Klucz decyduje, do którego bucketa trafi wpis.
Wartość jest tym, co zostaje zwrócone podczas wyszukiwania klucza.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Haszowanie klucza

Podczas wywołania put(key, value) mapa wywołuje key.hashCode(), aby uzyskać wartość typu int.

Następnie HashMap rozprasza te bity za pomocą wewnętrznej funkcji, dzięki czemu nawet słabe kody haszujące są rozprowadzane po bucketach.

Końcowa liczba jest redukowana za pomocą hash & (table.length - 1), aby uzyskać indeks bucketa.
Długość tablicy jest zawsze potęgą dwójki, dlatego maska działa poprawnie.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Buckety w działaniu

Każdy bucket może przechowywać więcej niż jeden wpis. Gdy dwa klucze wskazują ten sam bucket, występuje kolizja.

Kolizje są normalne i oczekiwane. HashMap obsługuje je, łącząc wpisy w łańcuch w obrębie bucketa.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Kolizje i łańcuchy

Przed Javą 8 wszystkie kolidujące wpisy znajdowały się na jednokierunkowej liście wiązanej wewnątrz bucketa.

Wyszukiwanie przechodzi po liście i wywołuje equals(), aż znajdzie pasujący klucz.

Niewiele kolizji: złożoność nadal jest efektywnie równa O(1).
Wiele kolizji w jednym buckecie: złożoność dla tego bucketa zbliża się do O(n).

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Dlaczego FB i Ea kolidują

Napisy "FB" i "Ea" mają w Javie tę samą wartość hashCode(). To klasyczny przykład kolizji.

Nawet przy identycznych kodach haszujących mapa nadal przechowuje je osobno, ponieważ metoda equals() rozróżnia je wewnątrz bucketa.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Współczynnik zapełnienia

Współczynnik zapełnienia określa, jak bardzo może zapełnić się tablica, zanim zostanie powiększona. Wartość domyślna to 0.75.

Pojemność 16 i współczynnik zapełnienia 0.75 oznaczają zmianę rozmiaru po osiągnięciu 12 wpisów.
Niższy współczynnik zapełnienia marnuje pamięć, ale ogranicza liczbę kolizji.
Wyższy współczynnik zapełnienia oszczędza pamięć, ale zwiększa liczbę kolizji.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Zmiana rozmiaru tablicy

Gdy liczba wpisów przekroczy wartość capacity * loadFactor, rozmiar tablicy podwaja się.

Każdy istniejący wpis jest ponownie haszowany i umieszczany w nowej, większej tablicy. Jest to kosztowna operacja, dlatego w przypadku dużych map ważne jest wcześniejsze określenie rozmiaru.

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

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Wstępne określanie rozmiaru na potrzeby wydajności

Jeśli znają Państwo przybliżoną liczbę przechowywanych wpisów, proszę podać początkową pojemność, aby uniknąć wielokrotnych zmian rozmiaru.

Praktyczna zasada: początkowa pojemność = expectedSize / 0.75 + 1.

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

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Klucze i wartości null

HashMap dopuszcza jeden klucz null i wiele wartości null.

Klucz null zawsze trafia do bucketa 0 (jego wartość haszująca jest traktowana jako 0).
Proszę użyć getOrDefault, aby uniknąć niejednoznaczności między brakującym kluczem a wartością null.

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

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

Kolejność iteracji nie jest gwarantowana

HashMap nie gwarantuje kolejności iteracji. Kolejność zależy od kodów haszujących i układu bucketów.

Jeśli potrzebują Państwo przewidywalnej kolejności, proszę użyć LinkedHashMap (kolejność wstawiania) lub TreeMap (kolejność sortowania).

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Podsumowanie ścieżki get()

Wyszukiwanie przebiega w następujących krokach:

Obliczenie hashCode() i rozproszenie bitów.
Użycie maski w celu znalezienia indeksu kubełka.
Przejście przez kubełek i porównanie kluczy za pomocą equals().
Zwrócenie pasującej wartości albo null.

Dobry hashCode oraz poprawny equals sprawiają, że każdy krok jest szybki.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Szybkie sprawdzenie

Proszę sprawdzić swoją wiedzę o tym, jak HashMap znajduje kubełek.

Podsumowanie

Poznali Państwo sposób działania HashMap od wewnątrz:

Klucze są haszowane i przypisywane do kubełków.
Kolizje są obsługiwane przez łańcuchowanie wpisów w kubełku.
Współczynnik obciążenia (0.75) uruchamia podwojenie rozmiaru i ponowne haszowanie.
Wstępne określenie rozmiaru pozwala uniknąć kosztownych zmian rozmiaru, a kolejność iteracji nie jest gwarantowana.

Następnie zobaczą Państwo, dlaczego sam hashCode nie wystarcza bez poprawnego equals.

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

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Często zadawane pytania

Czy lekcja „Jak działa HashMap” jest bezpłatna?

Tak — pełny tekst „Jak działa HashMap” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Jak działa HashMap”?

Koszyki, haszowanie i kolizje Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Java Academy?

Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Jak działa HashMap”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?

Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Java Academy