api: "YAML JSON TOON Database"
version: 1.0.0
format: toon
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: 6
  created_at: 1781275786
  updated_at: 1781275786
data:
  core_concepts
    -
      component: "Hash Function"
      purpose: "Maps arbitrary key to integer index in hash table array"
      properties:
        [4]: "Deterministic (same key → same hash)","Fast to compute","Uniform distribution","Minimizes collisions"
      common_functions:
        [5]: 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:
        [2]: "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:
        [4]: Simple,"Handles any load factor","Deletion easy","Never full (can always insert)"
      cons:
        [2]: "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:
        [2]: "No pointer overhead (cache friendly)","Lower memory use"
      cons:
        [3]: "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:
        [5]: "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:
        [3]: "Python: set","Java: HashSet","C++: std::unordered_set"
      use_cases:
        [3]: "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:
        [3]: "Java: ConcurrentHashMap","C++: tbb::concurrent_hash_map","Rust: dashmap"
      features:
        [3]: "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"