Hash Table

A Hash Table (Hash Map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values using a hash function.

Core Concepts

1. Hash Function

   • Converts keys into array indices

   • Should be deterministic

   • Should distribute values uniformly

   • Should be fast to compute

2. Collision Resolution

   • Chaining (linked lists)

   • Open addressing (linear probing)

   • Double hashing

3. Load Factor

   • ratio = n/k (n: entries, k: bucket count)

   • Triggers resizing when exceeded

   • Typically 0.75 in most implementations

Implementation in Go

Basic HashMap with Chaining

type Entry struct {
    key   string
    value interface{}
    next  *Entry
}

type HashMap struct {
    buckets []*Entry
    size    int
    count   int
}

func NewHashMap(size int) *HashMap {
    return &HashMap{
        buckets: make([]*Entry, size),
        size:    size,
    }
}

func (h *HashMap) hash(key string) int {
    hash := 0
    for i := 0; i < len(key); i++ {
        hash = 31*hash + int(key[i])
    }
    return hash % h.size
}

func (h *HashMap) Put(key string, value interface{}) {
    index := h.hash(key)
    
    // Check if key exists
    current := h.buckets[index]
    for current != nil {
        if current.key == key {
            current.value = value
            return
        }
        current = current.next
    }
    
    // Add new entry
    entry := &Entry{
        key:   key,
        value: value,
        next:  h.buckets[index],
    }
    h.buckets[index] = entry
    h.count++
    
    // Check load factor and resize if needed
    if float64(h.count)/float64(h.size) > 0.75 {
        h.resize()
    }
}

func (h *HashMap) Get(key string) (interface{}, bool) {
    index := h.hash(key)
    current := h.buckets[index]
    
    for current != nil {
        if current.key == key {
            return current.value, true
        }
        current = current.next
    }
    
    return nil, false
}

func (h *HashMap) resize() {
    oldBuckets := h.buckets
    h.size *= 2
    h.buckets = make([]*Entry, h.size)
    h.count = 0
    
    // Rehash all entries
    for _, entry := range oldBuckets {
        for entry != nil {
            h.Put(entry.key, entry.value)
            entry = entry.next
        }
    }
}

HashMap with Open Addressing

type Entry struct {
    key     string
    value   interface{}
    deleted bool
}

type OpenHashMap struct {
    entries []Entry
    size    int
    count   int
}

func NewOpenHashMap(size int) *OpenHashMap {
    return &OpenHashMap{
        entries: make([]Entry, size),
        size:    size,
    }
}

func (h *OpenHashMap) hash(key string, attempt int) int {
    hash := 0
    for i := 0; i < len(key); i++ {
        hash = 31*hash + int(key[i])
    }
    // Linear probing
    return (hash + attempt) % h.size
}

func (h *OpenHashMap) Put(key string, value interface{}) {
    if float64(h.count)/float64(h.size) > 0.75 {
        h.resize()
    }
    
    attempt := 0
    for {
        index := h.hash(key, attempt)
        if h.entries[index].key == "" || h.entries[index].deleted {
            h.entries[index] = Entry{key: key, value: value}
            h.count++
            return
        }
        if h.entries[index].key == key {
            h.entries[index].value = value
            return
        }
        attempt++
    }
}

func (h *OpenHashMap) Get(key string) (interface{}, bool) {
    attempt := 0
    for {
        index := h.hash(key, attempt)
        if h.entries[index].key == "" {
            return nil, false
        }
        if h.entries[index].key == key && !h.entries[index].deleted {
            return h.entries[index].value, true
        }
        attempt++
        if attempt >= h.size {
            return nil, false
        }
    }
}

Time Complexity

Average Case

• Insert: O(1)

• Delete: O(1)

• Search: O(1)

Worst Case (Many Collisions)

• Insert: O(n)

• Delete: O(n)

• Search: O(n)

Space Complexity

• O(n) where n is the number of key-value pairs

Common Applications

1. Database Indexing

2. Caching Systems

3. Symbol Tables

4. Counting/Frequency Tracking

5. Deduplication

6. Caching

7. Session Storage

Related LeetCode Problems

Easy

1. 1. Two Sum

   • HashMap for complement finding

   • Time: O(n), Space: O(n)

2. 217. Contains Duplicate

   • HashSet for tracking seen elements

   • Time: O(n), Space: O(n)

3. 705. Design HashSet

   • Basic HashSet implementation

   • Collision handling practice

Medium

1. 146. LRU Cache

   • HashMap + Doubly Linked List

   • O(1) operations

2. 380. Insert Delete GetRandom O(1)

   • HashMap + Array combination

   • Constant time operations

3. 49. Group Anagrams

   • HashMap with sorted string keys

   • Character counting

Hard

1. 76. Minimum Window Substring

   • Sliding window with HashMap

   • Character frequency tracking

2. 30. Substring with Concatenation of All Words

   • Multiple HashMaps

   • Sliding window technique

Best Practices

1. Hash Function Design

   • Use prime numbers

   • Distribute keys uniformly

   • Handle different data types

   • Consider performance vs. collision trade-offs

2. Collision Resolution

   • Choose appropriate method

   • Monitor load factor

   • Implement efficient resizing

   • Handle edge cases

3. Memory Management

   • Implement proper cleanup

   • Handle resizing efficiently

   • Consider memory constraints

   • Clean up deleted entries

4. Performance Optimization

   • Use efficient hash functions

   • Implement proper resizing

   • Choose appropriate initial size

   • Monitor performance metrics

Common Variations

1. Implementation Types

   • Separate Chaining

   • Open Addressing

   • Robin Hood Hashing

   • Cuckoo Hashing

2. Special Features

   • Thread-safe maps

   • Ordered maps

   • Concurrent maps

   • Weak reference maps

3. Use Cases

   • Cache implementation

   • Symbol tables

   • Database indexes

   • Frequency counting

Resources

1. Hash Table Visualization

2. Go Map Implementation

3. Introduction to Algorithms (CLRS) - Chapter on Hash Tables

4. Wikipedia - Hash Table