t-olimpians net · C++ · struktury danych

gp_hash_table

Szybsza tablica haszująca z GNU pb_ds: jak jej używać jako mapy i zbioru, czym różni się od unordered_map i unordered_set i gdzie łatwo się na niej potknąć.

Adresowanie otwarte na 16 miejscach

Wpisz liczbę i wstaw ją. Indeks to hash(x) & 15, a przy kolizji sprawdzane jest kolejne miejsce.

Z domyślnym haszem wielokrotności 16 lądują w jednym ciągu i każde kolejne wstawienie sprawdza coraz więcej miejsc. Po przełączeniu na splitmix64 te same liczby rozkładają się po tablicy. Przy połowie zajętych miejsc prawdziwa gp_hash_table podwoiłaby rozmiar, dlatego demo zatrzymuje się na 8 elementach.

Przygotowanie

Struktura jest częścią rozszerzenia GCC, więc działa na sprawdzarce OI, Codeforces i AtCoder, ale nie w MSVC.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

Jako mapa

Drugi parametr szablonu to typ wartości, tak jak w unordered_map.

gp_hash_table<int, int> cnt;

cnt[5]++;                        // operator[] działa jak zwykle
cnt.insert({7, 3});              // zwraca pair<iterator, bool>

auto it = cnt.find(5);
if (it != cnt.end())
    cout << it->second << '\n';  // 1

cnt.erase(7);                    // zwraca bool: czy coś usunięto

for (auto &[k, v] : cnt)          // kolejność nieokreślona
    cout << k << ' ' << v << '\n';

Jako zbiór

Zamiast typu wartości podaje się null_type. Znika wtedy operator[], a iterator wskazuje bezpośrednio na klucz.

gp_hash_table<int, null_type> s;

s.insert(5);
s.insert(5);                     // duplikat, nic się nie zmienia

if (s.find(5) != s.end())        // zamiast count()
    cout << "jest\n";

s.erase(5);

for (int x : s)
    cout << x << '\n';

W starszych GCC ten typ nazywał się null_mapped_type.

Porównanie metod

Średnia złożoność podstawowych operacji jest taka sama, czyli O(1). Różnią się dostępne metody i stała.

Operacjaunordered_map / unordered_setgp_hash_tableIle razy szybciej
m[k]Tworzy wartość domyślną, jeśli klucza nie ma. Tylko mapa.Tak samo. Tylko mapa.2,5× / 4,1×
insert(x)Zwraca pair<iterator, bool>.Tak samo.2,5× / 3,8×zbiór: 2,6× / 4,9×
find(k), klucz jestIterator albo end().Tak samo.1,9× / 1,9×zbiór: 2,3× / 2,3×
find(k), klucza nie maZwraca end().Tak samo.1,7× / 1,9×zbiór: 1,9× / 1,9×
count(k)Zwraca 0 lub 1.Brak, używaj find(k) != end().jak find
contains(k)Od C++20.Brak.jak find
erase(k)Zwraca liczbę usuniętych (0 lub 1).Zwraca bool.6,8× / 9,8×zbiór: 7,8× / 11,2×
Usuwanie warunkoweWolna funkcja std::erase_if(m, pred) od C++20.Metoda m.erase_if(pred).nie mierzono
at(k)Wyjątek, gdy klucza nie ma.Brak.brak w gp
emplace, try_emplaceSą.Brak, używaj insert lub [].brak w gp
size, emptySą, O(1).Tak samo.bez różnicy
clear()Jest.Tak samo.0,75× / 2,0×zbiór: 0,85× / 2,4×
IterowanieKolejność nieokreślona.Tak samo.2,4× / 7,8×zbiór: 2,5× / 8,3×
reserve(n), rehashSą.Brak. Rozmiar startowy podaje się w konstruktorze.brak w gp
load_factor, bucket_countSą.Brak w domyślnej konfiguracji.brak w gp
KolizjeLista w każdym kubełku, osobna alokacja na element.Jedna tablica, przy kolizji sprawdzane jest kolejne miejsce.
DostępnośćKażdy kompilator.Tylko GCC.

Przyspieszenie to czas unordered_* podzielony przez czas gp_hash_table, dla n = 10⁵ i n = 10⁶ losowych kluczy int. Pierwsza liczba dotyczy mapy <int, int>, druga linia zbioru. Obie struktury używały tego samego haszu splitmix64 i startowały bez reserve ani rozmiaru początkowego. Kompilacja: G++ 13.3, -O3 -static -std=c++23 (flagi jak na OI), mediana z kilku powtórzeń na jednym rdzeniu. Na innym sprzęcie liczby będą inne, ale proporcje zwykle podobne. Wartość poniżej 1× oznacza, że gp_hash_table była wolniejsza.

