在 JavaScript 中构建时间旅行的 HashMap

It looks like the text you’d like translated isn’t included in your message. Could you please paste the content you want translated (excluding the source line you already provided)? Once I have the full text, I’ll translate it into Simplified Chinese while preserving the formatting and code blocks.

介绍

标准哈希映射（或字典）将键映射到值，以实现快速数据检索。
当应用程序需要访问该数据的先前状态时，可以使用时光旅行哈希映射。它根据插入时间为同一键存储多个版本的值，允许使用诸如 get(key, timestamp) 之类的查询来检索特定时刻存在的值。

功能需求

• 常数时间插入 – set(key, value) 必须在 O(1) 时间内运行。插入时间被精确记录。
• 基于时间的检索 – get(key, t) 返回在时间 t 时应看到的值。
• 最近的过去回退 – 如果没有恰好对应时间戳的条目，映射返回时间戳 ≤ t 的最近值。
  示例：在时间 1 和 2 有更新，对时间 1.5 的查询返回时间 1 的值。

实现概述

JavaScript 实现使用两个内部 Map 对象：

复合键保证唯一性，而账本通过追加新条目保持历史记录的排序。

set 方法

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);
  }

• 通过连接原始键、唯一的 Symbol 分隔符以及当前的 ISO 时间戳来生成复合键。
• 将值保存到 _map 中。
• 将复合键追加到 _keyLookUpTable 中对应基键的历史数组中。该数组保持按时间顺序排列。

get 方法

  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

### 使用示例

```javascript
const map = new TimeTravellingHashMap();
map.set('myKey', 'v1'); // t0

setTimeout(() => {
  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 首先被插入。
• 短暂延迟后，捕获当前时间戳 (timeToRound)。
• v2 随后被插入。
• 使用 timeToRound 查询返回 'v1'，确认映射正确回退到最近的过去值。

结论

Time‑Travelling HashMap 演示了复合键和时间账本如何提供带版本的状态管理，而不会覆盖旧数据。该模式在 JavaScript 应用中实现了撤销/重做、历史查询以及轻量级版本控制等功能。

参考

• GitHub 仓库: time‑travelling‑hashmap