Hash Tables / Hash Maps for Complete Beginners

A hash table (hash map) stores data as key → value pairs for fast lookups. A hash function turns each key into a number called an index, which points to a “bucket” (a small list). We handle collisions (two keys landing in the same bucket) by chaining pairs inside that bucket. As the table fills up, we resize to keep things fast.

JavaScript Implementation


class HashMap {
  constructor(initialCapacity = 8) {
    this._capacity = Math.max(4, initialCapacity | 0);
    this._buckets = Array.from({ length: this._capacity }, () => []);
    this._count = 0;
    this._maxLoad = 0.7;
  }

  _hash(key) {
    const s = String(key);
    let h = 0;
    for (let i = 0; i < s.length; i++) {
      h = (h * 31 + s.charCodeAt(i)) | 0;
    }
    return Math.abs(h) % this._capacity;
  }

  _loadFactor() {
    return this._count / this._capacity;
  }

  _resize(newCapacity) {
    const oldBuckets = this._buckets;
    this._capacity = Math.max(4, newCapacity | 0);
    this._buckets = Array.from({ length: this._capacity }, () => []);
    this._count = 0;

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

  _ensureCapacity() {
    if (this._loadFactor() > this._maxLoad) {
      this._resize(this._capacity * 2);
    }
  }

  set(key, value) {
    const idx = this._hash(key);
    const bucket = this._buckets[idx];

    for (let i = 0; i < bucket.length; i++) {
      const pair = bucket[i];
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    bucket.push([key, value]);
    this._count++;
    this._ensureCapacity();
  }

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

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

  remove(key) {
    const idx = this._hash(key);
    const bucket = this._buckets[idx];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this._count--;
        return true;
      }
    }
    return false;
  }

  keys() {
    const result = [];
    for (const bucket of this._buckets) {
      for (const [k] of bucket) result.push(k);
    }
    return result;
  }

  values() {
    const result = [];
    for (const bucket of this._buckets) {
      for (const [, v] of bucket) result.push(v);
    }
    return result;
  }

  size() {
    return this._count;
  }

  clear() {
    this._buckets = Array.from({ length: this._capacity }, () => []);
    this._count = 0;
  }
}

// Example usage:
const map = new HashMap();
map.set("apple", 3);
map.set("banana", 5);
map.set("carrot", 2);
map.set("banana", 9);       // update existing key

console.log("has banana?", map.has("banana")); // true
console.log("banana =", map.get("banana"));    // 9
console.log("remove carrot", map.remove("carrot")); // true
console.log("keys:", map.keys());              // ["apple","banana"]
console.log("values:", map.values());          // [3, 9]
console.log("size:", map.size());              // 2 (after remove)

Complete Explanation of the Code

Constructor: Sets a starting bucket count (_capacity), creates empty buckets, sets the number of stored pairs (_count) to 0, and a target load factor (_maxLoad = 0.7).
_hash: Converts any key to a string and rolls characters into a 32-bit integer using h = h*31 + charCode. The absolute value mod capacity maps it to a bucket index.
_loadFactor: Returns how full the table is (_count / _capacity).
_resize: Builds a new bucket array with a larger capacity, resets _count, then re-inserts every old pair by calling set (so each pair is re-hashed to the new size).
_ensureCapacity: If the load factor exceeds _maxLoad, doubles capacity via _resize.
set: Finds the bucket for key. If the key already exists there, updates its value. Otherwise appends a new [key, value] pair, increments _count, and checks if resizing is needed.
get: Goes to the bucket for key and returns the value if found; otherwise returns undefined.
has: Returns true if get(key) is not undefined, else false.
remove: Locates the bucket, finds the matching key, deletes that pair with splice, decrements _count, and returns true; if not found, returns false.
keys / values: Walk all buckets, collecting the first (keys) or second (values) element of each pair into arrays and return them.
size / clear: size returns _count. clear empties all buckets but keeps the same capacity.
Example usage: Demonstrates insert, update, query, delete, and iteration helpers.

Performance Note: With a good hash and periodic resizing, set/get/has/remove are typically O(1) on average; in the worst case (many collisions in one bucket), operations degrade toward O(n).

Standard Pseudocode


