hashmap.hpp

#ifndef CUSTOM_HASHMAP_HPP
#define CUSTOM_HASHMAP_HPP

#include <vector>
#include <string>
#include <cstdint>
#include <cstdlib>

// Minimal separate-chaining HashMap.. written from scratch..
// Supports put, getPtr, contains, erase, size, keys ..
// Rehashes automatically when load factor > 0.75 ..

template<typename K>
struct DefaultHasher {
    size_t operator()(const K& k) const {
        const unsigned char* p = reinterpret_cast<const unsigned char*>(&k);
        size_t h = 1469598103934665603ull; //offset
        for (size_t i = 0; i < sizeof(K); ++i) {
            h ^= (size_t)p[i];
            h *= 1099511628211ull;
        }
        return h;
    }
};

template<>
struct DefaultHasher<int> {
    size_t operator()(int x) const {
        uint32_t ux = static_cast<uint32_t>(x);
        ux *= 2654435761u;
        return static_cast<size_t>(ux);
    }
};

template<>
struct DefaultHasher<std::string> {
    size_t operator()(const std::string& s) const {
        uint64_t h = 1469598103934665603ull;
        for (unsigned char c : s) {
            h ^= (uint64_t)c;
            h *= 1099511628211ull;
        }
        return (size_t)h;
    }
};

template<typename K, typename V, typename Hasher = DefaultHasher<K> >
class HashMap {
private:
    struct Node {
        K key;
        V value;
        Node* next;
        Node(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
    };

    std::vector<Node*> buckets;
    size_t _size;
    Hasher hasher;

    float load_factor() const {
        return buckets.empty() ? 0.0f : (float)_size / (float)buckets.size();
    }

    void rehash(size_t new_cap) {
        std::vector<Node*> new_buckets(new_cap, nullptr);
        for (Node* head : buckets) {
            Node* cur = head;
            while (cur) {
                Node* nxt = cur->next;
                size_t idx = hasher(cur->key) % new_cap;
                cur->next = new_buckets[idx];
                new_buckets[idx] = cur;
                cur = nxt;
            }
        }
        buckets.swap(new_buckets);
    }

    Node* findNode(const K& key, size_t idx) const {
        Node* cur = buckets[idx];
        while (cur) {
            if (cur->key == key) return cur;
            cur = cur->next;
        }
        return nullptr;
    }

public:
    HashMap(size_t cap = 8) : buckets(cap, nullptr), _size(0), hasher() {}

    ~HashMap() {
        clear();
    }

    void clear() {
        for (Node* head : buckets) {
            Node* cur = head;
            while (cur) {
                Node* nxt = cur->next;
                delete cur;
                cur = nxt;
            }
        }
        buckets.assign(8, nullptr);
        _size = 0;
    }

    size_t size() const { return _size; }

    bool contains(const K& key) const {
        if (buckets.empty()) return false;
        size_t idx = hasher(key) % buckets.size();
        return findNode(key, idx) != nullptr;
    }

    V* getPtr(const K& key) {
        if (buckets.empty()) return nullptr;
        size_t idx = hasher(key) % buckets.size();
        Node* n = findNode(key, idx);
        if (!n) return nullptr;
        return &n->value;
    }

    const V* getPtr(const K& key) const {
        if (buckets.empty()) return nullptr;
        size_t idx = hasher(key) % buckets.size();
        Node* n = findNode(key, idx);
        if (!n) return nullptr;
        return &n->value;
    }

    void put(const K& key, const V& value) {
        if (buckets.empty()) buckets.assign(8, nullptr);
        if (load_factor() > 0.75f) {
            rehash(buckets.size() * 2);
        }
        size_t idx = hasher(key) % buckets.size();
        Node* cur = buckets[idx];
        while (cur) {
            if (cur->key == key) {
                cur->value = value;
                return;
            }
            cur = cur->next;
        }
        Node* n = new Node(key, value);
        n->next = buckets[idx];
        buckets[idx] = n;
        ++_size;
    }

    bool erase(const K& key) {
        if (buckets.empty()) return false;
        size_t idx = hasher(key) % buckets.size();
        Node* cur = buckets[idx];
        Node* prev = nullptr;
        while (cur) {
            if (cur->key == key) {
                if (prev) prev->next = cur->next;
                else buckets[idx] = cur->next;
                delete cur;
                --_size;
                return true;
            }
            prev = cur;
            cur = cur->next;
        }
        return false;
    }

    void keys(std::vector<K>& out) const {
        out.clear();
        out.reserve(_size);
        for (Node* head : buckets) {
            Node* cur = head;
            while (cur) {
                out.push_back(cur->key);
                cur = cur->next;
            }
        }
    }
};

#endif