Open-Addressing Robin Hood Hash Map with Backward-Shift Deletion

Overview

An open-addressed hash table implementing Celis Robin Hood displacement, early-exit lookups on PSL ordering, and tombstone-free backward-shift deletion.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Probe Sequence Length (PSL) Arithmetic on Power-of-2 Ring

• Core Mechanical Concept: Measuring Cyclic Probe Distance via Bitmask Subtraction
• Target Module: index.js (RobinHoodHashMap._psl)
• Engineering Specification: Implement _psl(slotIdx, idealIdx) to compute how many linear probes an entry at slotIdx has traveled from idealIdx. In a power-of-two table, (slotIdx - idealIdx) & this._mask handles wrap-around across index 0 in $O(1)$ without branches.
• Verification Invariant: computes cyclic probe sequence length across wrap-around

Step 2: Robin Hood Displacement Insertion

• Core Mechanical Concept: Stealing Slots from "Rich" Keys (Small PSL) to Give to "Poor" Keys (Large PSL)
• Target Module: index.js (RobinHoodHashMap.set)
• Engineering Specification: Implement set(key, value) with Robin Hood swap semantics. 1. If (this._size + 1) > this._capacity * this._maxLoad, double capacity via this._resize(this._capacity * 2). 2. Walk linearly from idx = this._idealIndex(key). If cur.key === entry.key, overwrite cur.value. 3. If entry.psl > cur.psl, swap entry and this._slots[idx] and continue probing with the displaced entry.
• Verification Invariant: inserts keys and bounds PSL variance via Robin Hood displacement

Step 3: Early-Exit Lookup on PSL Monotonicity

• Core Mechanical Concept: Aborting Unsuccessful Searches When currentPSL > occupantPSL
• Target Module: index.js (RobinHoodHashMap.get)
• Engineering Specification: Implement get(key) with early termination. Because Robin Hood insertion guarantees that any key with a larger psl would have displaced an occupant with a smaller cur.psl, if cur === null || psl > cur.psl, the target key cannot exist further down the probe chain.
• Verification Invariant: terminates lookups early when probe distance exceeds occupant PSL

Step 4: Tombstone-Free Backward-Shift Deletion

• Core Mechanical Concept: Healing Probe Chains by Shifting Displaced Neighbors Left
• Target Module: index.js (RobinHoodHashMap.delete)
• Engineering Specification: Implement delete(key) using backward-shift deletion instead of tombstones. 1. Locate key at idx (returning false if absent). 2. Clear this._slots[idx] = null and decrement this._size. 3. While next = (prev + 1) & _mask is occupied and this._slots[next].psl > 0, shift this._slots[next] into prev, decrement its psl, and advance.
• Verification Invariant: deletes keys via backward-shift without leaving tombstones

Asymptotic & Memory Layout Guarantees

• Category: Hashing & Sketches
• Difficulty: Advanced (~35 minutes)
• Key Architectural Highlights:
  • Probe Sequence Length (PSL) displacement minimizing probe variance
  • Early-exit search termination when current PSL exceeds occupant PSL
  • Tombstone-free backward-shift deletion preventing probe degradation
• Tags & Primitives: Robin Hood Hashing, Open Addressing, Backward-Shift Delete, PSL Variance, FNV-1a

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.