hash_table_chaining.cpp

/**
 * Hash table with separate chaining, dynamic rehashing.
 * Teaching demo: string keys, int values, division method h(k)=hash_code(k)%m.
 */
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>

class HashMapChaining {
    static constexpr double kMaxLoadFactor = 0.75;

    struct Entry {
        std::string key;
        int value;
    };

    std::vector<std::list<Entry>> buckets_;
    std::size_t size_{0};

    static std::size_t strHash(const std::string& s) {
        std::size_t h = 5381;
        for (unsigned char c : s) {
            h = ((h << 5) + h) + c;  // DJB2-style
        }
        return h;
    }

    std::size_t indexFor(const std::string& key) const {
        return strHash(key) % buckets_.size();
    }

    void rehash(std::size_t new_m) {
        std::vector<std::list<Entry>> old = std::move(buckets_);
        buckets_.assign(new_m, {});
        size_ = 0;
        for (auto& chain : old) {
            for (auto& e : chain) {
                insertUnchecked(std::move(e.key), e.value);
            }
        }
    }

    void insertUnchecked(std::string key, int value) {
        std::size_t idx = strHash(key) % buckets_.size();
        for (auto& e : buckets_[idx]) {
            if (e.key == key) {
                e.value = value;
                return;
            }
        }
        buckets_[idx].push_back(Entry{std::move(key), value});
        ++size_;
    }

    void ensureCapacity() {
        if (buckets_.empty()) {
            buckets_.assign(7, {});
            return;
        }
        double alpha = static_cast<double>(size_) / static_cast<double>(buckets_.size());
        if (alpha <= kMaxLoadFactor) return;
        // next prime-ish size
        std::size_t nm = buckets_.size() * 2 + 1;
        rehash(nm);
    }

public:
    void insert(const std::string& key, int value) {
        ensureCapacity();
        std::size_t idx = indexFor(key);
        for (auto& e : buckets_[idx]) {
            if (e.key == key) {
                e.value = value;
                return;
            }
        }
        buckets_[idx].push_back(Entry{key, value});
        ++size_;
    }

    bool find(const std::string& key, int& out) const {
        if (buckets_.empty()) return false;
        std::size_t idx = indexFor(key);
        for (const auto& e : buckets_[idx]) {
            if (e.key == key) {
                out = e.value;
                return true;
            }
        }
        return false;
    }

    bool erase(const std::string& key) {
        if (buckets_.empty()) return false;
        std::size_t idx = indexFor(key);
        auto& chain = buckets_[idx];
        for (auto it = chain.begin(); it != chain.end(); ++it) {
            if (it->key == key) {
                chain.erase(it);
                --size_;
                return true;
            }
        }
        return false;
    }

    std::size_t bucketCount() const { return buckets_.size(); }
    std::size_t size() const { return size_; }
    double loadFactor() const {
        if (buckets_.empty()) return 0;
        return static_cast<double>(size_) / static_cast<double>(buckets_.size());
    }
};

int main() {
    HashMapChaining map;
    map.insert("apple", 1);
    map.insert("banana", 2);
    map.insert("grape", 3);
    int v = 0;
    if (map.find("banana", v)) std::cout << "banana -> " << v << "\n";
    std::cout << "size=" << map.size() << " buckets=" << map.bucketCount()
              << " load_factor=" << map.loadFactor() << "\n";

    for (int i = 0; i < 50; ++i) {
        map.insert("k" + std::to_string(i), i);
    }
    std::cout << "after bulk insert: size=" << map.size()
              << " buckets=" << map.bucketCount()
              << " load_factor=" << map.loadFactor() << "\n";
    return 0;
}