SimuVedaAlgorithms Lab Open in the lab

Hashing / Beginner

Hash Table with Chaining Visualizer

hash(key) mod m picks a bucket. Keys that land in the same bucket (a collision) are kept in a short list. Lookup only scans one bucket.

Start the Hash Table with Chaining simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(1)
Worst timeO(n)
Extra spaceO(n + m)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. 7 empty buckets. Each key goes to bucket key mod 7.
  2. 15 mod 7 = 1. Go to bucket 1.
  3. Bucket 1 was empty. Store 15.
  4. 11 mod 7 = 4. Go to bucket 4.
  5. Bucket 4 was empty. Store 11.
  6. 27 mod 7 = 6. Go to bucket 6.
  7. Bucket 6 was empty. Store 27.
  8. 8 mod 7 = 1. Go to bucket 1.
  9. Is 15 equal to 8?
  10. Collision: bucket 1 already holds 1 key. Add 8 to its chain.
  11. 12 mod 7 = 5. Go to bucket 5.
  12. Bucket 5 was empty. Store 12.
  13. 33 mod 7 = 5. Go to bucket 5.
  14. Is 12 equal to 33?
  15. Collision: bucket 5 already holds 1 key. Add 33 to its chain.
  16. 19 mod 7 = 5. Go to bucket 5.
  17. Is 12 equal to 19?
  18. Is 33 equal to 19?
  19. Collision: bucket 5 already holds 2 keys. Add 19 to its chain.
  20. 42 mod 7 = 0. Go to bucket 0.
  21. … 5 more steps …
  22. Collision: bucket 5 already holds 3 keys. Add 5 to its chain.
  23. Look up 33: 33 mod 7 = 5. Only bucket 5 needs checking.
  24. 12 is not 33. Keep going along the chain.
  25. Found 33 after checking 2 keys in bucket 5.

Try it with your own input →

Hash table with chaining in Java, Python, C++, C and JavaScript

void put(int key) {
  int b = Math.floorMod(key, m);
  for (int k : table[b]) {
    if (k == key) return;
  }
  table[b].add(key);
}
boolean contains(int key) {
  int b = Math.floorMod(key, m);
  for (int k : table[b]) {
    if (k == key) return true;
  }
  return false;
}
class HashSet:
    def __init__(self, m):
        self.m, self.table = m, [[] for _ in range(m)]

    def put(self, key):
        b = key % self.m
        for k in self.table[b]:
            if k == key:
                return
        self.table[b].append(key)

    def contains(self, key):
        b = key % self.m
        for k in self.table[b]:
            if k == key:
                return True
        return False
int m;                            // number of buckets
vector<list<int>> table;          // table[b] holds the keys in bucket b

void put(int key) {
  int b = ((key % m) + m) % m;
  for (int k : table[b]) {
    if (k == key) return;
  }
  table[b].push_back(key);
}
bool contains(int key) {
  int b = ((key % m) + m) % m;
  for (int k : table[b]) {
    if (k == key) return true;
  }
  return false;
}
#include <stdlib.h>

/* Separate chaining: table[b] is a linked list of the keys in bucket b. */
struct Item { int key; struct Item* next; };
int m;
struct Item** table;

void put(int key) {
  int b = ((key % m) + m) % m;
  for (struct Item* it = table[b]; it; it = it->next) {
    if (it->key == key) return;
  }
  struct Item* it = malloc(sizeof *it);
  it->key = key; it->next = table[b]; table[b] = it;
}
int contains(int key) {
  int b = ((key % m) + m) % m;
  for (struct Item* it = table[b]; it; it = it->next) {
    if (it->key == key) return 1;
  }
  return 0;
}
class HashSet {
  constructor(m) { this.m = m; this.table = Array.from({ length: m }, () => []); }
  put(key) {
    const b = ((key % this.m) + this.m) % this.m;
    for (const k of this.table[b]) {
      if (k === key) return;
    }
    this.table[b].push(key);
  }
  contains(key) {
    const b = ((key % this.m) + this.m) % this.m;
    for (const k of this.table[b]) {
      if (k === key) return true;
    }
    return false;
  }
}

In an interview

LeetCode 706, Design HashMap, and 705 Design HashSet. Every "use a HashMap" answer relies on this.

Watch the load factor n ÷ m. Java’s HashMap doubles its buckets when it passes 0.75, which keeps chains short so operations stay O(1) on average.

More hashing