C++ unordered_map — Bad Hash Silently Kills Server

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

int main() {
    // --- unordered_map: count word frequencies in a document ---
    std::vector<std::string> words = {
        "apple", "banana", "apple", "cherry",
        "banana", "apple", "date", "cherry"
    };

    // Reserve buckets upfront to avoid mid-run rehashing.
    // Rule of thumb: reserve at least as many buckets as you expect elements.
    std::unordered_map<std::string, int> wordCount;
    wordCount.reserve(words.size());

    for (const auto& word : words) {
        // operator[] inserts a zero-initialized value if key is absent,
        // then increments it. Clean idiom for counting.
        wordCount[word]++;
    }

    std::cout << "=== Word Frequencies ===\n";
    for (const auto& [word, count] : wordCount) {
        // Note: iteration order is NOT alphabetical — it's bucket order.
        std::cout << word << ": " << count << "\n";
    }

    // --- unordered_set: fast duplicate detection ---
    std::vector<std::string> emails = {
        "alice@example.com", "bob@example.com",
        "alice@example.com", "carol@example.com"
    };

    std::unordered_set<std::string> seen;
    std::cout << "\n=== Duplicate Emails ===\n";
    for (const auto& email : emails) {
        // insert() returns a pair<iterator, bool>.
        // The bool is false if the element already existed.
        auto [it, inserted] = seen.insert(email);
        if (!inserted) {
            std::cout << "Duplicate found: " << email << "\n";
        }
    }

    // --- Inspecting internal state ---
    std::cout << "\n=== Internal State of wordCount ===\n";
    std::cout << "Bucket count : " << wordCount.bucket_count() << "\n";
    std::cout << "Load factor  : " << wordCount.load_factor() << "\n";
    std::cout << "Max load factor: " << wordCount.max_load_factor() << "\n";

    return 0;
}

} // namespace io::thecodeforge

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <string>

// A 2D grid coordinate — used in game maps, image processing, pathfinding.
struct GridCell {
    int row;
    int col;

    // The container also needs to know when two keys are EQUAL.
    // Without this, it can't resolve collisions correctly.
    bool operator==(const GridCell& other) const {
        return row == other.row && col == other.col;
    }
};

// Custom hash functor for GridCell.
// We combine the hashes of both fields using the hash_combine pattern.
// This avoids the symmetry problem of plain XOR.
struct GridCellHash {
    std::size_t operator()(const GridCell& cell) const {
        std::size_t rowHash = std::hash<int>{}(cell.row);
        std::size_t colHash = std::hash<int>{}(cell.col);

        // This magic number (0x9e3779b9) is derived from the golden ratio.
        // It spreads bits in a way that minimises clustering in the bucket array.
        // This is the same technique used by Boost and Abseil internally.
        return rowHash ^ (colHash + 0x9e3779b9 + (rowHash << 6) + (rowHash >> 2));
    }
};

int main() {
    // Pass GridCellHash as the third template argument (the hasher).
    // The fourth argument (std::equal_to by default) uses our operator==.
    std::unordered_map<GridCell, std::string, GridCellHash> terrainMap;

    terrainMap[{0, 0}] = "Forest";
    terrainMap[{0, 1}] = "Mountain";
    terrainMap[{1, 0}] = "River";
    terrainMap[{3, 7}] = "Desert";

    // Look up terrain at a specific coordinate — O(1) average.
    GridCell target = {1, 0};
    auto it = terrainMap.find(target);

    if (it != terrainMap.end()) {
        std::cout << "Terrain at (1,0): " << it->second << "\n";
    }

    // Prove that (0,1) and (1,0) are distinct keys — XOR alone would collide here.
    std::cout << "Terrain at (0,1): " << terrainMap[{0, 1}] << "\n";
    std::cout << "Total cells mapped: " << terrainMap.size() << "\n";

    return 0;
}

} // namespace io::thecodeforge

