map.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <stdexcept>
#include <string>
using namespace std;

template <typename K, typename V>
class map
{
private:
    struct Node
    {
        K key;
        V value;
        Node(const K &k, const V &v) : key(k), value(v) {}
    };

    vector<vector<Node>> buckets;
    size_t currentSize;
    double maxLoadFactor;

    size_t customHash(const string &key) const
    {
        const size_t p = 31;
        const size_t m = 1000000009ULL;
        size_t hashVal = 0;
        size_t p_pow = 1;

        for (char c : key)
        {
            hashVal = (hashVal + (c - 'a' + 1) * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }
        return hashVal;
    }

    size_t customHash(long long key) const
    {
        return (size_t)(key * 2654435761ULL);
    }

    size_t getBucketIndex(const K &key) const
    {
        if constexpr (is_same<K, string>::value)
            return customHash(key) % buckets.size();
        else if constexpr (is_integral<K>::value)
            return customHash((long long)key) % buckets.size();
        else
            throw runtime_error("Unsupported key type");
    }

    void rehash(size_t newBucketCount)
    {
        vector<vector<Node>> newBuckets(newBucketCount);

        for (auto &bucket : buckets)
        {
            for (auto &node : bucket)
            {
                size_t newIndex = getBucketIndex(node.key);
                newBuckets[newIndex].push_back(node);
            }
        }

        buckets.swap(newBuckets);
    }

public:
    map(size_t initBucketCount = 8, double loadFactor = 0.75)
        : buckets(initBucketCount), currentSize(0), maxLoadFactor(loadFactor) {}

    bool count(const K &key) const
    {
        size_t idx = getBucketIndex(key);
        for (const auto &node : buckets[idx])
        {
            if (node.key == key)
                return true;
        }
        return false;
    }

    V &operator[](const K &key)
    {
        size_t idx = getBucketIndex(key);

        for (auto &node : buckets[idx])
        {
            if (node.key == key)
                return node.value;
        }

        if ((double)(currentSize + 1) / buckets.size() > maxLoadFactor)
        {
            rehash(buckets.size() * 2);
            idx = getBucketIndex(key);
        }

        buckets[idx].emplace_back(key, V{});
        currentSize++;
        return buckets[idx].back().value;
    }

    void insert(const K &key, const V &value)
    {
        size_t idx = getBucketIndex(key);

        for (auto &node : buckets[idx])
        {
            if (node.key == key)
            {
                node.value = value;
                return;
            }
        }

        if ((double)(currentSize + 1) / buckets.size() > maxLoadFactor)
        {
            rehash(buckets.size() * 2);
            idx = getBucketIndex(key);
        }

        buckets[idx].emplace_back(key, value);
        currentSize++;
    }

    void erase(const K &key)
    {
        size_t idx = getBucketIndex(key);
        auto &bucket = buckets[idx];

        for (size_t i = 0; i < bucket.size(); i++)
        {
            if (bucket[i].key == key)
            {
                bucket[i] = bucket.back(); // swap with last
                bucket.pop_back();         // remove last
                currentSize--;
                return;
            }
        }
    }

    size_t size() const
    {
        return currentSize;
    }

    bool empty() const
    {
        return currentSize == 0;
    }

    vector<pair<K, V>> items() const
    {
        vector<pair<K, V>> all;
        all.reserve(currentSize);
        for (const auto &bucket : buckets)
        {
            for (const auto &node : bucket)
            {
                all.push_back({node.key, node.value});
            }
        }
        return all;
    }
};