api: YAML JSON TOON Database
version: 1.0.0
format: yaml
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: 5
  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 → 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