JavaScript에서 시간 여행 HashMap 구축하기

Source: Dev.to

소개

표준 해시 맵(또는 딕셔너리)은 키를 값에 매핑하여 빠른 데이터 검색을 가능하게 합니다.
애플리케이션이 데이터의 이전 상태에 접근해야 할 때는 **시간 여행 해시맵(Time‑Travelling HashMap)**을 사용할 수 있습니다. 이 맵은 삽입 시점을 기준으로 같은 키에 대한 여러 버전의 값을 저장하므로 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

사용 예시

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'이 반환되며, 맵이 가장 가까운 과거 값을 올바르게 반환함을 확인할 수 있습니다.

결론

시간 여행 해시맵은 복합 키와 시간 순서 장부를 활용해 이전 데이터를 덮어쓰지 않으면서 버전 관리된 상태를 제공하는 방법을 보여줍니다. 이 패턴을 통해 JavaScript 애플리케이션에서 undo/redo, 히스토리 조회, 경량 버전 관리와 같은 기능을 손쉽게 구현할 수 있습니다.

참고

• GitHub repository: time‑travelling‑hashmap