Jak działa mapa w Go?

Mapa w Go jest zaimplementowana jako tablica mieszająca.

Główne składniki struktury map:

• Funkcja haszująca: Mapuje klucze na wartości haszujące (liczby całkowite).
• Tablica kubełków: Zbiór list lub tablic, w których przechowywane są pary klucz-wartość. Indeks kubełka jest określany przez wartość haszującą klucza.
• Obsługa kolizji: Gdy różne klucze mają ten sam hash (kolizja), elementy z tymi kluczami są przechowywane w tym samym kubełku, zwykle w postaci listy powiązanej lub kubełka nadmiarowego.
• Współczynnik obciążenia: Stosunek liczby elementów do liczby kubełków. Po przekroczeniu pewnego progu następuje rehaszowanie: tworzy się nową, większą tablicę kubełków i przenosi wszystkie elementy ze starych kubełków do nowych.

Struktura map w Go jest reprezentowana przez typ hmap:

 type hmap struct {
    count     int // Liczba elementów
    flags     uint8 // Flagi stanu
    B         uint8 // log_2 liczby kubełków (liczba kubełków to 2^B)
    noverflow uint16 // Liczba kubełków z nadmiarem (tylko do statystyk)
    hash0     uint32 // Wartość początkowa funkcji haszującej

    buckets    unsafe.Pointer // Wskaźnik na tablicę kubełków (główne i nadmiarowe)
    oldbuckets unsafe.Pointer // Wskaźnik na starą tablicę kubełków podczas migracji
    nevacuate  uintptr // Określa, do którego starego kubełka zakończyła się migracja

    extra *mapextra // Dodatkowe informacje (opcjonalnie)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Wskaźniki na tablice nadmiarowych kubełków
    oldoverflow *[2]*[]*bmap // Wskaźniki na stare tablice nadmiarowych kubełków
    nextOverflow *bmap // Następny wolny nadmiarowy kubełek
}

 type bmap struct {
    tophash [8]uint8 // Top-hash (górne bity hasza) dla przyspieszenia wyszukiwania w kubełku
    // Następują klucze, wartości i wskaźniki na następny bmap (jeśli kubełek jest przepełniony)
    // rozkład wszystkich danych dla hmap.buckets w jednym malloc
    // patrz ../../runtime/map.go dla szczegółów
}

Operacje:

• Wstawianie/aktualizacja: Oblicza się hash klucza, określa kubełek. Jeśli klucz już istnieje, wartość jest aktualizowana. W przeciwnym razie, para klucz-wartość jest dodawana do kubełka. Przy przepełnieniu kubełka lub przekroczeniu Load Factor może nastąpić rehaszowanie.
• Wyszukiwanie: Oblicza się hash klucza, określa kubełek. Elementy w kubełku są przeszukiwane po top-hash, następnie porównywane są pełne klucze. Zwracana jest wartość i flaga istnienia.
• Usuwanie: Oblicza się hash klucza, określa kubełek. Element jest oznaczany jako usunięty (ale nie jest natychmiast usuwany z pamięci). Usunięcie następuje podczas operacji późniejszych lub rehaszowania.

Mapa w Go nie jest synchronizowana i nie może być bezpiecznie używana przez wiele gorutyn bez zewnętrznej synchronizacji.