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
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.
| Operacja | unordered_map / unordered_set | gp_hash_table | Ile 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 jest | Iterator albo end(). | Tak samo. | 1,9× / 1,9×zbiór: 2,3× / 2,3× |
find(k), klucza nie ma | Zwraca 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 warunkowe | Wolna 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_emplace | Są. | Brak, używaj insert lub []. | brak w gp |
size, empty | Są, O(1). | Tak samo. | bez różnicy |
clear() | Jest. | Tak samo. | 0,75× / 2,0×zbiór: 0,85× / 2,4× |
| Iterowanie | Kolejność nieokreślona. | Tak samo. | 2,4× / 7,8×zbiór: 2,5× / 8,3× |
reserve(n), rehash | Są. | Brak. Rozmiar startowy podaje się w konstruktorze. | brak w gp |
load_factor, bucket_count | Są. | Brak w domyślnej konfiguracji. | brak w gp |
| Kolizje | Lista 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:
| Klucze | Bez pierwszego XOR | Z pierwszym XOR | splitmix64 |
|---|---|---|---|
| losowe | 1,4 ms | 1,4 ms | 1,7 ms |
i << 16 | 1,0 ms | 1,2 ms | 1,5 ms |
i << 32 | 2,2 ms | 1,3 ms | 1,4 ms |
i << 44 | 52,6 ms | 1,2 ms | 1,6 ms |
i << 48 | 554 ms | 0,9 ms | 1,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):
| Generator | Czas na liczbę | Bitów w wyniku |
|---|---|---|
mt19937 | ~1,6 ns | 32 |
mt19937_64 | ~1,6 ns | 64 |
| splitmix64 | ~2,0 ns | 64 |
mt19937_64 + uniform_int_distribution | ~2,5 ns | zadany przedział |
| xorshift64 | ~3,4 ns | 64 |
rand() | ~15,8 ns | 31 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ć
- Brak
count. Kod przepisany zunordered_mapczęsto się nie skompiluje właśnie przez to. Zamień nafind(k) != end(). m[k]przy sprawdzaniu tworzy element. Tak samo jak w zwykłej mapie:if (m[k])dopisuje klucz z zerem i powiększa tablicę. Do samego sprawdzania używajfind.- Domyślny hasz a regularne dane. Na Codeforces to znany cel hacków. Na OI testy są stałe, ale klucze typu
i * 1024potrafią spowolnić tablicę przypadkiem. - Dużo usunięć. Adresowanie otwarte zostawia po usuniętych elementach znaczniki, które nadal wydłużają wyszukiwanie. Przy naprzemiennym wstawianiu i usuwaniu wielu kluczy przewaga nad
unordered_mapmoże zniknąć. - Klucze niebędące liczbami. Dla
pair,vectori innych typów bezstd::hashtrzeba podać własny hasz, dokładnie jak przyunordered_map.