Kata: Build a Hash Map

Table of contents

Problem Statement

Implement a hash map that supports:

• set(key, value) — insert or update a key-value pair
• get(key) — retrieve a value by key
• delete(key) — remove a key-value pair
• has(key) — check if a key exists
• size — number of entries
• Dynamic resizing when load factor exceeds 0.75

Use separate chaining (linked list per bucket) for collision handling.

Concepts

A hash map stores key-value pairs in an array of “buckets”. A hash function maps keys to bucket indices. When multiple keys hash to the same index (collision), we chain them in a list.

Load factor = entries / buckets. When it’s too high, we resize (typically double) and rehash all entries.

PHP: PHP arrays are natively ordered hash maps — one of the most powerful built-in data structures in any language. See PHP Core Concepts.

Python: Python dict is a highly optimized hash map with open addressing. See Python Core Concepts for __hash__ and __eq__.

Boilerplate

TypeScript

// hash-map.ts
class HashMap<K, V> {
  private buckets: Array<Array<[K, V]>>;
  private count: number = 0;
  private capacity: number;

  constructor(initialCapacity: number = 16) {
    this.capacity = initialCapacity;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
  }

  private hash(key: K): number {
    // TODO: implement hash function
    return 0;
  }

  set(key: K, value: V): void { /* TODO */ }
  get(key: K): V | undefined { /* TODO */ return undefined; }
  delete(key: K): boolean { /* TODO */ return false; }
  has(key: K): boolean { /* TODO */ return false; }
  get size(): number { return this.count; }
}

Hints

Solution

TypeScript

class HashMap<K, V> {
  private buckets: Array<Array<[K, V]>>;
  private count: number = 0;
  private capacity: number;
  private readonly loadFactorThreshold = 0.75;

  constructor(initialCapacity: number = 16) {
    this.capacity = initialCapacity;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
  }

  private hash(key: K): number {
    const str = String(key);
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) | 0;
    }
    return Math.abs(hash) % this.capacity;
  }

  set(key: K, value: V): void {
    if (this.count / this.capacity > this.loadFactorThreshold) {
      this.resize();
    }

    const index = this.hash(key);
    const bucket = this.buckets[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }

    bucket.push([key, value]);
    this.count++;
  }

  get(key: K): V | undefined {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    for (const [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }

  delete(key: K): boolean {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this.count--;
        return true;
      }
    }
    return false;
  }

  has(key: K): boolean {
    return this.get(key) !== undefined;
  }

  get size(): number {
    return this.count;
  }

  private resize(): void {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
    this.count = 0;

    for (const bucket of oldBuckets) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }
}

Complexity Analysis

Worst case occurs when all keys hash to the same bucket (degenerate case).

Cross-Language Notes

PHP: You don’t need to implement this in PHP for production use. PHP arrays are hash maps with O(1) average lookup, insertion order preservation, and rich built-in functions (array_key_exists, array_filter, etc.). See PHP Core Concepts.

Python: Python’s dict uses open addressing (not chaining) and is one of the most optimized hash map implementations in any language. Since Python 3.7, dicts maintain insertion order. The __hash__ and __eq__ dunder methods control how custom objects behave as dict keys.

Java: HashMap uses separate chaining with a twist — when a bucket exceeds 8 entries, it converts from a linked list to a balanced tree (Red-Black tree), improving worst case from O(n) to O(log n).