{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "dataset": {
        "id": 418,
        "slug": "hash-tables",
        "title": "Hash Tables & Hash Functions",
        "description": "Hash table implementations, collision resolution strategies, hash functions, load factor, and performance characteristics.",
        "category": "Data Structures",
        "category_slug": "data-structures",
        "tags": "hash-tables,dictionaries,associative-arrays,collision-resolution,hashing",
        "view_count": 4,
        "created_at": 1781275786,
        "updated_at": 1781275786
    },
    "data": {
        "core_concepts": [
            {
                "component": "Hash Function",
                "purpose": "Maps arbitrary key to integer index in hash table array",
                "properties": [
                    "Deterministic (same key \u2192 same hash)",
                    "Fast to compute",
                    "Uniform distribution",
                    "Minimizes collisions"
                ],
                "common_functions": [
                    "MurmurHash3",
                    "CityHash",
                    "FNV-1a",
                    "SHA-256 (cryptographic, slow)",
                    "MD5 (cryptographic, deprecated)"
                ],
                "example": "h(k) = (a \u00d7 k + b) mod m (affine hash for integers)",
                "notes": "Cryptographic hashes (SHA, MD5) are slow; non-cryptographic preferred for hash tables"
            },
            {
                "component": "Load Factor (\u03b1)",
                "definition": "Ratio of number of entries to number of buckets (n \/ m)",
                "threshold": "Typically 0.75 for separate chaining, 0.5-0.7 for open addressing",
                "rehashing": "When \u03b1 exceeds threshold, resize table (usually double) and rehash all entries",
                "time_impact": "Amortized O(1) if resizing infrequent; worst-case O(n) during resize",
                "notes": "Higher \u03b1 \u2192 more collisions, slower lookups; lower \u03b1 \u2192 wasted memory"
            },
            {
                "component": "Collision Resolution",
                "strategies": [
                    "Separate Chaining",
                    "Open Addressing (Linear\/Quadratic\/Double Hashing)"
                ],
                "description": "Method to handle multiple keys mapping to same bucket index"
            }
        ],
        "collision_strategies": {
            "separate_chaining": {
                "structure": "Each bucket is linked list (or tree) of entries; hash(key) \u2192 bucket index \u2192 traverse list",
                "complexity": {
                    "avg_search": "O(1 + \u03b1) = O(1) if \u03b1 constant",
                    "worst_search": "O(n) if all keys collide",
                    "insert": "O(1) (prepend to list)",
                    "delete": "O(1) if have pointer, else O(length of chain)"
                },
                "pros": [
                    "Simple",
                    "Handles any load factor",
                    "Deletion easy",
                    "Never full (can always insert)"
                ],
                "cons": [
                    "Memory overhead (pointers per node)",
                    "Cache unfriendly (linked list scattered)"
                ],
                "optimization": "Convert linked list to balanced BST (e.g., Java 8+) when chain length exceeds threshold (e.g., 8) \u2192 O(log n) worst case"
            },
            "open_addressing": {
                "structure": "All entries stored directly in array; collision \u2192 probe sequence to find next available slot",
                "probing_methods": {
                    "linear": "h(k, i) = (h'(k) + i) mod m \u2014 simple but primary clustering",
                    "quadratic": "h(k, i) = (h'(k) + c\u2081i + c\u2082i\u00b2) mod m \u2014 reduces clustering but secondary clustering remains",
                    "double_hashing": "h(k, i) = (h\u2081(k) + i \u00d7 h\u2082(k)) mod m \u2014 minimal clustering, best performance; h\u2082(k) must be relatively prime to m"
                },
                "complexity": {
                    "avg_search": "O(1 \/ (1 - \u03b1)) for successful, O(1 \/ (1 - \u03b1)\u00b2) for unsuccessful",
                    "worst_search": "O(n) if table nearly full",
                    "insert": "Same as search (find empty slot)",
                    "delete": "Complex \u2014 cannot simply remove (breaks probe chain); use tombstone marker"
                },
                "pros": [
                    "No pointer overhead (cache friendly)",
                    "Lower memory use"
                ],
                "cons": [
                    "More sensitive to load factor",
                    "Deletion tricky (tombstones accumulate)",
                    "Clustering issues (linear\/quadratic)"
                ],
                "notes": "Table load should stay \u2264 0.5-0.7 for good performance; tombstone cleanup periodic rehash"
            }
        },
        "hash_table_types": [
            {
                "name": "HashMap \/ Dictionary",
                "implementation": "Array of buckets + hash function + collision resolution",
                "languages": [
                    "Python: dict",
                    "Java: HashMap",
                    "JavaScript: Object\/Map",
                    "C++: std::unordered_map",
                    "Go: map"
                ],
                "avg_operations": "O(1)",
                "notes": "Most common associative array; maintains insertion order in some implementations (Python 3.7+)"
            },
            {
                "name": "HashSet",
                "implementation": "Hash table storing only keys (no values)",
                "languages": [
                    "Python: set",
                    "Java: HashSet",
                    "C++: std::unordered_set"
                ],
                "use_cases": [
                    "Duplicate elimination",
                    "Membership testing",
                    "Set operations (union, intersection)"
                ],
                "notes": "Backed by hash table; hash of key determines bucket"
            },
            {
                "name": "Concurrent Hash Map",
                "implementation": "Lock striping or lock-free segments for thread-safe access",
                "languages": [
                    "Java: ConcurrentHashMap",
                    "C++: tbb::concurrent_hash_map",
                    "Rust: dashmap"
                ],
                "features": [
                    "Fine-grained locking (segment\/ stripe)",
                    "Lock-free reads",
                    "High concurrency"
                ],
                "notes": "Traditional HashMap requires external synchronization (synchronized\/mutex); concurrent maps scale to many threads"
            }
        ],
        "design_considerations": {
            "choose_hash_function": {
                "integers": "Multiplicative: (a \u00d7 k) >> shift or modulo prime",
                "strings": "Polynomial rolling hash (h = \u03a3 char[i] \u00d7 p^i mod m) or MurmurHash3",
                "objects": "Combine field hashes: hash = 31 \u00d7 (31 \u00d7 seed + field1.hash) + field2.hash (Java style)"
            },
            "avoid_collisions": {
                "prime_bucket_count": "Use prime number of buckets (reduces clustering with mod)",
                "good_hash": "Uniform distribution; test with real key distribution",
                "dynamic_resize": "Resize when \u03b1 exceeds threshold (typically 0.75)"
            },
            "when_not_to_use": {
                "ordered_operations": "Need sorted keys \u2192 use BST (TreeMap)",
                "range_queries": "Need keys in range \u2192 BST or B-tree",
                "memory_constrained": "Hash tables have overhead (pointers\/buckets)",
                "extremely_large_keys": "Consider key interning or perfect hash"
            }
        }
    }
}