Największa przewaga jest przy usuwaniu i iterowaniu: gp_hash_table przy usunięciu tylko oznacza miejsce jako wolne i przechodzi po ciągłej tablicy, a unordered_map zwalnia pamięć węzła i skacze po wskaźnikach. Przy większym n rośnie znaczenie pamięci podręcznej, dlatego przewaga dla 10⁶ jest wyraźniejsza.

Rozmiar startowy

Odpowiednikiem reserve jest piąty argument konstruktora, czyli polityka zmiany rozmiaru. Pierwsze cztery {} budują domyślnie hasz, porównanie, mapowanie na indeks i sondowanie.

gp_hash_table<int, int> m({}, {}, {}, {}, {1 << 16});

Tablica startuje od 65 536 miejsc i powiększa się dwukrotnie, gdy zapełni się w połowie, więc taki start wystarcza na około 32 tysiące elementów bez rehashowania. Podawaj potęgę dwójki, bo indeks liczony jest maską bitową.

Własny hasz

Mapowanie hash & (rozmiar − 1) patrzy tylko na niskie bity, a domyślny hasz liczb całkowitych w GCC to sama liczba. Klucze o tych samych niskich bitach tworzą więc długie ciągi kolizji, co widać w demie na górze. Splitmix64 z losowym seedem miesza wszystkie bity i zapobiega celowanym atakom.

struct H {
    static uint64_t sm(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t R =
            chrono::steady_clock::now().time_since_epoch().count();
        return sm(x + R);
    }
};

gp_hash_table<int, int, H>       m({}, {}, {}, {}, {1 << 16});
gp_hash_table<int, null_type, H> s({}, {}, {}, {}, {1 << 16});

Prostsza wersja do zapamiętania

Na OI testy są przygotowane z góry i nikt nie dobiera danych pod Twój hasz, więc pełny splitmix64 nie jest potrzebny. Wystarczą trzy kroki: XOR, mnożenie przez losową nieparzystą liczbę i znowu XOR, bez żadnych stałych do zapamiętania:

struct H {
    size_t operator()(uint64_t x) const {
        static const uint64_t C = mt19937_64(time(0))() | 1;
        x ^= x >> 32;
        x *= C;
        return x ^ (x >> 32);
    }
};

x *= C rozprowadza bity w górę: każdy bit wpływa na wszystkie wyższe bity iloczynu. Mnożenie przez liczbę nieparzystą jest odwracalne modulo 2⁶⁴, dlatego | 1 gwarantuje, że różne wartości dają różne iloczyny. Mnożenie nie przenosi jednak informacji w dół: dolne bity iloczynu zależą tylko od dolnych bitów tego, co mnożymy, a gp_hash_table wybiera miejsce właśnie po dolnych bitach. Dlatego końcowe x ^ (x >> 32) ściąga wymieszaną górną połowę na dół.

Po co pierwszy XOR

Bez linijki x ^= x >> 32 hasz ma dziurę. Końcowy XOR ściąga na dół tylko bity 32–63 iloczynu. Jeśli klucze różnią się wyłącznie wysokimi bitami, np. i << 48, to iloczyn x * C ma dolne 48 bitów równe zeru, więc po XOR-ze dolne 16 bitów wyniku jest zerem dla każdego klucza. Przy tablicy do 65 536 miejsc wszystkie klucze trafiają wtedy w to samo miejsce.

Pierwszy XOR składa górną połowę klucza na dolną jeszcze przed mnożeniem. Dzięki temu wysokie bity też biorą udział w mnożeniu i rozchodzą się po całym wyniku. Ta operacja jest odwracalna, więc różne klucze nadal dają różne wartości. Czas dla 20 tysięcy kluczy w gp_hash_table:

KluczeBez pierwszego XORZ pierwszym XORsplitmix64
losowe1,4 ms1,4 ms1,7 ms
i << 161,0 ms1,2 ms1,5 ms
i << 322,2 ms1,3 ms1,4 ms
i << 4452,6 ms1,2 ms1,6 ms
i << 48554 ms0,9 ms1,5 ms

Kluczy typu int ten problem nie dotyczy, bo nie mają wysokich bitów. Pojawia się przy long long i uint64_t, np. przy spakowanych lub przesuniętych wartościach, a także w haszach par i wektorów, które używają tej samej funkcji. Z pierwszym XOR-em prosty hasz był dobry na wszystkich wzorcach i nawet odrobinę szybszy od splitmix64.

Co robią time i mt19937_64

time(0) z nagłówka <ctime> zwraca liczbę sekund, które upłynęły od 1 stycznia 1970 roku (czas uniksowy), np. około 1,8 miliarda. Wartość zmienia się raz na sekundę, więc dwa uruchomienia w tej samej sekundzie dostaną ten sam wynik. Służy tu tylko jako ziarno, czyli punkt startowy dla generatora.

