hash_table_open_addressing.cpp

/**
 * Open addressing: linear probing, quadratic probing, double hashing.
 * Tombstones preserve probe sequences after erase.
 */
#include <iostream>
#include <string>
#include <vector>

enum class ProbeKind { Linear, Quadratic, Double };

template <ProbeKind Kind>
class OpenAddressMap {
    enum class State : unsigned char { Empty, Occupied, Deleted };

    struct Slot {
        State state{State::Empty};
        std::string key;
        int value{0};
    };

    std::vector<Slot> table_;
    std::size_t alive_{0};

    static constexpr double kMaxLoad = 0.65;

    static std::size_t h1(const std::string& s) {
        std::size_t h = 0;
        for (unsigned char c : s) h = h * 131u + c;
        return h;
    }

    static std::size_t h2(const std::string& s) {
        std::size_t h = 1;
        for (unsigned char c : s) h = h * 37u + c;
        h = (h << 1) | 1u;
        return h;
    }

    std::size_t slotIndex(const std::string& key, std::size_t i) const {
        std::size_t m = table_.size();
        std::size_t base = h1(key) % m;
        if constexpr (Kind == ProbeKind::Linear) {
            return (base + i) % m;
        } else if constexpr (Kind == ProbeKind::Quadratic) {
            return (base + i * i) % m;
        } else {
            std::size_t d = h2(key) % m;
            if (d == 0) d = 1;
            return (base + i * d) % m;
        }
    }

    void rehash(std::size_t new_m) {
        std::vector<Slot> old = std::move(table_);
        table_.assign(new_m, {});
        alive_ = 0;
        for (const auto& s : old) {
            if (s.state == State::Occupied) {
                insertInternal(s.key, s.value);
            }
        }
    }

    void insertInternal(const std::string& key, int value) {
        std::size_t m = table_.size();
        for (std::size_t i = 0; i < m; ++i) {
            std::size_t idx = slotIndex(key, i);
            Slot& sl = table_[idx];
            if (sl.state == State::Empty || sl.state == State::Deleted) {
                sl.state = State::Occupied;
                sl.key = key;
                sl.value = value;
                ++alive_;
                return;
            }
            if (sl.key == key) {
                sl.value = value;
                return;
            }
        }
    }

public:
    void insert(const std::string& key, int value) {
        if (table_.empty()) table_.assign(17, {});
        if (static_cast<double>(alive_) / static_cast<double>(table_.size()) > kMaxLoad) {
            rehash(table_.size() * 2 + 1);
        }
        std::size_t m = table_.size();
        for (std::size_t i = 0; i < m; ++i) {
            std::size_t idx = slotIndex(key, i);
            Slot& sl = table_[idx];
            if (sl.state == State::Empty || sl.state == State::Deleted) {
                sl.state = State::Occupied;
                sl.key = key;
                sl.value = value;
                ++alive_;
                return;
            }
            if (sl.key == key) {
                sl.value = value;
                return;
            }
        }
        rehash(table_.size() * 2 + 1);
        insertInternal(key, value);
    }

    bool find(const std::string& key, int& out) const {
        if (table_.empty()) return false;
        std::size_t m = table_.size();
        for (std::size_t i = 0; i < m; ++i) {
            std::size_t idx = slotIndex(key, i);
            const Slot& sl = table_[idx];
            if (sl.state == State::Empty) return false;
            if (sl.state == State::Deleted) continue;
            if (sl.key == key) {
                out = sl.value;
                return true;
            }
        }
        return false;
    }

    bool erase(const std::string& key) {
        if (table_.empty()) return false;
        std::size_t m = table_.size();
        for (std::size_t i = 0; i < m; ++i) {
            std::size_t idx = slotIndex(key, i);
            Slot& sl = table_[idx];
            if (sl.state == State::Empty) return false;
            if (sl.state == State::Deleted) continue;
            if (sl.key == key) {
                sl.state = State::Deleted;
                sl.key.clear();
                --alive_;
                return true;
            }
        }
        return false;
    }

    std::size_t slots() const { return table_.size(); }
    std::size_t size() const { return alive_; }
};

template <ProbeKind K>
static void demo(const char* name) {
    std::cout << "=== " << name << " ===\n";
    OpenAddressMap<K> m;
    m.insert("a", 1);
    m.insert("b", 2);
    int v = 0;
    if (m.find("a", v)) std::cout << "a -> " << v << "\n";
    std::cout << "slots=" << m.slots() << " size=" << m.size() << "\n";
}

int main() {
    demo<ProbeKind::Linear>("Linear probing");
    demo<ProbeKind::Quadratic>("Quadratic probing");
    demo<ProbeKind::Double>("Double hashing");
    return 0;
}