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." summary: "How hash tables work: hash functions, load factor and collision resolution by chaining or open addressing, the common hash table types in programming languages, and design considerations for choosing a hash function and avoiding collisions." use_when[2]: You are explaining or implementing a hash table.,You need to reason about collisions and load factor. caveats[2]: Average O(1) lookup depends on a good hash function and a bounded load factor; adversarial inputs can degrade it.,Hash tables do not keep keys ordered; use a tree-based map when order matters. related[4]: complexity-analysis,bloom-filters-probabilistic,concurrent-data-structures,prime-numbers-list 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 entry_count: 6 fields[21]{section,field,type,example}: core_concepts,component,string,Hash Function core_concepts,purpose,string,Maps arbitrary key to integer index in hash tab… core_concepts,properties,array,"[4 items]" core_concepts,common_functions,array,"[5 items]" core_concepts,example,string,h(k) = (a × k + b) mod m (affine hash for integ… core_concepts,notes,string,"Cryptographic hashes (SHA, MD5) are slow; non-c…" core_concepts,definition,string,Ratio of number of entries to number of buckets… core_concepts,threshold,string,"Typically 0.75 for separate chaining, 0.5-0.7 f…" core_concepts,rehashing,string,"When α exceeds threshold, resize table (usually…" core_concepts,time_impact,string,Amortized O(1) if resizing infrequent; worst-ca… core_concepts,strategies,array,"[2 items]" core_concepts,description,string,Method to handle multiple keys mapping to same … collision_strategies,*,object,"{separate_chaining,open_addressing}" hash_table_types,name,string,HashMap / Dictionary hash_table_types,implementation,string,Array of buckets + hash function + collision re… hash_table_types,languages,array,"[5 items]" hash_table_types,avg_operations,string,O(1) hash_table_types,notes,string,Most common associative array; maintains insert… hash_table_types,use_cases,array,"[3 items]" hash_table_types,features,array,"[3 items]" design_considerations,*,object,"{choose_hash_function,avoid_collisions,when_not_to_use}" data: core_concepts[3]: - 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[3]: - 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