namespace io::thecodeforge {

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>
#include <chrono>
#include <random>

// Helper to time a block of code in microseconds.
auto timeIt(auto&& fn) {
    auto start = std::chrono::high_resolution_clock::now();
    fn();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
}

int main() {
    const int NUM_PLAYERS = 100'000;
    std::mt19937 rng(42); // Fixed seed for reproducibility.
    std::uniform_int_distribution<int> scoreDist(1, 1'000'000);

    // Build player ID -> score maps.
    std::map<int, int>           orderedLeaderboard;
    std::unordered_map<int, int> fastLeaderboard;
    fastLeaderboard.reserve(NUM_PLAYERS);

    // --- Insertion timing ---
    auto orderedInsertTime = timeIt([&]() {
        for (int id = 0; id < NUM_PLAYERS; ++id)
            orderedLeaderboard[id] = scoreDist(rng);
    });

    rng.seed(42); // Reset so both maps get identical data.
    auto unorderedInsertTime = timeIt([&]() {
        for (int id = 0; id < NUM_PLAYERS; ++id)
            fastLeaderboard[id] = scoreDist(rng);
    });

    // --- Lookup timing: 100k random lookups ---
    std::uniform_int_distribution<int> idDist(0, NUM_PLAYERS - 1);
    volatile int sink = 0; // Prevent the compiler from optimising the loop away.

    auto orderedLookupTime = timeIt([&]() {
        for (int i = 0; i < NUM_PLAYERS; ++i)
            sink += orderedLeaderboard[idDist(rng)];
    });

    auto unorderedLookupTime = timeIt([&]() {
        for (int i = 0; i < NUM_PLAYERS; ++i)
            sink += fastLeaderboard[idDist(rng)];
    });

    std::cout << "=== Insertion (100k elements) ===\n";
    std::cout << "std::map        : " << orderedInsertTime   << " us\n";
    std::cout << "std::unordered_map: " << unorderedInsertTime << " us\n";

    std::cout << "\n=== Lookup (100k random) ===\n";
    std::cout << "std::map        : " << orderedLookupTime   << " us\n";
    std::cout << "std::unordered_map: " << unorderedLookupTime << " us\n";

    // std::map shines here: iterate in ascending player ID order — free with map.
    std::cout << "\n=== Top 3 Players by ID (ordered iteration — only map can do this) ===\n";
    int count = 0;
    for (const auto& [id, score] : orderedLeaderboard) {
        std::cout << "Player " << id << " -> Score: " << score << "\n";
        if (++count == 3) break;
    }

    return 0;
}

} // namespace io::thecodeforge

+---------------------------+---------------------------+-------------------------------+-------------------------------+
| Aspect                   | std::map                  | std::unordered_map            | std::set                      | std::unordered_set            |
+---------------------------+---------------------------+-------------------------------+-------------------------------+
| Underlying structure     | Red-Black Tree            | Hash table (chaining)         | Red-Black Tree                | Hash table (chaining)         |
| Ordering                 | Sorted ascending by key   | None (bucket order)           | Sorted ascending by key       | None (bucket order)           |
| Lookup average           | O(log n)                  | O(1)                          | O(log n)                      | O(1)                          |
| Lookup worst case        | O(log n)                  | O(n)                          | O(log n)                      | O(n)                          |
| Insert average           | O(log n)                  | O(1) amortized                | O(log n)                      | O(1) amortized                |
| Insert worst case        | O(log n)                  | O(n) during rehash            | O(log n)                      | O(n) during rehash            |
| Memory overhead          | ~48 bytes per entry       | ~40 bytes per entry + buckets | ~40 bytes per entry           | ~32 bytes per entry + buckets |
| Range queries            | Yes (lower_bound/upper)   | No                            | Yes (lower_bound/upper)       | No                            |
| Min / Max key            | O(log n) via begin/rbegin | Not available                 | O(log n) via begin/rbegin     | Not available                 |
| Custom key requirements  | operator<                 | std::hash + operator==        | operator<                     | std::hash + operator==        |
| Iterator invalidation (insert) | No                               | Yes if rehash                          | No                                     | Yes if rehash                        |
| Iterator invalidation (erase)  | Only erased                       | Only erased                          | Only erased                         | Only erased                        |
| Thread safety            | None                       | None                            | None                           | None                            |
+---------------------------+---------------------------+-------------------------------+-------------------------------+

Note: Memory overhead values are approximate and implementation-dependent. The hash table's bucket array can add significant fixed overhead, especially for small containers.

== unordered_map ==