CLASS HashMap
    SET capacity TO 8 (minimum 4)
    INITIALIZE buckets AS array of empty lists WITH length = capacity
    SET count TO 0
    SET maxLoad TO 0.7

    PROCEDURE INITIALIZE(initialCapacity)
        IF initialCapacity IS NOT PROVIDED THEN
            SET capacity TO 8
        ELSE
            SET capacity TO MAX(4, FLOOR(initialCapacity))
        END IF
        INITIALIZE buckets AS array of empty lists WITH length = capacity
        SET count TO 0
        SET maxLoad TO 0.7
    END PROCEDURE

    FUNCTION HASH(key)
        SET s TO STRING(key)
        SET h TO 0
        FOR i FROM 0 TO LENGTH(s) - 1
            SET h TO (h * 31 + CODE_POINT_OF(s[i]))
        END FOR
        SET index TO ABS(h) MOD capacity
        RETURN index
    END FUNCTION

    FUNCTION LOAD_FACTOR()
        RETURN count / capacity
    END FUNCTION

    PROCEDURE ENSURE_CAPACITY()
        IF LOAD_FACTOR() > maxLoad THEN
            CALL RESIZE(capacity * 2)
        END IF
    END PROCEDURE

    PROCEDURE RESIZE(newCapacity)
        SET oldBuckets TO buckets
        SET capacity TO MAX(4, FLOOR(newCapacity))
        INITIALIZE buckets AS array of empty lists WITH length = capacity
        SET count TO 0
        FOR EACH bucket IN oldBuckets
            FOR EACH pair IN bucket
                CALL SET(pair[0], pair[1])
            END FOR
        END FOR
    END PROCEDURE

    PROCEDURE SET(key, value)
        SET idx TO HASH(key)
        SET bucket TO buckets[idx]

        FOR i FROM 0 TO LENGTH(bucket) - 1
            IF bucket[i][0] = key THEN
                SET bucket[i][1] TO value
                RETURN
            END IF
        END FOR

        APPEND [key, value] TO bucket
        INCREMENT count
        CALL ENSURE_CAPACITY()
    END PROCEDURE

    FUNCTION GET(key)
        SET idx TO HASH(key)
        SET bucket TO buckets[idx]
        FOR EACH pair IN bucket
            IF pair[0] = key THEN
                RETURN pair[1]
            END IF
        END FOR
        RETURN undefined
    END FUNCTION

    FUNCTION HAS(key)
        IF GET(key) IS NOT undefined THEN
            RETURN true
        ELSE
            RETURN false
        END IF
    END FUNCTION

    FUNCTION REMOVE(key)
        SET idx TO HASH(key)
        SET bucket TO buckets[idx]
        FOR i FROM 0 TO LENGTH(bucket) - 1
            IF bucket[i][0] = key THEN
                DELETE bucket[i] AND SHIFT LEFT REMAINING ELEMENTS
                DECREMENT count
                RETURN true
            END IF
        END FOR
        RETURN false
    END FUNCTION

    FUNCTION KEYS()
        INITIALIZE result AS empty list
        FOR EACH bucket IN buckets
            FOR EACH pair IN bucket
                APPEND pair[0] TO result
            END FOR
        END FOR
        RETURN result
    END FUNCTION

    FUNCTION VALUES()
        INITIALIZE result AS empty list
        FOR EACH bucket IN buckets
            FOR EACH pair IN bucket
                APPEND pair[1] TO result
            END FOR
        END FOR
        RETURN result
    END FUNCTION

    FUNCTION SIZE()
        RETURN count
    END FUNCTION

    PROCEDURE CLEAR()
        INITIALIZE buckets AS array of empty lists WITH length = capacity
        SET count TO 0
    END PROCEDURE
END CLASS

Explanation of the Pseudocode

Fields: capacity is bucket count, buckets holds lists of [key, value], count tracks total pairs, maxLoad is the resize threshold.
INITIALIZE: Picks a safe capacity (min 4), creates empty buckets, and resets counters like the JavaScript constructor.
HASH: Walks each character, updates a running number, then uses remainder (MOD) to map into 0..capacity-1.
LOAD_FACTOR / ENSURE_CAPACITY: Computes fullness and grows the table by calling RESIZE if it’s above maxLoad.
RESIZE: Creates larger buckets, resets count, and re-inserts every pair via SET so each key is re-hashed.
SET: Updates the value if the key exists in its bucket; otherwise appends a new pair, increments count, then checks capacity.
GET / HAS: Scans the correct bucket to return the matched value (or undefined); HAS is a simple check built on GET.
REMOVE: Finds and deletes the pair for a key, decreases count, and returns whether removal happened.
KEYS / VALUES / SIZE / CLEAR: Collect keys or values across all buckets; report the total item count; reset buckets to empty.