Hash Table

Data Structures

avgO(1)worstO(n)spaceO(n + m)

h(k) = k mod 7

7 buckets holding 3 keys (load factor 0.43)

1 / 42

Code

class HashTable {  private buckets: number[][];  constructor(private m = 7) {    this.buckets = Array.from({ length: m }, () => []);  }  private hash(key: number) {    return ((key % this.m) + this.m) % this.m;  }  insert(key: number) {    const h = this.hash(key);    for (const k of this.buckets[h]) {      if (k === key) return false;    }    this.buckets[h].push(key);    return true;  }  delete(key: number) {    const h = this.hash(key);    const chain = this.buckets[h];    for (let i = 0; i < chain.length; i++) {      if (chain[i] === key) {        chain.splice(i, 1);        return true;      }    }    return false;  }  search(key: number) {    const h = this.hash(key);    for (const k of this.buckets[h]) {      if (k === key) return true;    }    return false;  }}

structure HashTable    ▷ separate chaining  buckets  constructor(m = 7)    buckets ← m empty chains  end constructor  function hash(key)    return key mod m  end function  procedure insert(key)    h ← hash(key)    for each k in buckets[h] do      if k = key then return false    ▷ no duplicates    end for    append key to buckets[h]    return true  end procedure  procedure delete(key)    h ← hash(key)    chain ← buckets[h]    for i ← 0 to length(chain) − 1 do      if chain[i] = key then        remove chain[i]        return true      end if    end for    return false  end procedure  procedure search(key)    h ← hash(key)    for each k in buckets[h] do      if k = key then return true    end for    return false  end procedureend structure

Variables

m=7n=3load=0.43

Counters

probes: 0
collisions: 0

Starting contents3 values

Operations8 / 40

1. insert(15)
2. insert(29)
3. insert(8)
4. insert(22)
5. search(29)
6. delete(15)
7. search(44)
8. insert(36)

How it works

Maps each key to one of m buckets with hash(k) = k mod m and keeps colliding keys in a chain. With a good hash and a low load factor every chain is short, so insert, search and delete take O(1) on average. If every key collides, they take O(n).

Complexity

Best: O(1)
Average: O(1)
Worst: O(n)
Space: O(n + m)

Hash Table

How it works

Complexity

Search algorithms