Category            | Member Function               | Average      | Worst Case    | Notes
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Element access      | at(key)                       | O(1)         | O(n)          | Throws if key missing
                    | operator[](key)                | O(1)         | O(n)          | Inserts default if key missing
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Lookup              | find(key)                     | O(1)         | O(n)          | Returns iterator or end()
                    | count(key)                    | O(1)         | O(n)          | Returns 0 or 1
                    | contains(key) (C++20)         | O(1)         | O(n)          | Returns bool
                    | equal_range(key)              | O(1)         | O(n)          | Returns pair of iterators
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Capacity            | empty()                       | O(1)         | O(1)          | 
                    | size()                        | O(1)         | O(1)          | 
                    | max_size()                    | O(1)         | O(1)          | 
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Modifiers           | insert(pair)                  | O(1)         | O(n)          | Rehash may occur
                    | insert(hint, pair)            | O(1)         | O(n)          | Hint ignored
                    | insert_or_assign(key, val)    | O(1)         | O(n)          | C++17
                    | try_emplace(key, args...)     | O(1)         | O(n)          | C++17
                    | emplace(args...)              | O(1)         | O(n)          | 
                    | emplace_hint(hint, args...)   | O(1)         | O(n)          | Hint ignored
                    | erase(iterator)               | O(1) average | O(1)          | Does not invalidate other iterators
                    | erase(key)                    | O(1)         | O(n)          | Returns number of erased elements
                    | erase(first, last)            | O(k)         | O(n)          | k = distance
                    | swap(other)                   | O(1)         | O(1)          | Swaps pointers
                    | clear()                       | O(n)         | O(n)          | Destroys all elements
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Modifiers (rehash)  | rehash(n)                     | O(n)         | O(n)          | Sets bucket count to at least n
                    | reserve(n)                    | O(n)         | O(n)          | Ensures capacity for n elements without rehash
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Bucket interface    | bucket_count()                | O(1)         | O(1)          | Number of buckets
                    | max_bucket_count()             | O(1)         | O(1)          | Implementation-defined max
                    | bucket_size(i)                | O(b)         | O(b)          | Elements in bucket i (b = bucket size)
                    | bucket(key)                   | O(1)         | O(1)          | Bucket index for key
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Hash policy         | load_factor()                 | O(1)         | O(1)          | size() / bucket_count()
                    | max_load_factor()             | O(1)         | O(1)          | Get threshold
                    | max_load_factor(float)        | O(1)         | O(1)          | Set threshold (default 1.0)
--------------------|-------------------------------|--------------|---------------|----------------------------------------
Observers           | hash_function()               | O(1)         | O(1)          | Returns the hash functor
                    | key_eq()                      | O(1)         | O(1)          | Returns the equality functor
                    | get_allocator()               | O(1)         | O(1)          | 


== unordered_set ==

Same as unordered_map but without element access (at, operator[]). Lookup functions find/count/contains work on the key directly. The rest of the interface is identical with Key being both the key and the element.

Note: Worst-case O(n) for lookups/inserts occurs when all keys hash to the same bucket. This can be caused by a poor hash, high load factor, or deliberate hash-flooding attack.

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <string>
#include <random>

// A deliberately poor hash that clusters all keys ending in same digit.
struct BadHash {
    std::size_t operator()(const std::string& s) const {
        if (s.empty()) return 0;
        return s.back(); // last character only = terrible distribution
    }
};

int main() {
    std::unordered_map<std::string, int, BadHash> map;
    // Insert 100 strings with distinct last characters to spread them? No – they share few.
    // Let's just see bucket distribution.
    map["cat"] = 1;
    map["dog"] = 2;
    map["bird"] = 3;
    map["fish"] = 4;
    map["rabbit"] = 5;
    map["hamster"] = 6;

    std::cout << "Bucket count: " << map.bucket_count() << "\n";
    for (size_t i = 0; i < map.bucket_count(); ++i) {
        std::cout << "Bucket " << i << ": " << map.bucket_size(i) << " elements\n";
    }
    // With BadHash using last char, all keys ending in same char collide.
    // 'cat', 'rabbit', 'hamster' all end in 't' (well, 't' 't' 'r'? Actually cat->t, rabbit->t, hamster->r) – you get the idea.
    return 0;
}

} // namespace io::thecodeforge

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <thread>
#include <string>
#include <mutex>

