Inspired by https://arxiv.org/pdf/2501.02305
I'll review the paper and implement a TypeScript version of the hash map that adheres to the JavaScript Map interface. This implementation will include standard methods such as set, get, delete, has, clear, keys, values, and entries. I'll get back to you once it's ready.
Overview: The referenced paper, "Optimal Bounds for Open Addressing Without Reordering" by Farach-Colton et al., introduces elastic hashing – a hash table design that splits the table into multiple sub-arrays and uses a non-greedy probe strategy. This approach achieves amortized O(1) operations with a worst-case expected probe complexity of O(log δ−1) (δ is the slack or fraction of free slots) () (GitHub - MWARDUNI/ElasticHashing: This is a proof of concept for implementing Elastic Hashing to create a new type of hash table without reordering elements while achieving optimal probe complexity.). In simpler terms, even at high load factors, lookups remain efficient (polylogarithmic in the inverse of free space fraction) without the need to move elements after insertion. Below, we implement a TypeScript hash map based on these ideas, matching the JavaScript Map interface (methods set, get, delete, has, clear, keys, values, entries). We incorporate performance optimizations like open-addressing (to avoid pointer overhead) and the multi-level “elastic” probe sequence from the paper.
-
Array Partitioning: The hash table of size n is partitioned into disjoint sub-arrays A1, A2, ..., Am, where each subsequent array is about half the size of the previous one (GitHub - MWARDUNI/ElasticHashing: This is a proof of concept for implementing
Elastic Hashingto create a new type of hash table without reordering elements while achieving optimal probe complexity.). (This yields a geometric series of bucket array sizes summing to n.) For example, if n = 16, we might have |A1| = 8, |A2| = 4, |A3| = 2, |A4| = 2 (ensuring each is ≈ half of the prior, adjusting by ±1 to sum exactly to n). -
Two-Dimensional Probe Sequence: Instead of a single linear probe sequence, each sub-array Ai has its own probe sequence
h_{i,1}(x), h_{i,2}(x), ...that picks random slots within that sub-array () (GitHub - MWARDUNI/ElasticHashing: This is a proof of concept for implementingElastic Hashingto create a new type of hash table without reordering elements while achieving optimal probe complexity.). These sequences are mapped into a single global sequence via an injection function φ, but conceptually the table probes “further” (into higher-index sub-arrays) before settling (). In practice, we simulate this by generating two independent hash values for each key per level (for initial slot and step) so that probes in each sub-array appear random and independent. -
Elastic (Non-Greedy) Insertion: When inserting a key, the algorithm may skip over some free slots in lower-level array Ai and place the key in a higher-level array Ai+1 if Ai is getting full (). This controlled slack means each lower array always retains a fraction of free slots (≈ δ/2 of Ai>), avoiding the classic “coupon-collector” clustering problem that can cause long probe sequences (). Concretely:
- If Ai is sufficiently empty (above a threshold) and Ai+1 is not almost full, attempt a limited number of probes in Ai. If no free slot is found in those attempts, place the item in Ai+1 ().
- If Ai is too full (below the threshold), skip it and insert directly into Ai+1 ().
- Dually, if Ai+1 is extremely full, then insert in Ai (greedily) instead ().
This strategy ensures lower arrays never completely fill up, yielding amortized O(1) performance and provably optimal probe costs ().
-
No Reordering & Deletions: Once placed, an element is never moved (no rehashing or cuckoo-style swapping during insertion) (). To support deletion, we use tombstone markers to fill vacated slots so as not to break probe sequences. A tombstone is treated as “occupied” for search (so lookups continue past it) but “free” for insertion (new inserts can reuse those slots).
Using these principles, we implement the hash map. The map will maintain multiple internal arrays (levels[]), manage the threshold conditions (based on a chosen load factor δ), and generate probe sequences per level. We also preserve insertion order of keys to match iteration behavior of JS Map, by maintaining a doubly linked list of entries.
Below is the TypeScript implementation of an ElasticHashMap class. It provides the full Map interface and optimizes operations as described:
class ElasticHashMap<K, V> {
private totalSize: number; // total number of entries in the map
private maxLoadFactor: number; // load factor (e.g., 0.75 means 25% slack, δ = 0.25)
private levels: { table: any[], size: number }[]; // sub-arrays for open addressing
private salts: { base: number, step: number }[]; // random salts for hashing per level
// Doubly-linked list for insertion order iteration:
private head: { key: K, value: V, next: any, prev: any } | null;
private tail: { key: K, value: V, next: any, prev: any } | null;
// Tombstone marker for deleted slots:
private static TOMBSTONE = Symbol("TOMBSTONE");
// Maps for assigning unique IDs to object and symbol keys (for hashing):
private objectKeyIds = new WeakMap<object, number>();
private symbolKeyIds = new Map<symbol, number>();
private nextObjectId = 1;
private nextSymbolId = 1;
constructor(initialCapacity: number = 16, maxLoadFactor: number = 0.75) {
this.totalSize = 0;
this.maxLoadFactor = maxLoadFactor;
// Determine sub-array partition sizes:
const levelsCap: number[] = this.partitionLevels(initialCapacity);
this.levels = levelsCap.map(cap => ({
table: new Array(cap).fill(undefined),
size: 0
}));
// Initialize random salts for each level (for double hashing probes):
this.salts = levelsCap.map(() => ({
base: Math.floor(Math.random() * 0xffffffff) >>> 0,
step: Math.floor(Math.random() * 0xffffffff) >>> 0
}));
this.head = this.tail = null;
}
/** Partition total capacity into sub-array sizes (each ~half the previous). */
private partitionLevels(n: number): number[] {
if (n < 1) n = 1;
const levels: number[] = [];
// Determine number of levels (m ≈ ⌈log2 n⌉):
const m = Math.ceil(Math.log2(n));
let remaining = n;
if (m < 1) {
// n is 1
levels.push(remaining);
return levels;
}
for (let i = 1; i < m; i++) {
// For levels 1 .. m-1, allocate roughly half of remaining
let size = (i === m - 1)
? Math.ceil(remaining / 2) // use ceil for second-last level
: Math.floor(remaining / 2);
if (size < 1) size = 1;
levels.push(size);
remaining -= size;
}
// Last level gets the rest:
if (remaining > 0) levels.push(remaining);
return levels;
}
/** Hash function: returns a 32-bit integer for the given key. */
private hashCode(key: K): number {
// If key is number or big int:
if (typeof key === "number") {
// Use multiplicative hashing for numbers (spread bits):
let x = key | 0;
x ^= x >>> 16;
x = Math.imul(x, 0x85ebca6b);
x ^= x >>> 13;
x = Math.imul(x, 0xc2b2ae35);
x ^= x >>> 16;
return x >>> 0;
}
if (typeof key === "bigint") {
// Hash by splitting into lower 32 bits:
const x = Number(key & BigInt(0xffffffff));
return this.hashCode(x as any);
}
// If key is string:
if (typeof key === "string") {
// Compute a simple polynomial rolling hash:
let h = 0;
const len = key.length;
for (let i = 0; i < len; i++) {
h = (h * 31 + key.charCodeAt(i)) | 0;
}
return h >>> 0;
}
// If key is boolean:
if (typeof key === "boolean") {
return key ? 0xAAAAAAAA : 0x55555555; // two distinctive 32-bit patterns
}
// If key is symbol:
if (typeof key === "symbol") {
let id = this.symbolKeyIds.get(key);
if (id === undefined) {
id = this.nextSymbolId++;
this.symbolKeyIds.set(key, id);
}
// Mix the symbol id into a hash:
return this.hashCode(id as any);
}
// If key is an object or function:
if (typeof key === "object" || typeof key === "function") {
let id = this.objectKeyIds.get(key);
if (id === undefined) {
id = this.nextObjectId++;
this.objectKeyIds.set(key, id);
}
// Mix the object id into a hash:
return this.hashCode(id as any);
}
// Fallback: treat as string
return this.hashCode(String(key) as any);
}
/** Internal helper to find an entry's node and its location (for get/delete). */
private findEntry(key: K): { node: { key: K, value: V, next: any, prev: any } | null, level: number, index: number } {
const hash = this.hashCode(key);
const δ = 1 - this.maxLoadFactor; // slack fraction
const logInvDelta = Math.log2(1/δ);
// Iterate through levels:
for (let i = 0; i < this.levels.length; i++) {
const levelSize = this.levels[i].table.length;
// Determine probe attempt limit for this level (if not last level):
const isLastLevel = (i === this.levels.length - 1);
let attemptLimit = isLastLevel ? levelSize : Math.floor(2 * Math.min(Math.log2(levelSize / (levelSize - this.levels[i].size || 1)), logInvDelta));
if (attemptLimit < 1) attemptLimit = 1;
// Probe sequence in level i:
const baseSalt = this.salts[i].base;
const stepSalt = this.salts[i].step;
// Double hashing parameters:
const baseIndex = (hash ^ baseSalt) % levelSize;
let step = (hash ^ stepSalt) % levelSize;
if (step === 0) step = 1; // step must be non-zero
let foundEmpty = false;
for (let j = 0; j < attemptLimit; j++) {
const idx = (baseIndex + j * step) % levelSize;
const slot = this.levels[i].table[idx];
if (slot === undefined) {
// Empty slot encountered
foundEmpty = true;
break; // no entry here, so key cannot be in this level beyond this point
}
if (slot === ElasticHashMap.TOMBSTONE) {
// Treat tombstone as occupied (just skip it for search)
continue;
}
// We have a live entry
const node = slot as { key: K, value: V, next: any, prev: any };
if (Object.is(node.key, key)) {
// Found the key
return { node, level: i, index: idx };
}
}
if (!isLastLevel) {
// If not found in this level, move to next level and continue search
// (regardless of foundEmpty or not, since if no empty found in these attempts,
// the insertion logic would have placed the key in a higher level).
continue;
} else {
// Last level: if we didn't find the key in attemptLimit (which for last is full length),
// the key is not present.
break;
}
}
return { node: null, level: -1, index: -1 };
}
/** Retrieve the value for a given key, or undefined if not found. */
get(key: K): V | undefined {
const result = this.findEntry(key);
return result.node ? result.node.value : undefined;
}
/** Check if the map contains a key. */
has(key: K): boolean {
return !!this.findEntry(key).node;
}
/** Insert or update a key-value pair. */
set(key: K, value: V): this {
// If the key already exists, update its value
const existing = this.findEntry(key);
if (existing.node) {
existing.node.value = value;
return this;
}
// Key not present; prepare to insert a new entry.
// Resize if load factor exceeded:
if (this.totalSize + 1 > this.maxLoadFactor * this.totalCapacity()) {
this.resize(this.totalCapacity() * 2);
}
// Create new node for the entry
const newNode = { key, value, prev: null, next: null };
// Append to insertion-order linked list
if (!this.head) {
this.head = this.tail = newNode;
} else {
newNode.prev = this.tail;
if (this.tail) this.tail.next = newNode;
this.tail = newNode;
}
// Perform insertion probe to find slot
const hash = this.hashCode(key);
const δ = 1 - this.maxLoadFactor;
const logInvDelta = Math.log2(1/δ);
// Insertion: iterate through levels for proper placement
for (let i = 0; i < this.levels.length; i++) {
const levelCap = this.levels[i].table.length;
const isLastLevel = (i === this.levels.length - 1);
// Determine threshold conditions:
const level = this.levels[i];
const nextLevel = !isLastLevel ? this.levels[i+1] : undefined;
const emptiness_i = 1 - (level.size / levelCap);
const emptiness_next = nextLevel ? (1 - (nextLevel.size / nextLevel.table.length)) : 1;
// Cases based on fullness:
let attemptLimit = 0;
if (!isLastLevel && emptiness_i > δ/2 && emptiness_next > 0.25) {
// Case 1: A_i is sufficiently empty and A_{i+1} not too full – try limited probes in A_i
attemptLimit = Math.floor(2 * Math.min(Math.log2(1/emptiness_i), logInvDelta));
if (attemptLimit < 1) attemptLimit = 1;
} else if (!isLastLevel && emptiness_i <= δ/2) {
// Case 2: A_i too full – skip to next level directly
continue; // move to next level without probing A_i at all
} else {
// Case 3 (or last level): either next level is very full or this is the last level.
// We will place in A_i greedily (use full probe sequence if needed).
attemptLimit = isLastLevel ? levelCap : levelCap;
}
// Compute double-hash probe parameters for level i
const baseSalt = this.salts[i].base;
const stepSalt = this.salts[i].step;
const levelTable = level.table;
const baseIndex = (hash ^ baseSalt) % levelCap;
let step = (hash ^ stepSalt) % levelCap;
if (step === 0) step = 1;
let insertIdx: number | null = null;
for (let j = 0; j < attemptLimit; j++) {
const idx = (baseIndex + j * step) % levelCap;
const slot = levelTable[idx];
if (slot === undefined || slot === ElasticHashMap.TOMBSTONE) {
insertIdx = idx;
// We don't break immediately; instead, we could continue to see if the key exists later.
// But since we've confirmed the key doesn't exist in lower levels and not in this level up to j,
// we can safely choose this slot for insertion.
break;
}
}
if (insertIdx !== null) {
// Found a free slot in current level to insert
level.table[insertIdx] = newNode;
level.size++;
this.totalSize++;
return this;
}
// If we exit the loop without finding a slot (i.e., no free slot in attempt range):
// move to next level and continue (the key will be placed in a higher array).
// Note: If this was the last level and no slot found (which means table is full), we handle by resizing.
if (isLastLevel) {
// As a safety, if last level had no space (shouldn't happen under load factor limit), resize and retry.
this.resize(this.totalCapacity() * 2);
return this.set(key, value); // retry insertion after resizing
}
// Otherwise, loop continues to next level i+1
}
return this;
}
/** Remove a key from the map. Returns true if the key was found and removed. */
delete(key: K): boolean {
const result = this.findEntry(key);
if (!result.node) {
return false; // key not found
}
const { node, level, index } = result;
// Remove from linked list (iteration order)
if (node.prev) node.prev.next = node.next;
if (node.next) node.next.prev = node.prev;
if (node === this.head) this.head = node.next;
if (node === this.tail) this.tail = node.prev;
// Mark slot as a tombstone
this.levels[level].table[index] = ElasticHashMap.TOMBSTONE;
this.levels[level].size--;
this.totalSize--;
return true;
}
/** Remove all entries from the map. */
clear(): void {
// Reset all levels
for (let lvl of this.levels) {
lvl.table.fill(undefined);
lvl.size = 0;
}
// Reset size and linked list
this.totalSize = 0;
this.head = this.tail = null;
// Reset key ID maps for objects/symbols
this.objectKeyIds = new WeakMap<object, number>();
this.symbolKeyIds.clear();
this.nextObjectId = 1;
this.nextSymbolId = 1;
}
/** Total capacity (number of slots) of the hash table across all levels. */
private totalCapacity(): number {
return this.levels.reduce((sum, lvl) => sum + lvl.table.length, 0);
}
/** Resize the table to a new total capacity (re-partition levels and rehash entries). */
private resize(newCapacity: number): void {
const oldEntries: { key: K, value: V }[] = [];
// Collect all existing entries
for (let node = this.head; node; node = node.next) {
oldEntries.push({ key: node.key, value: node.value });
}
// Reinitialize levels with new partition sizes
const newLevelsCap = this.partitionLevels(newCapacity);
this.levels = newLevelsCap.map(cap => ({
table: new Array(cap).fill(undefined),
size: 0
}));
this.salts = newLevelsCap.map(() => ({
base: Math.floor(Math.random() * 0xffffffff) >>> 0,
step: Math.floor(Math.random() * 0xffffffff) >>> 0
}));
// Reinsert all entries (this will rebuild the linked list too)
// Save current insertion order list, then reconstruct it:
const entriesInOrder = oldEntries; // (already in insertion order)
this.head = this.tail = null;
this.totalSize = 0;
for (let { key, value } of entriesInOrder) {
// Create a fresh node for each (to avoid carrying old links)
const node = { key, value, prev: null, next: null };
if (!this.head) {
this.head = this.tail = node;
} else {
node.prev = this.tail;
if (this.tail) this.tail.next = node;
this.tail = node;
}
// Insert into levels (similar to set, but we know no duplicates)
const hash = this.hashCode(key);
const δ = 1 - this.maxLoadFactor;
const logInvDelta = Math.log2(1/δ);
for (let i = 0; i < this.levels.length; i++) {
const level = this.levels[i];
const levelCap = level.table.length;
const isLastLevel = (i === this.levels.length - 1);
const emptiness_i = 1 - (level.size / levelCap);
const emptiness_next = !isLastLevel ? (1 - (this.levels[i+1].size / this.levels[i+1].table.length)) : 1;
let attemptLimit = 0;
if (!isLastLevel && emptiness_i > δ/2 && emptiness_next > 0.25) {
attemptLimit = Math.floor(2 * Math.min(Math.log2(1/emptiness_i), logInvDelta));
if (attemptLimit < 1) attemptLimit = 1;
} else if (!isLastLevel && emptiness_i <= δ/2) {
continue;
} else {
attemptLimit = isLastLevel ? levelCap : levelCap;
}
const baseSalt = this.salts[i].base;
const stepSalt = this.salts[i].step;
const baseIndex = (hash ^ baseSalt) % levelCap;
let step = (hash ^ stepSalt) % levelCap;
if (step === 0) step = 1;
let insertIdx: number | null = null;
for (let j = 0; j < attemptLimit; j++) {
const idx = (baseIndex + j * step) % levelCap;
const slot = level.table[idx];
if (slot === undefined || slot === ElasticHashMap.TOMBSTONE) {
insertIdx = idx;
break;
}
}
if (insertIdx !== null) {
level.table[insertIdx] = node;
level.size++;
this.totalSize++;
break; // inserted, break out of level loop
}
// otherwise continue to next level
}
}
}
/** Iterate over keys in insertion order. */
keys(): IterableIterator<K> {
const self = this;
function* generator() {
for (let node = self.head; node; node = node.next) {
yield node.key;
}
}
return generator();
}
/** Iterate over values in insertion order. */
values(): IterableIterator<V> {
const self = this;
function* generator() {
for (let node = self.head; node; node = node.next) {
yield node.value;
}
}
return generator();
}
/** Iterate over [key, value] entries in insertion order. */
entries(): IterableIterator<[K, V]> {
const self = this;
function* generator() {
for (let node = self.head; node; node = node.next) {
yield [node.key, node.value] as [K, V];
}
}
return generator();
}
/** Default iterator (for `for...of` loops) yields [key, value] pairs. */
[Symbol.iterator](): IterableIterator<[K, V]> {
return this.entries();
}
}Explanation: The ElasticHashMap manages an array of levels (this.levels), each with a fixed capacity. We partition the total capacity into geometrically decreasing sizes (GitHub - MWARDUNI/ElasticHashing: This is a proof of concept for implementing Elastic Hashing to create a new type of hash table without reordering elements while achieving optimal probe complexity.) using partitionLevels. Each level has a random salt for hashing, used to generate a double-hashed probe sequence (given a key’s 32-bit hash, we XOR with a level-specific salt for the base index and step size). This yields a pseudo-random probe order within each sub-array.
-
Insertion (
set): When adding a new key, we first check if it already exists (to update in place). If not, we possibly resize the table if the global load factor would exceedmaxLoadFactorafter insertion. Then we append the new entry to the linked list (for iteration order). We iterate through the levels from A1 upwards. For each leveli, we compute the emptiness of Ai and Ai+1 (fraction of slots free) to decide which case to follow ().-
Case 1: If Ai is still relatively empty (above δ/2 free) and Ai+1 isn’t close to full (> 25% free), we try a limited number of probes in Ai. The attempt limit
f(ε)is set proportional tomin(log₂(1/ε_i), log₂(1/δ))() (we multiply by 2 as a constant factor; in theory c would be a larger constant ()). We search for the first free slot (either truly empty or a tombstone, which we treat as free) within those attempts. If found, we insert the item there and finish. If no free slot is found in that range, we defer the insertion to the next level (i+1). -
Case 2: If Ai is too full (≤ δ/2 free slots), we skip it entirely (no probes) and move the insertion to the next level ().
-
Case 3: If Ai+1 is very full (≤ 25% free) or we are at the last level, we treat Ai greedily – essentially probing until we find a spot in Ai (this is the “expensive case” which is rare ()). In the implementation, we set the attempt limit to the full level size in this scenario.
The new entry is placed in the first available slot according to the above logic, and the sizes are updated. Because each level always retains some free slots (δ/2 fraction) until we move past it, the probe sequences remain short on average (). If we ever reach the final level and find no slot (which shouldn’t happen if we respect the load factor), we trigger a resize as a fallback.
-
-
Lookup (
get/has): We traverse the levels similarly to insertion. For each level, we probe up to the samef(ε)attempts. If we encounter the key, we return it. If we hit an empty slot in a level before exhausting the attempts, we break early to move to the next level (because an empty slot in Ai indicates the key would not have been placed further in Ai> – it would have been inserted there if present). We treat tombstones as filled (so the search doesn’t prematurely terminate) but skip over them. By following the same pattern as insertion, we ensure we don’t miss a key that was inserted in a higher level. In the last level, we probe until we either find the key or confirm an empty slot (meaning the key isn’t in the table). This multi-level search remains efficient: in expectation the number of probes is O(1) on average, and O(log δ−1) in the worst-case expected sense (). -
Deletion (
delete): We locate the key similarly toget. If found, we remove its node from the linked list and mark the slot with a specialTOMBSTONE. We decrement the level’s size (tombstones count as free for load factor). Tombstones ensure that lookups that traversed this slot when it was occupied will continue to probe further levels correctly. New insertions will reuse tombstone slots just like empty ones (treated as “first free slot” available). Over time, if many tombstones accumulate, an occasional resize (rehashing) can clean them up. -
Iteration (
keys(),values(),entries()): We maintain aprev/nextlinked list in each node to preserve insertion order. The iterator methods traverse this list fromheadtotail, yielding keys, values, or[key, value]pairs. This matches the behavior of JavaScript’sMap.prototype.keys(), etc. The[Symbol.iterator]is also defined to return entries, so the map is iterable withfor..of. -
Resizing: When the overall load factor exceeds the chosen maximum (e.g. 0.75), we allocate a new set of levels with roughly double total capacity, and reinsert all existing entries. Reinsertion iterates over entries in insertion order and places them into the new levels following the elastic hashing rules. This operation is O(n), but amortized over growth it maintains average O(1) insertion cost.
You can use ElasticHashMap just like a regular Map:
const map = new ElasticHashMap<string, number>(16, 0.75);
map.set("alice", 1);
map.set("bob", 2);
console.log(map.get("alice")); // 1
console.log(map.has("carol")); // false
map.set("alice", 42); // update value
map.delete("bob"); // remove key "bob"
for (const [key, val] of map) {
console.log(key, val);
}This custom hash map will preserve insertion order in iteration and support all typical operations. Internally, it distributes keys across multiple sub-arrays and limits clustering, achieving high performance even at high load factors. By ensuring each segment of the table keeps some slack and by avoiding long contiguous probe sequences, it sidesteps the heavy tail of probe costs seen in traditional open addressing at high loads (). The result is a hash map with optimal expected probe complexity — constant on average and logarithmic in the inverse of free-space fraction in the worst case (), as proven in the research paper.
References: