# Så här använder du hash-table containers i C++ 13 augusti 2025 | https://www.ribomation.se/blog/2025/sa-har-anvander-du-hash-table-containers-i-c++/ I mina två tidigare artiklar gick jag igenom de sorterade associativa containrarna `std::set` och `std::map` – båda implementerade som balanserade binära sökträd. Nu är det dags att titta på deras osorterade syskon: `std::unordered_set` och `std::unordered_map`. Gemensamt för dessa är att de använder en **hash-tabell** internt. ```cpp #include #include #include using namespace std::string_literals; int main() { auto names = std::unordered_set{"Anna"s, "Berit"s, "Carin"s}; for (auto const& name : names) std::print("{} ", name); //prints: Carin Berit Anna } ``` Vad är en hash-tabell? ---------------------- En hash-tabell består av ett antal **buckets**, där varje bucket rymmer noll eller fler element. Vilken bucket ett element hamnar i beror på dess hash-värde, som räknas ut med hjälp av en hash-funktion. En dylik funktion tar ett nyckelvärde (key) och returnerar ett icke-negativt heltalsvärde. Samma nyckelvärde måste alltid ge samma hash-värde. Vidare så behövs en equals funktion, med egenskapen att om två nycklar har samma hash-värde, måste equals returnera true. Samt omvänt, om två nycklar är lika måste de ha samma hash-värde. Själva hash-tabellen är en dynamiskt allokerad array, där storleken är vald som ett primtal. Ett hash-värde ger en bucket index-position i array:en genom att ta värdet modulo array-storleken. På så sätt får man en insättnings-position eller återfinner ett befintligt värde. Det händer att två nycklar ger upphov till samma bucket. Detta kallas för nyckel-kollision och innebär att mer än ett värde lagras i samma bucket. Vanligtvis utgörs en bucket av en enkel-länkad lista. ![Hash table med buckets](/blog/2025/sa-har-anvander-du-hash-table-containers-i-c++/hash-table-1300w.png "Hash table med buckets") _Bilden är hämtad från Wikipedia._ Vitsen med en hash-tabell är att åtkomsttiden för insättning, sökning och borttagning är approximativt konstant, dvs oberoende av antalet element i tabellen. Detta kallas för _O(1)_. `std::unordered_set` -------------------------------------- En unordered\_set lagrar endast nycklar – precis som en vanlig set – men utan sortering. Som standard används `std::hash` för att generera hashvärden och `std::equal_to` för jämförelser. ```cpp #include #include int main() { auto numbers = std::unordered_set{1, 2, 3, 4, 5, 6}; numbers.insert(42); numbers.insert(3); // duplicat ignoreras if (numbers.contains(42)) std::println("found 42"); numbers.erase(4); std::println("set: {}", numbers); } ``` Till skillnad från std::set så kommer iterationen inte vara i sorterad ordning, utan i den ordning elementen råkar ligga i bucketerna. ```shell found 42 set: {6, 5, 3, 2, 42, 1} ``` Vill du ha en egen hash-funktion eller jämförelse, skickar du in dessa som template parametrar: ```cpp struct MyHash { size_t operator()(std::string const& s) const noexcept { return std::hash{}(s) ^ 0x9e3779b97f4a7c15ULL; } }; struct MyEqual { bool operator()(std::string const& a, std::string const& b) const noexcept { return a.size() == b.size(); // jämför längden istället! } }; auto s = std::unordered_set{}; ``` `std::unordered_map` --------------------------------------------- En unordered\_map är precis som en map, fast utan sortering. Den parar ihop en nyckel med ett värde, men elementens placering styrs av hashvärdet istället för nyckelordning. ```cpp #include #include #include using namespace std::string_literals; int main() { auto ages = std::unordered_map{ {"Anna"s, 42}, {"Berit"s, 37}, {"Doris"s, 23} }; ages["Carin"s] = 50; // skapar nytt element ages["Anna"s] += 3; // uppdaterar befintligt ++ages["Doris"s]; // uppdaterar befintligt if (ages.contains("Berit")) std::println("Berit finns"); for (auto&& [name, age] : ages) std::println("{} -> {}", name, age); } ``` ```shell Berit finns Carin -> 50 Doris -> 24 Berit -> 37 Anna -> 45 ``` Även här kan du skicka in egna hash- och jämförelsefunktioner om standardbeteendet inte räcker. ### Prestanda och buckets Eftersom unordered\_\* bygger på hash-tabeller så beror prestandan på hur väl hashfunktionen sprider nycklarna över bucketerna. Du kan styra antalet buckets och lastfaktorn (load factor) själv: ```cpp auto m = std::unordered_map{}; m.max_load_factor(0.7F); // sänk lastfaktorn m.reserve(1000); // förallokera buckets ``` Metoden reserve() ser till att det finns tillräckligt många buckets för att hålla nere antalet omhashningar, vilket annars sker automatiskt när lastfaktorn överskrids. Prestandajämförelse: `std::map` vs `std::unordered_map` ------------------------------------------------------- För att ge en känsla av skillnaden i åtkomsttid kan vi mäta hur lång tid det tar att sätta in och slå upp ett antal element. Här använder jag `std::chrono` för att mäta tidsåtgången. ```cpp #include #include #include #include #include #include namespace cr = std::chrono; template void benchmark(std::string const& type, unsigned N) { auto r = std::default_random_engine{std::random_device{}()}; auto U = std::uniform_int_distribution{1, N * 10U}; auto target = Container{}; { auto start = std::chrono::steady_clock::now(); for (auto i = 0U; i < N; ++i) target[U(r)] = i; auto stop = std::chrono::steady_clock::now(); auto elapsed = cr::duration_cast(stop - start); std::println("{} insert: {:4} ms", type, elapsed.count()); } { auto start = std::chrono::steady_clock::now(); for (auto i = 0U; i < N; ++i) target.contains(U(r)); auto stop = std::chrono::steady_clock::now(); auto elapsed = cr::duration_cast(stop - start); std::println("{} lookup: {:4} ms", type, elapsed.count()); } } int main() { auto const N = 1'000'000U; benchmark< std::map >("binary-tree", N); benchmark< std::unordered_map >("hash-table ", N); } ``` Exempel på körning (din maskin kan ge andra värden): ```shell binary-tree insert: 2417 ms binary-tree lookup: 2115 ms hash-table insert: 1052 ms hash-table lookup: 815 ms ``` [![Compiler Explorer](/images/compiler-explorer-logo.svg "Compiler Explorer - Try it yourself") Try it yourself on Compiler Explorer](https://godbolt.org/z/bdoeqKe7W) Som synes är std::unordered\_map betydligt snabbare vid både insättning och uppslagning när antalet element är stort och hashfunktionen är effektiv. Detta är den huvudsakliga anledningen till att använda hash-tabeller när du inte behöver sorterad ordning. Sammanfattning -------------- #### När ska man välja unordered\_\*? * När du inte bryr dig om sorteringsordning * När du behöver snabb genomsnittlig åtkomst (O(1)) * När hashfunktionen är enkel och sprider nycklarna väl #### Undvik dem när: * Du behöver iteration i sorterad ordning → använd std::set/std::map istället * Nyckeltypen är kostsam att hashberäkna eller dåligt distribuerad Med std::unordered\_set och std::unordered\_map är verktygslådan av associativa containrar i C++ komplett. Nu kan du välja mellan sorterad ordning och logaritmisk åtkomsttid med tree containers – eller osorterad ordning och konstant genomsnittlig åtkomsttid med hash-tabeller.