std::unordered_map<int, std::string> map;
std::mutex mtx;

void writer() {
    for (int i = 0; i < 1000; ++i) {
        std::lock_guard<std::mutex> lock(mtx); // WITHOUT LOCK: data race
        map[i] = "value" + std::to_string(i);
    }
}

void reader() {
    for (int i = 0; i < 1000; ++i) {
        std::lock_guard<std::mutex> lock(mtx); // WITHOUT LOCK: undefined behavior
        auto it = map.find(i);
        if (it != map.end()) {
            // safe read within lock
        }
    }
}

int main() {
    std::thread t1(writer);
    std::thread t2(reader);
    t1.join();
    t2.join();
    return 0;
}

} // namespace io::thecodeforge

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<int, std::string> map;
    map[1] = "one";
    auto it = map.find(1);
    std::cout << "Initial bucket count: " << map.bucket_count() << "\n";
    std::cout << "Inserted key 1, value: " << it->second << "\n";

    // Now insert many keys to force a rehash
    for (int i = 2; i < 100; ++i) {
        map[i] = std::to_string(i);
    }
    std::cout << "After many inserts, bucket count: " << map.bucket_count() << "\n";

    // The old iterator 'it' is now invalid!
    // Dereferencing it is undefined behavior — it may crash or give wrong data.
    // In practice, it might still work if memory hasn't been overwritten, but don't rely on it.
    // std::cout << it->second; // BAD: undefined behavior

    // Correct approach: re-obtain the iterator after all inserts
    auto valid_it = map.find(1);
    if (valid_it != map.end()) {
        std::cout << "After rehash, key 1 still exists with value: " << valid_it->second << "\n";
    }

    return 0;
}

} // namespace io::thecodeforge

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>

// Problem 1: Two Sum
// Given an array of integers and a target, return indices of the two numbers that add up to target.
// Uses unordered_map to store complement -> index. O(n) time, O(n) space.
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map; // value -> index
    for (int i = 0; i < (int)nums.size(); ++i) {
        int complement = target - nums[i];
        auto it = map.find(complement);
        if (it != map.end()) {
            return {it->second, i};
        }
        map[nums[i]] = i;
    }
    return {};
}

// Problem 2: Group Anagrams
// Given a list of strings, group anagrams together.
// Uses unordered_map with sorted string as key. O(n * k log k) time where k is max string length.
std::vector<std::vector<std::string>> groupAnagrams(const std::vector<std::string>& strs) {
    std::unordered_map<std::string, std::vector<std::string>> groups;
    for (const auto& s : strs) {
        std::string sorted = s;
        std::sort(sorted.begin(), sorted.end());
        groups[sorted].push_back(s);
    }
    std::vector<std::vector<std::string>> result;
    for (auto& [key, group] : groups) {
        result.push_back(std::move(group));
    }
    return result;
}

// Problem 3: Contains Duplicate II
// Check if there are two distinct indices i and j such that nums[i] == nums[j] and |i - j| <= k.
// Uses unordered_set to maintain a sliding window of size k. O(n) time, O(k) space.
bool containsNearbyDuplicate(const std::vector<int>& nums, int k) {
    std::unordered_set<int> window;
    for (int i = 0; i < (int)nums.size(); ++i) {
        if (window.count(nums[i])) {
            return true;
        }
        window.insert(nums[i]);
        if ((int)window.size() > k) {
            window.erase(nums[i - k]);
        }
    }
    return false;
}

// Problem 4: Intersection of Two Arrays
// Return unique elements common to both arrays.
// Uses unordered_set for O(n) time.
std::vector<int> intersection(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    std::unordered_set<int> set1(nums1.begin(), nums1.end());
    std::unordered_set<int> result;
    for (int x : nums2) {
        if (set1.count(x)) {
            result.insert(x);
        }
    }
    return std::vector<int>(result.begin(), result.end());
}

