Insertions 1..m:       m insertions, each O(1)          = O(m)
Rehash at m:           reinsert m elements               = O(m)
Insertions m+1..2m:    m insertions, each O(1)          = O(m)
Rehash at 2m:          reinsert 2m elements              = O(2m)
...

Total cost for n insertions = n + (n/2 + n/4 + n/8 + ... + 1) = n + n = O(n)
Amortized cost per insertion = O(n) / n = O(1)

Slots: [22, 88, _, _, 4, 15, 28, 17, _, 31, 10]
                                     Indices: 0-10

Suppose 88 was placed at index 1 because 0 was occupied (linear probing).
If we delete 22 (index 0):

Slots: [ _, 88, _, _, 4, 15, 28, 17, _, 31, 10]

Now search for 88: h(88)=0, slot 0 is empty --> "88 not found!" WRONG!

Slots: [DEL, 88, _, _, 4, 15, 28, 17, _, 31, 10]

Search for 88: h(88)=0, slot 0 is DEL (skip), slot 1 has 88 --> found!

#include <bits/stdc++.h>
using namespace std;

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

    vector<Node*> buckets;
    int sz;
    int capacity;
    float maxLoadFactor;

    int getBucket(const K& key) const {
        return std::hash<K>{}(key) % capacity;
    }

    void rehash() {
        int oldCap = capacity;
        capacity *= 2;
        vector<Node*> oldBuckets = move(buckets);
        buckets.assign(capacity, nullptr);
        sz = 0;

        for (int i = 0; i < oldCap; i++) {
            Node* curr = oldBuckets[i];
            while (curr) {
                put(curr->key, curr->value);
                Node* temp = curr;
                curr = curr->next;
                delete temp;
            }
        }
    }

