api: "YAML JSON TOON Database"
version: "1.0.0"
format: "json"
dataset:
  id: 27
  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: 0
  created_at: 1777673262
  updated_at: 1777673262
data:
  core_concepts:
    - component: "Hash Function"
      purpose: "Maps arbitrary key to integer index in hash table array"
      properties:
        - "Deterministic (same key → 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 × k + b) mod m (affine hash for integers)"
      notes: "Cryptographic hashes (SHA, MD5) are slow; non-cryptographic preferred for hash tables"
    - component: "Load Factor (α)"
      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 α 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 α → more collisions, slower lookups; lower α → 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) → bucket index → traverse list"
      complexity:
        avg_search: "O(1 + α) = O(1) if α 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) → O(log n) worst case"
    open_addressing:
      structure: "All entries stored directly in array; collision → probe sequence to find next available slot"
      probing_methods:
        linear: "h(k, i) = (h'(k) + i) mod m — simple but primary clustering"
        quadratic: "h(k, i) = (h'(k) + c₁i + c₂i²) mod m — reduces clustering but secondary clustering remains"
        double_hashing: "h(k, i) = (h₁(k) + i × h₂(k)) mod m — minimal clustering, best performance; h₂(k) must be relatively prime to m"
      complexity:
        avg_search: "O(1 / (1 - α)) for successful, O(1 / (1 - α)²) for unsuccessful"
        worst_search: "O(n) if table nearly full"
        insert: "Same as search (find empty slot)"
        delete: "Complex — 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 ≤ 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 × k) >> shift or modulo prime"
      strings: "Polynomial rolling hash (h = Σ char[i] × p^i mod m) or MurmurHash3"
      objects: "Combine field hashes: hash = 31 × (31 × 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 α exceeds threshold (typically 0.75)"
    when_not_to_use:
      ordered_operations: "Need sorted keys → use BST (TreeMap)"
      range_queries: "Need keys in range → BST or B-tree"
      memory_constrained: "Hash tables have overhead (pointers/buckets)"
      extremely_large_keys: "Consider key interning or perfect hash"