Building a Time-Traveling HashMap in JavaScript

Source: Dev.to

Introduction

A standard Hash Map (or dictionary) maps keys to values for quick data retrieval.
When an application needs to access a previous state of that data, a Time‑Travelling HashMap can be used. It stores multiple versions of values for the same key based on their insertion time, allowing queries like get(key, timestamp) to retrieve the value that existed at a specific moment.

Functional Requirements

• Constant‑time insertion – set(key, value) must run in O(1). The insertion time is recorded exactly.
• Time‑based retrieval – get(key, t) returns the value that would have been seen at time t.
• Closest past fallback – If no entry exists for the exact timestamp, the map returns the most recent value whose timestamp is ≤ t.
  Example: updates at times 1 and 2, a query for 1.5 returns the value from time 1.

Implementation Overview

The JavaScript implementation uses two internal Map objects:

The composite key guarantees uniqueness, while the ledger keeps the history sorted because new entries are appended.

set Method

class TimeTravellingHashMap {
  constructor() {
    this._map = new Map();               // compositeKey → value
    this._keyLookUpTable = new Map();    // baseKey → [compositeKey, ...]
    this._separator = Symbol('separator');
  }

  set(key, value) {
    const timestamp = new Date().toISOString();
    const compositeKey = `${key}${this._separator.toString()}${timestamp}`;

    // Store the value
    this._map.set(compositeKey, value);

    // Update the ledger
    if (!this._keyLookUpTable.has(key)) {
      this._keyLookUpTable.set(key, []);
    }
    this._keyLookUpTable.get(key).push(compositeKey);
  }

• Generates a composite key by concatenating the original key, a unique Symbol separator, and the current ISO timestamp.
• Saves the value in _map.
• Appends the composite key to the history array for the base key in _keyLookUpTable. The array remains chronologically ordered.

get Method

  get(key, time) {
    const ledger = this._keyLookUpTable.get(key);
    if (!ledger) return undefined;

    // Try exact match first
    const exactKey = `${key}${this._separator.toString()}${time}`;
    if (this._map.has(exactKey)) {
      return this._map.get(exactKey);
    }

    // Fallback: find the closest past entry
    for (let i = ledger.length - 1; i >= 0; i--) {
      const compositeKey = ledger[i];
      const entryTime = this._getTimeFromKey(compositeKey);
      if (entryTime  {
  const timeToRound = new Date().toISOString(); // captured after v1
  map.set('myKey', 'v2');             // t1 (later)

  // Query using the earlier timestamp
  const result = map.get('myKey', timeToRound);
  console.log(result); // → 'v1'
}, 10);

• v1 is inserted first.
• After a short delay, the current timestamp (timeToRound) is captured.
• v2 is inserted later.
• Querying with timeToRound returns 'v1', confirming that the map correctly falls back to the closest past value.

Conclusion

The Time‑Travelling HashMap demonstrates how composite keys and a chronological ledger can provide versioned state management without overwriting older data. This pattern enables features such as undo/redo, historical queries, and lightweight version control in JavaScript applications.

Reference

• GitHub repository: time‑travelling‑hashmap