int main() {
    // Test Two Sum
    std::vector<int> nums1 = {2, 7, 11, 15};
    auto res1 = twoSum(nums1, 9);
    std::cout << "Two Sum: " << res1[0] << ", " << res1[1] << "\n";

    // Test Group Anagrams
    std::vector<std::string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    auto groups = groupAnagrams(words);
    std::cout << "Group Anagrams:\n";
    for (const auto& g : groups) {
        for (const auto& s : g) std::cout << s << " ";
        std::cout << "\n";
    }

    // Test Contains Duplicate II
    std::vector<int> nums2 = {1, 2, 3, 1, 2, 3};
    std::cout << "Contains near duplicate (k=2): " << containsNearbyDuplicate(nums2, 2) << "\n";
    std::cout << "Contains near duplicate (k=3): " << containsNearbyDuplicate(nums2, 3) << "\n";

    // Test Intersection
    std::vector<int> a = {4, 9, 5};
    std::vector<int> b = {9, 4, 9, 8, 4};
    auto inter = intersection(a, b);
    std::cout << "Intersection: ";
    for (int x : inter) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

} // namespace io::thecodeforge

namespace io::thecodeforge {

#include <iostream>
#include <unordered_map>
#include <memory_resource> // pmr
#include <cstddef>

int main() {
    // Allocate a fixed-size buffer on the stack for memory pooling
    std::byte buffer[2048];
    std::pmr::monotonic_buffer_resource pool(buffer, sizeof(buffer));

    // Create an unordered_map using the pool
    std::pmr::unordered_map<int, std::string> map(&pool);

    // Insert elements — no heap allocations after initial pool setup
    map[1] = "one";
    map[2] = "two";
    map[3] = "three"; // All allocated from 'buffer'

    std::cout << "Map size: " << map.size() << "\n";
    std::cout << "Bucket count: " << map.bucket_count() << "\n";

    // Note: monotonic_buffer_resource does NOT deallocate individual elements.
    // Memory is reclaimed when 'pool' goes out of scope.
    return 0;
}

} // namespace io::thecodeforge

// io.thecodeforge — c-cpp tutorial

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> cache;

    // Typical trap: growing incrementally
    for (int i = 0; i < 100000; ++i) {
        cache[i] = "value";
    }
    std::cout << "bucket_count after growth: " << cache.bucket_count() << "\n";

    // Senior fix: reserve known capacity
    std::unordered_map<int, std::string> smart_cache;
    smart_cache.reserve(100000);
    for (int i = 0; i < 100000; ++i) {
        smart_cache[i] = "value";
    }
    std::cout << "bucket_count after reserve: " << smart_cache.bucket_count() << "\n";

    return 0;
}

// io.thecodeforge — c-cpp tutorial

#include <unordered_map>
#include <string>
#include <iostream>

// djb2 — simple, fast, good avalanche
struct StringHasher {
    std::size_t operator()(const std::string& key) const noexcept {
        std::size_t hash = 5381;
        for (char c : key) {
            hash = ((hash << 5) + hash) + static_cast<unsigned char>(c);
        }
        return hash;
    }
};

int main() {
    std::unordered_map<std::string, int, StringHasher> token_counts;
    token_counts["auth_token"] = 1;
    token_counts["refresh_token"] = 2;
    token_counts["access_token"] = 3;

    std::cout << "Bucket count: " << token_counts.bucket_count() << "\n";
    std::cout << "Max bucket size: " << token_counts.bucket_size(0) << "\n";
    return 0;
}

// io.theforgecode — c-cpp tutorial

#include <unordered_map>
#include <iostream>

struct BadHash {
    size_t operator()(int i) const { return i; }
};

int main() {
    // Zero rehashes — reserve up front
    std::unordered_map<int, std::string> ids;
    ids.reserve(5000);
    for (int i = 0; i < 5000; ++i)
        ids[i] = "user_" + std::to_string(i);

    // Initializer list — fine for small static data
    std::unordered_map<std::string, int> ages{{"alice", 30}, {"bob", 25}};

    // Custom hash + initial bucket count
    std::unordered_map<int, std::string, BadHash> custom(100, BadHash{});

    std::cout << "Buckets: " << ids.bucket_count() << '\n';
    return 0;
}

// io.theforgecode — c-cpp tutorial

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> m{{1,"a"}, {2,"b"}, {3,"c"}};

    // SAFE ERASE WHILE TRAVERSING
    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first % 2 == 0)    // remove evens
            it = m.erase(it);      // returns next valid iterator
        else
            ++it;
    }

    for (const auto& [k, v] : m)
        std::cout << k << ": " << v << '\n';
    return 0;
}