Hash Table, Hash Map & Hash Set Architectures

Topics Covered:
41. Hash Table Architecture & Dynamic Rehashing • 42. Hash Map (Key-Value Associative Dictionaries, Invariants & Entry Sets) • Production Collision Optimizations (Java 8+ Bucket Treeification & Python Compact Hash Tables) • 43. Hash Set (Deduplication Engine, Backing Mechanics & Mathematical Set Operations) • 44. Master Comparison: Hash Table vs Hash Map vs Hash Set vs Tree Structures

Associative data structures represent the backbone of practical software engineering, powering database primary keys, symbol tables, routing caches, and in-memory key-value stores. While Hash Tables, Hash Maps, and Hash Sets are often used interchangeably in colloquial discussion, they embody distinct mathematical contracts, memory representations, and concurrency profiles. This chapter examines the core mechanics of associative arrays, dynamic rehashing invariants, modern runtime defenses against Hash-DoS attacks (such as Java 8+ bucket treeification and Python 3.6+ compact sparse/dense layouts), mathematical set algebra algorithms, and trade-offs against tree-based structures.

• Differentiate Hash Tables, Hash Maps, and Hash Sets by their formal mathematical invariants, interface contracts, and physical memory configurations.
• Implement dynamic table rehashing and prove why existing elements must be recomputed via $h(k)(\mathrm{mod}{m}_{\text{new}})$ rather than copied verbatim.
• Analyze production engine optimizations that foil Hash DoS attacks, including Java 8+ Red-Black tree bucket treeification and Python 3.6+ compact indices.
• Construct a Hash Set as an abstraction over an internal Hash Map with sentinel constants and determine optimal time complexities for set operations ($\cap ,\cup ,\setminus$).
• Evaluate the asymptotic and practical performance trade-offs between hash-based associative containers and self-balancing binary search trees.

C++20 Templated Hash Map with Separate Chaining & RAII

#include <vector>
#include <list>
#include <utility>
#include <stdexcept>
#include <optional>

template <typename K, typename V>
class ChainedHashMap {
private:
    struct Entry {
        K key;
        V value;
    };

    std::vector<std::list<Entry>> buckets_;
    size_t capacity_;
    size_t size_;
    float max_load_factor_;

    size_t bucket_index(const K& key) const {
        return std::hash<K>{}(key) % capacity_;
    }

    void rehash(size_t new_cap) {
        std::vector<std::list<Entry>> new_buckets(new_cap);
        for (const auto& bucket : buckets_) {
            for (const auto& entry : bucket) {
                size_t idx = std::hash<K>{}(entry.key) % new_cap;
                new_buckets[idx].push_back(entry);
            }
        }
        buckets_ = std::move(new_buckets);
        capacity_ = new_cap;
    }

public:
    explicit ChainedHashMap(size_t initial_cap = 11, float mlf = 0.75f)
        : capacity_(initial_cap), size_(0), max_load_factor_(mlf), buckets_(initial_cap) {}

    void insert(const K& key, const V& value) {
        if (static_cast<float>(size_ + 1) / capacity_ > max_load_factor_) {
            rehash(capacity_ * 2 + 1);
        }
        size_t idx = bucket_index(key);
        for (auto& entry : buckets_[idx]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        buckets_[idx].push_back({key, value});
        ++size_;
    }

    std::optional<V> get(const K& key) const {
        size_t idx = bucket_index(key);
        for (const auto& entry : buckets_[idx]) {
            if (entry.key == key) return entry.value;
        }
        return std::nullopt;
    }

    bool remove(const K& key) {
        size_t idx = bucket_index(key);
        auto& bucket = buckets_[idx];
        for (auto it = bucket.begin(); it != bucket.end(); ++it) {
            if (it->key == key) {
                bucket.erase(it);
                --size_;
                return true;
            }
        }
        return false;
    }

    [[nodiscard]] size_t size() const noexcept { return size_; }
    [[nodiscard]] bool empty() const noexcept { return size_ == 0; }
};

1. Rehashing Mechanics: Dynamic rehashing requires recomputing new index slots for all existing elements via $h(k)(\mathrm{mod}{m}_{\text{new}})$; simple memory copying is invalid.
2. Treeification: Java 8+ converts long bucket chains ($\ge 8$) to Red-Black trees, strictly foiling algorithmic Hash-DoS attacks.
3. Compact Hash Tables: Decoupling sparse indices from dense entries (Python 3.6+) eliminates empty gap memory waste and preserves insertion order.
4. Set Optimization: Hash Sets reuse Hash Map key machinery with dummy sentinels; set intersection achieves optimal $O(\min (n,m))$ time by driving lookups from the smaller set.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 11: Hash Tables, Chapter 13: Red-Black Trees. MIT Press.
2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Section 6.4: Hashing. Addison-Wesley.
3. Hettinger, R. (2012). Modern Dictionaries by More Compact Means. Python Developers Conference (PyCon).