Hash Table Data Structure: Complete Guide with Code Examples

A hash table (also called a hash map) is a data structure that maps keys to values in O(1) average time. It is one of the most important data structures in computer science — used inside Python dictionaries, JavaScript objects, Java HashMap, and virtually every database index.

Understanding how a hash table works — and why it can degrade to O(n) — is essential for coding interviews and everyday engineering.

Quick reference

Worst-case O(n) happens when many keys hash to the same slot (collisions). A good hash function and a reasonable load factor keep it rare.

How a hash table works

A hash table is backed by an array of fixed size (the bucket array). To store a key-value pair:

1. Hash the key — run the key through a hash function to get an integer index.
2. Reduce to array size — take that integer modulo the array length: index = hash(key) % capacity.
3. Store at that index — place the value (or a bucket node) at buckets[index].

Key "name"
  │
  ▼
hash("name") = 2871452974        (some large integer)
  │
  ▼
2871452974 % 8 = 6               (if capacity = 8)
  │
  ▼
buckets[6] = "Alice"

To look up "name" later, repeat the same two steps — no search required. That's why lookup is O(1).

What is a hash function?

A hash function converts a key (string, integer, object) into an integer. Good hash functions are:

Simple integer hash for strings (djb2 algorithm):

def djb2(key: str) -> int:
    h = 5381
    for ch in key:
        h = ((h << 5) + h) + ord(ch)  # h * 33 + ord(ch)
    return h & 0xFFFFFFFF  # keep 32-bit unsigned

Real languages use battle-tested hash functions (SipHash in Python 3.4+, FNV in Go) that also defend against hash flooding attacks (malicious inputs designed to cause maximum collisions).

Collisions: the core challenge

Two different keys can produce the same index. This is a collision. Two main strategies handle it:

Strategy 1: Separate chaining

Each bucket holds a linked list (or dynamic array) of all key-value pairs that hashed to that slot.

buckets:
  0 → [("cat", 3)]
  1 → [("dog", 7) → ("log", 2)]   ← collision
  2 → []
  3 → [("rat", 5)]

• Insert: O(1) amortised — prepend to the list.
• Lookup: O(1) average — traverse one short list.
• Worst case: all n keys in one bucket → O(n) per operation.

Strategy 2: Open addressing

All entries live inside the array itself — no external lists. When a collision occurs, probe for the next empty slot.

Linear probing: try (index + 1) % cap, (index + 2) % cap, …

insert "dog" → hash → slot 3 occupied → try slot 4 → empty ✓

Quadratic probing: try offsets +1², +2², +3², … (reduces primary clustering).

Double hashing: use a second hash function to compute the step size.

Load factor and rehashing

The load factor λ = n / capacity (number of entries ÷ array size).

When λ exceeds the threshold, the table rehashes:

1. Allocate a new array (typically 2× the size).
2. Reinsert every existing entry into the new array.
3. Old array is garbage collected.

Rehashing is O(n) but happens infrequently — amortised over all inserts, each insert is still O(1).

Implementations in 4 languages

Python

Python's built-in dict is a hash table. Build a minimal one from scratch:

class HashMap:
    def __init__(self, capacity: int = 16):
        self._cap = capacity
        self._buckets: list[list] = [[] for _ in range(capacity)]
        self._size = 0

    def _index(self, key: str) -> int:
        return hash(key) % self._cap

    def put(self, key: str, value) -> None:
        idx = self._index(key)
        for pair in self._buckets[idx]:
            if pair[0] == key:
                pair[1] = value
                return
        self._buckets[idx].append([key, value])
        self._size += 1
        if self._size / self._cap > 0.75:
            self._rehash()

    def get(self, key: str):
        for pair in self._buckets[self._index(key)]:
            if pair[0] == key:
                return pair[1]
        raise KeyError(key)

    def delete(self, key: str) -> None:
        idx = self._index(key)
        bucket = self._buckets[idx]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket.pop(i)
                self._size -= 1
                return
        raise KeyError(key)

    def _rehash(self) -> None:
        old = self._buckets
        self._cap *= 2
        self._buckets = [[] for _ in range(self._cap)]
        self._size = 0
        for bucket in old:
            for key, value in bucket:
                self.put(key, value)

# Usage
m = HashMap()
m.put("name", "Alice")
m.put("age", 30)
print(m.get("name"))  # Alice
m.delete("age")

JavaScript

JavaScript objects are hash maps. Build a minimal one:

class HashMap {
  constructor(capacity = 16) {
    this._cap = capacity;
    this._buckets = Array.from({ length: capacity }, () => []);
    this._size = 0;
  }

  _hash(key) {
    let h = 0;
    for (const ch of key) h = (Math.imul(31, h) + ch.charCodeAt(0)) | 0;
    return Math.abs(h) % this._cap;
  }

  put(key, value) {
    const idx = this._hash(key);
    for (const pair of this._buckets[idx]) {
      if (pair[0] === key) { pair[1] = value; return; }
    }
    this._buckets[idx].push([key, value]);
    this._size++;
    if (this._size / this._cap > 0.75) this._rehash();
  }

