Hash Tables

What you'll learn

• Core Concept: The Hash Function

  A hash function takes a key (of any type) and converts it into an integer index within the bounds of an underlying array. The ideal hash function: - Is deterministic (same key always produces same index) - Distributes keys uniformly acro…

• Simple Example

• How Hashing Works in Practice

  For strings, a common approach is to use the characters' numeric values: The modulo operation ensures the result fits within the array bounds.

• Collision Resolution

  Since the array is finite but possible keys are infinite, two different keys can hash to the same index. This is called a collision. There are two main strategies to handle collisions.

• Strategy 1: Chaining (Separate Chaining)

  Each bucket in the array holds a linked list (or another collection). When a collision occurs, the new element is appended to the list at that bucket. Lookup with chaining: 1. Compute hash(key) to find the bucket 2. Traverse the linked l…

• Strategy 2: Open Addressing

  All elements are stored directly in the array. When a collision occurs, we probe for the next available slot.

• Chaining vs Open Addressing Comparison

• Load Factor and Rehashing

  The load factor is defined as: As the load factor increases, performance degrades: - Chaining: Average chain length = load factor. At load factor 2, each lookup traverses 2 nodes on average. - Open addressing: Performance degrades sharpl…

• Rehashing

  When the load factor exceeds a threshold (commonly 0.75), the table rehashes: 1. Allocate a new array (typically 2x the size) 2. Recompute hash for every existing element 3. Insert all elements into the new array

• Why O(1) Amortized Insert

  Consider inserting n elements starting from table size 1, doubling each time:

• Time Complexity Analysis

• Why O(n) Worst Case Happens

  The worst case occurs when all keys hash to the same index. This can happen when: 1. Poor hash function: A badly designed hash function maps many keys to the same bucket 2. Adversarial input: An attacker who knows the hash function craft…

• Hash Set vs Hash Map

  A hash set is essentially a hash map where you only care about the keys. Internally, many implementations use a hash map with dummy values. Key operations comparison:

• Python Dict Internals

  Python's dict uses open addressing with a technique called perturbation-based probing.

• How Python Probes

  Key design choices: - Load factor threshold: Python resizes when the table is 2/3 full - Growth factor: Table size grows by 4x when small, 2x when large - Compact dict (Python 3.6+): Separates hash indices from key-value storage, maintai…

• Pattern: Frequency Counting

  Count occurrences of elements in a collection. Sample Input / Output Input: items = ["the", "cat", "sat", "on", "the", "mat", "the"] Output: {"the": 3, "cat": 1, "sat": 1, "on": 1, "mat": 1} Input: items = [] Output: {} — edge case: empt…

• Pattern: Two-Sum (Complement Lookup)

  The classic pattern: find two elements that satisfy a condition using a hash map to store previously seen values. Sample Input / Output Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] (nums[0] + nums[1] == 9) Input: nums = [3, 2,…

• Pattern: Group Anagrams (Canonical Key)

  Group items that share a common property by computing a canonical (normalized) representation as the hash key. Sample Input / Output Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["eat","tea","ate"], ["tan","nat"], […

• When to Use Hash Tables

• Use hash tables when:

  1. O(1) lookups are needed - checking membership, finding values by key 2. Frequency counting - counting occurrences of elements 3. Deduplication - removing duplicates from a collection 4. Caching/Memoization - storing computed results f…

• Do NOT use hash tables when:

  1. Ordered data is needed - hash tables don't maintain sorted order. Use a BST or sorted array instead. 2. Range queries - "find all keys between 10 and 20" requires O(n) scan. Use a BST or segment tree. 3. Small data sets - for fewer th…

• Data Structure Design

• Operations Complexity

  Get: O(1) amortized. Hash map lookup is O(1), and promoting within the LRU list is O(1) pointer manipulation. Set: O(log n). Inserting into the BST or heap is O(log n), and potential eviction is at most O(log n) for priority-based remova…

• Eviction Logic

  How eviction selects a victim: First check the heap for expired items (O(1) peek). If none expired, use the BST to find the minimum priority bucket (O(log n)), then remove the tail (LRU) from that bucket's doubly-linked list (O(1)). This…

• Key Insight

  The challenge is maintaining O(1) or O(log n) for all operations. The combination of: - HashMap for O(1) key lookup - Min-heap for O(1) access to earliest expiration - BST with LRU lists for O(log n) access to lowest priority + LRU withi…

• Summary