mt19937_64 z nagłówka <random> to generator liczb pseudolosowych Mersenne Twister w wersji 64-bitowej. Z ziarna buduje wewnętrzny stan (312 liczb 64-bitowych), a każde wywołanie () zwraca kolejną liczbę z pełnego zakresu 64 bitów. Ten sam seed zawsze daje ten sam ciąg liczb, więc generator jest deterministyczny.

Zapis mt19937_64(time(0))() ma dwie pary nawiasów. Pierwsza tworzy tymczasowy generator z ziarnem time(0), druga od razu wywołuje go raz i pobiera pierwszą liczbę. Generator potem znika, bo potrzebna jest tylko ta jedna wartość.

Dlaczego nie użyć time(0) | 1 bezpośrednio jako mnożnika? Bo to liczba 31-bitowa, a mnożnik powinien mieć nieregularne bity w całym zakresie 64 bitów. Przy małym mnożniku i małych kluczach górna połowa iloczynu byłaby pusta i XOR nie miałby czego ściągać w dół. Generator zamienia małe, przewidywalne ziarno w pełną, losowo wyglądającą liczbę 64-bitową.

Słowo static sprawia, że C jest liczone tylko raz, przy pierwszym wywołaniu, a potem pozostaje stałe. To konieczne, bo hasz tego samego klucza musi być zawsze taki sam. Oba nagłówki są dołączane przez <bits/stdc++.h>.

Dlaczego mt19937_64, a nie inny generator

Czas losowania jednej liczby, zmierzony na 100 milionach losowań z flagami jak na OI (G++ 13.3, -O3 -static -std=c++23):

GeneratorCzas na liczbęBitów w wyniku
mt19937~1,6 ns32
mt19937_64~1,6 ns64
splitmix64~2,0 ns64
mt19937_64 + uniform_int_distribution~2,5 nszadany przedział
xorshift64~3,4 ns64
rand()~15,8 ns31 na Linuksie, 15 na Windowsie

mt19937_64 jest najszybszy z mierzonych, mimo dużego stanu, bo generuje liczby partiami. Daje od razu pełne 64 bity, jest częścią standardu i działa tak samo na każdym kompilatorze. Prostsze generatory, jak xorshift czy splitmix64, nie dają tu żadnego zysku, a różnica rzędu nanosekund i tak nigdy nie jest wąskim gardłem rozwiązania.

rand() ma kilka wad naraz. W GCC jest około 10 razy wolniejszy, bo jest zabezpieczony blokadą dla wielu wątków. Jego zakres zależy od systemu: na sprawdzarce OI RAND_MAX wynosi 2³¹ − 1, ale na Windowsie z MinGW tylko 32 767, więc np. rand() % 1000000 lokalnie nigdy nie przekroczy 32 767. Do tego do 64-bitowego mnożnika trzeba by sklejać kilka wywołań.

Przy okazji: do mieszania tablicy używaj shuffle(v.begin(), v.end(), rng). Stare random_shuffle zostało usunięte w C++17, więc z flagą -std=c++23 kod się nie skompiluje.

Pary i wektory uint64_t

Ten sam prosty hasz z mnożeniem wystarczy też dla par i wektorów. Mieszanie (XOR, mnożenie, XOR) jest wydzielone do funkcji f, a przeciążenia operator() tylko z niej korzystają.

struct H {
    static uint64_t f(uint64_t x) {
        static const uint64_t C = mt19937_64(time(0))() | 1;
        x ^= x >> 32;
        x *= C;
        return x ^ (x >> 32);
    }
    // int, long long, uint64_t
    size_t operator()(uint64_t x) const {
        return f(x);
    }
    // pair<uint64_t, uint64_t>
    size_t operator()(const pair<uint64_t, uint64_t>& p) const {
        return f(f(p.first) + p.second);
    }
    // vector<uint64_t>
    size_t operator()(const vector<uint64_t>& v) const {
        uint64_t h = v.size();
        for (uint64_t x : v)
            h = f(h + x);
        return h;
    }
};

gp_hash_table<pair<uint64_t, uint64_t>, int, H> mp;
gp_hash_table<vector<uint64_t>, null_type, H>   sv;

Dwóch liczb 64-bitowych nie da się spakować w jedną bez straty, więc para jest haszowana w dwóch krokach: najpierw mieszany jest first, potem dodawany second i całość mieszana jeszcze raz. Wektor jest mieszany element po elemencie, a start od v.size() odróżnia wektory różnej długości, np. {0} od {0, 0}. W obu przypadkach kolejność ma znaczenie, więc {1, 2} i {2, 1} dają różne hasze.

Losowy mnożnik C jest zmienną static wewnątrz f, więc wszystkie przeciążenia korzystają z tego samego C. W teście z gp_hash_table na parach (siatka i, j, przesunięte i << 20 i losowe) oraz wektorach ta wersja była tak samo szybka jak splitmix64. Haszowanie wektora kosztuje O(długość) przy każdej operacji, a przy trafieniu w zajęte miejsce dochodzi jeszcze porównanie całych wektorów.

Na co uważać