Hoe zou je de datastructuur ontwerpen voor snelle zoekopdrachten op sleutel met behulp van een hashfunctie?

Voor snelle zoekopdrachten op sleutel met behulp van een hashfunctie wordt gewoonlijk een datastructuur gebruikt die een hash-tabel (hash table) wordt genoemd. De belangrijkste elementen van het ontwerp zijn:

1. Array van buckets (manden) — de hoofdcontainer voor het opslaan van elementen.
2. Hashfunctie — zet de sleutel om in een index van de array.
3. Afhandeling van botsingen — wanneer twee sleutels dezelfde index geven.

Voorbeeld van botsingsafhandeling:

• Chaining (ketting): in elke mand wordt een gekoppelde lijst van elementen met dezelfde index opgeslagen.
• Open adressering: bij een botsing wordt de volgende vrije cel gezocht.

Voorbeeld in C++ met chaining:

#include <vector>
#include <list>
#include <string>

class HashTable {
    static const int SIZE = 100;
    std::vector<std::list<std::pair<std::string, int>>> table;

    int hash(const std::string& key) {
        int hashVal = 0;
        for (char c : key) {
            hashVal = (hashVal * 31 + c) % SIZE;
        }
        return hashVal;
    }

public:
    HashTable() : table(SIZE) {}

    void insert(const std::string& key, int value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                kv.second = value; // bijwerken
                return;
            }
        }
        table[idx].emplace_back(key, value);
    }

    bool find(const std::string& key, int& value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                value = kv.second;
                return true;
            }
        }
        return false;
    }
};

Deze aanpak zorgt voor een gemiddelde zoektijd die dicht bij O(1) ligt.