  get(key) {
    for (const [k, v] of this._buckets[this._hash(key)]) {
      if (k === key) return v;
    }
    return undefined;
  }

  delete(key) {
    const idx = this._hash(key);
    const b = this._buckets[idx];
    const i = b.findIndex(([k]) => k === key);
    if (i !== -1) { b.splice(i, 1); this._size--; }
  }

  _rehash() {
    const old = this._buckets;
    this._cap *= 2;
    this._buckets = Array.from({ length: this._cap }, () => []);
    this._size = 0;
    for (const bucket of old)
      for (const [k, v] of bucket) this.put(k, v);
  }
}

// Usage
const m = new Map();          // built-in
m.set("name", "Alice");
console.log(m.get("name"));  // Alice
m.delete("name");

Java

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();

        // Insert
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Carol", 92);

        // Lookup
        System.out.println(scores.get("Alice")); // 95
        System.out.println(scores.getOrDefault("Dave", 0)); // 0

        // Update
        scores.put("Bob", 90);

        // Delete
        scores.remove("Carol");

        // Iterate
        for (Map.Entry<String, Integer> e : scores.entrySet()) {
            System.out.printf("%s → %d%n", e.getKey(), e.getValue());
        }

        // Compute if absent
        scores.computeIfAbsent("Eve", k -> 88);

        // Merge
        scores.merge("Alice", 5, Integer::sum); // Alice = 100
    }
}

Java's HashMap uses separate chaining (linked list that converts to a balanced BST when a bucket exceeds 8 entries — since Java 8).

Go

Go's built-in map is a hash table:

package main

import "fmt"

func main() {
    // Create
    scores := make(map[string]int)

    // Insert
    scores["Alice"] = 95
    scores["Bob"] = 87

    // Lookup with existence check
    if v, ok := scores["Alice"]; ok {
        fmt.Println("Alice:", v) // 95
    }

    // Update
    scores["Bob"] = 90

    // Delete
    delete(scores, "Bob")

    // Iterate (order not guaranteed)
    for k, v := range scores {
        fmt.Printf("%s → %d\n", k, v)
    }

    // Zero value for missing key
    fmt.Println(scores["Carol"]) // 0
}

Go's map uses a variant of open addressing with hash seed randomisation per program run (to prevent hash flooding).

Hash table vs array vs linked list

Hash table vs binary search tree (BST)

Use a BST (TreeMap in Java, std::map in C++) when you need keys in sorted order or range queries. Use a hash table for everything else.

6 classic interview problems

1. Two sum (LeetCode #1)

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}   # value → index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

2. First non-repeating character

from collections import Counter

def first_unique(s: str) -> str:
    freq = Counter(s)
    for ch in s:
        if freq[ch] == 1:
            return ch
    return ""

print(first_unique("leetcode"))  # "l"

3. Group anagrams

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))
        groups[key].append(w)
    return list(groups.values())

print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

4. Longest consecutive sequence

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for n in num_set:
        if n - 1 not in num_set:       # start of a sequence
            length = 1
            while n + length in num_set:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100,4,200,1,3,2]))  # 4

5. Subarray sum equals k

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix = 0
    seen: dict[int, int] = defaultdict(int)
    seen[0] = 1
    for n in nums:
        prefix += n
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

6. LRU cache (HashMap + doubly linked list)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self._cap = capacity
        self._cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self._cache:
            return -1
        self._cache.move_to_end(key)
        return self._cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self._cache:
            self._cache.move_to_end(key)
        self._cache[key] = value
        if len(self._cache) > self._cap:
            self._cache.popitem(last=False)

Real-world uses

Common mistakes

Hash table vs related concepts

FAQ

Q: Why does Python dict maintain insertion order?
Since Python 3.7, dict is guaranteed to preserve insertion order. CPython achieves this by keeping a compact index array separate from a dense array of (hash, key, value) entries added in insertion order.

Q: Can a hash table have duplicate keys?
No — by definition, keys are unique. Inserting with an existing key overwrites the value. For multiple values per key, store a list as the value: map[key] = map.get(key, []) + [value].

Q: What makes a "bad" hash function?
One that maps many different keys to the same bucket. For example, hash(key) = 0 for all keys turns every lookup into an O(n) linear scan. A good hash function distributes keys uniformly across all buckets.

Q: Is dict in Python thread-safe?
Individual operations (d[k], d[k] = v) are atomic in CPython due to the GIL, but compound operations like "check then set" are not. For multi-threaded code, use threading.Lock or concurrent.futures.

Q: When should I use a TreeMap instead of a HashMap?
When you need keys in sorted order (e.g., find all keys in a range, iterate in alphabetical order). TreeMap gives O(log n) per operation but supports floorKey, ceilingKey, subMap, and sorted iteration. HashMap gives O(1) but has no ordering.

Q: What is Robin Hood hashing?
An open-addressing variant that reduces variance in probe lengths. When inserting, if the new key has probed further than the key already in a slot ("richer" slot), they swap — the "poor" key continues probing. This keeps the maximum probe length low and improves cache performance.