public:
    HashMap(int cap = 16) : capacity(cap), sz(0), maxLoadFactor(0.75f) {
        buckets.assign(capacity, nullptr);
    }

    ~HashMap() {
        for (int i = 0; i < capacity; i++) {
            Node* curr = buckets[i];
            while (curr) {
                Node* temp = curr;
                curr = curr->next;
                delete temp;
            }
        }
    }

    // Insert or update
    void put(const K& key, const V& value) {
        if ((float)sz / capacity >= maxLoadFactor) {
            rehash();
        }

        int idx = getBucket(key);
        Node* curr = buckets[idx];

        // Check if key already exists -- update
        while (curr) {
            if (curr->key == key) {
                curr->value = value;
                return;
            }
            curr = curr->next;
        }

        // Key not found -- prepend new node (O(1) insertion)
        Node* newNode = new Node(key, value);
        newNode->next = buckets[idx];
        buckets[idx] = newNode;
        sz++;
    }

    // Lookup -- returns pointer to value, or nullptr if not found
    V* get(const K& key) {
        int idx = getBucket(key);
        Node* curr = buckets[idx];
        while (curr) {
            if (curr->key == key) return &curr->value;
            curr = curr->next;
        }
        return nullptr;
    }

    // Delete -- returns true if key was found and removed
    bool remove(const K& key) {
        int idx = getBucket(key);
        Node* curr = buckets[idx];
        Node* prev = nullptr;

        while (curr) {
            if (curr->key == key) {
                if (prev) prev->next = curr->next;
                else buckets[idx] = curr->next;
                delete curr;
                sz--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false;
    }

    bool contains(const K& key) {
        return get(key) != nullptr;
    }

    int size() const { return sz; }
    bool empty() const { return sz == 0; }

    // Operator [] for convenient access (inserts default if missing)
    V& operator[](const K& key) {
        V* val = get(key);
        if (val) return *val;
        put(key, V{});
        return *get(key);
    }
};

// Usage example
int main() {
    HashMap<string, int> map;
    map.put("apple", 5);
    map.put("banana", 3);
    map.put("cherry", 7);

    cout << *map.get("apple") << endl;   // 5
    cout << map["banana"] << endl;       // 3
    map.remove("cherry");
    cout << map.contains("cherry") << endl;  // 0 (false)

    // Overwrite
    map.put("apple", 10);
    cout << *map.get("apple") << endl;   // 10

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

template<typename K, typename V>
class OpenAddressMap {
    enum SlotState { EMPTY, OCCUPIED, DELETED };

    struct Slot {
        K key;
        V value;
        SlotState state = EMPTY;
    };

    vector<Slot> table;
    int sz;
    int capacity;

    int getBucket(const K& key) const {
        return std::hash<K>{}(key) % capacity;
    }

    void rehash() {
        vector<Slot> oldTable = move(table);
        capacity *= 2;
        table.assign(capacity, Slot());
        sz = 0;
        for (auto& slot : oldTable) {
            if (slot.state == OCCUPIED)
                put(slot.key, slot.value);
        }
    }

public:
    OpenAddressMap(int cap = 16) : capacity(cap), sz(0) {
        table.assign(capacity, Slot());
    }

    void put(const K& key, const V& value) {
        if (sz * 2 >= capacity) rehash();   // keep alpha < 0.5

        int idx = getBucket(key);
        int firstDeleted = -1;

        for (int i = 0; i < capacity; i++) {
            int probe = (idx + i) % capacity;

            if (table[probe].state == EMPTY) {
                int target = (firstDeleted != -1) ? firstDeleted : probe;
                table[target] = {key, value, OCCUPIED};
                sz++;
                return;
            }
            if (table[probe].state == DELETED && firstDeleted == -1) {
                firstDeleted = probe;
            }
            if (table[probe].state == OCCUPIED && table[probe].key == key) {
                table[probe].value = value;  // update existing
                return;
            }
        }

        // Table is full (shouldn't happen with proper rehashing)
        if (firstDeleted != -1) {
            table[firstDeleted] = {key, value, OCCUPIED};
            sz++;
        }
    }

    V* get(const K& key) {
        int idx = getBucket(key);
        for (int i = 0; i < capacity; i++) {
            int probe = (idx + i) % capacity;
            if (table[probe].state == EMPTY) return nullptr;
            if (table[probe].state == OCCUPIED && table[probe].key == key)
                return &table[probe].value;
            // If DELETED, keep probing
        }
        return nullptr;
    }

    bool remove(const K& key) {
        int idx = getBucket(key);
        for (int i = 0; i < capacity; i++) {
            int probe = (idx + i) % capacity;
            if (table[probe].state == EMPTY) return false;
            if (table[probe].state == OCCUPIED && table[probe].key == key) {
                table[probe].state = DELETED;   // tombstone
                sz--;
                return true;
            }
        }
        return false;
    }
};

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        // XOR with a random seed so the hash is unpredictable
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Usage:
unordered_map<int, int, custom_hash> safe_map;

struct pair_hash {
    size_t operator()(const pair<int,int>& p) const {
        auto h1 = custom_hash{}(p.first);
        auto h2 = custom_hash{}(p.second);
        return h1 ^ (h2 << 32);  // combine hashes
    }
};

unordered_map<pair<int,int>, int, pair_hash> pairMap;

// Reserve capacity upfront to avoid rehashing
unordered_map<int, int, custom_hash> mp;
mp.reserve(1 << 20);           // reserve 2^20 buckets
mp.max_load_factor(0.25);      // lower load factor = fewer collisions

// For small key ranges, use a plain array instead!
int freq[1000001] = {};        // much faster than unordered_map

// WRONG -- undefined behavior!
for (auto it = mp.begin(); it != mp.end(); ++it) {
    if (it->second == 0) mp.erase(it);  // invalidates iterator!
}

// CORRECT
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->second == 0) it = mp.erase(it);
    else ++it;
}

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // value -> index
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};  // no solution
}
// Time: O(n), Space: O(n)

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (auto& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& [key, group] : groups) {
        result.push_back(move(group));
    }
    return result;
}
// Time: O(n * k log k) where k is max string length
// Space: O(n * k)

string getKey(const string& s) {
    int count[26] = {};
    for (char c : s) count[c - 'a']++;
    string key;
    for (int i = 0; i < 26; i++) {
        key += '#';
        key += to_string(count[i]);
    }
    return key;
}
// Now grouping is O(n * k) instead of O(n * k log k)

class LRUCache {
    int capacity;
    list<pair<int,int>> dll;                         // {key, value}
    unordered_map<int, list<pair<int,int>>::iterator> map;  // key -> iterator

    void moveToFront(int key, int value) {
        if (map.count(key)) dll.erase(map[key]);
        dll.push_front({key, value});
        map[key] = dll.begin();
    }

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (!map.count(key)) return -1;
        int val = map[key]->second;
        moveToFront(key, val);
        return val;
    }

    void put(int key, int value) {
        moveToFront(key, value);
        if ((int)map.size() > capacity) {
            int lruKey = dll.back().first;
            dll.pop_back();
            map.erase(lruKey);
        }
    }
};
// All operations O(1)

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> prefixCount;
    prefixCount[0] = 1;  // empty prefix has sum 0
    int sum = 0, count = 0;
    for (int x : nums) {
        sum += x;
        if (prefixCount.count(sum - k))
            count += prefixCount[sum - k];
        prefixCount[sum]++;
    }
    return count;
}
// Time: O(n), Space: O(n)