Hash Table

A key-value store that uses a hash function to map keys to bucket indices, enabling O(1) average lookups.

Complexity

Time (Best)

O(1)

Time (Avg)

O(1)

Time (Worst)

O(n)

Space

O(n)

Key Points

›O(1) average for insert, delete, and lookup
›Hash collisions (two keys → same bucket) degrade to O(n) in the worst case
›Common collision strategies: chaining (linked list per bucket) or open addressing
›Load factor (n/capacity) triggers a resize when too high (typically > 0.75)
›Keys must be hashable; order is not guaranteed (use LinkedHashMap for insertion order)

Code Examples

Swift

// Swift uses Dictionary as its hash table
var table: [String: Int] = [:]

// Insert/Update — O(1) avg
table["apple"] = 5
table["banana"] = 3
table["cherry"] = 8

// Lookup — O(1) avg
if let count = table["apple"] {
    print("apple: \(count)")   // apple: 5
}

// Delete — O(1) avg
table.removeValue(forKey: "banana")

// Check existence — O(1) avg
let exists = table["cherry"] != nil

// Iterate — O(n)
for (key, value) in table {
    print("\(key): \(value)")
}

print(table.count)  // 2

Practice Problems

Two Sum

EasyLeetCode ↗

Contains Duplicate

EasyLeetCode ↗

Group Anagrams

MediumLeetCode ↗

Longest Consecutive Sequence

MediumLeetCode ↗