Så här använder 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.

#include <unordered_set>
#include <string>
#include <print>
using namespace std::string_literals;

int main() {
    auto names = std::unordered_set<std::string>{"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.

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<Key, Hash, Equal>

En unordered_set lagrar endast nycklar – precis som en vanlig set – men utan sortering. Som standard används std::hash<Key> för att generera hashvärden och std::equal_to<Key> för jämförelser.

#include <unordered_set>
#include <print>

int main() {
    auto numbers = std::unordered_set<int>{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.

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:

struct MyHash {
    size_t operator()(std::string const& s) const noexcept {
        return std::hash<std::string>{}(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::string, MyHash, MyEqual>{};

std::unordered_map<Key, Value, Hash, Equal>

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.

#include <unordered_map>
#include <print>
#include <string>
using namespace std::string_literals;

int main() {
    auto ages = std::unordered_map<std::string, int>{
        {"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);
}

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:

auto m = std::unordered_map<int, std::string>{};
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.

#include <map>
#include <unordered_map>
#include <string>
#include <random>
#include <chrono>
#include <print>
namespace cr = std::chrono;

template <typename Container>
void benchmark(std::string const& type, unsigned N) {
    auto r = std::default_random_engine{std::random_device{}()};
    auto U = std::uniform_int_distribution<unsigned>{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<cr::milliseconds>(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<cr::milliseconds>(stop - start);
        std::println("{} lookup: {:4} ms", type, elapsed.count());
    }
}

int main() {
    auto const N = 1'000'000U;
    benchmark< std::map<int, int> >("binary-tree", N);
    benchmark< std::unordered_map<int, int> >("hash-table ", N);
}

Exempel på körning (din maskin kan ge andra värden):

binary-tree insert: 2417 ms
binary-tree lookup: 2115 ms
hash-table  insert: 1052 ms
hash-table  lookup:  815 ms

Try it yourself on Compiler Explorer

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.