Hash Table

Maps keys to values using a hash function. O(1) average-case insert/lookup/delete. Used in dictionaries, caches, and sets.

Syntax

dsa

insert(key, value)
get(key)
delete(key)

Example

dsa

// JavaScript Object / Map:
const map = new Map();
map.set("alice", 95);  // O(1)
map.set("bob", 87);
map.get("alice");      // O(1): 95
map.has("carol");      // false
map.delete("bob");

// Collisions resolved by chaining or open addressing