JavaScriptライブラリであるlodashでは、Mapのような機能をエミュレートするためにListCacheというデータ構造が実装されています。このキャッシュ機構は、環境がネイティブなMapをサポートしていない場合に代替手段として利用されます。

目的と利用方法

Hashキャッシュではオブジェクトベースのストレージを使用しており、キーとして文字列またはSymbol型しか受け付けません。これに対してMapは任意の型をキーとして使用できるため、Hashキャッシュでは配列やオブジェクトなどの複雑な型をキーとした場合に対応できません。

ListCacheは二次元配列構造を利用してデータを保存し、以下のように使用します：

const cacheInstance = new ListCache([
  [{identifier: 'ObjectBasedKey'}, 100],
  [['ArrayBasedKey'], 200],
  [function(){return 'FunctionAsKey'}, 300]
]);

この構造は次のような形式でデータを保持します：

{
  size: 3,
  __storage__: [
    [{identifier: 'ObjectBasedKey'}, 100],
    [['ArrayBasedKey'], 200],
    [function(){return 'FunctionAsKey'}, 300]
  ]
}

インターフェース設計

ListCacheはMapと同様のAPIを提供し、標準的なマップ操作メソッドを実装しています。

依存関係

import findEntryIndex from './findEntryIndex.js'

実装詳細

class ListCache {
  
  constructor(initialEntries) {
    let currentIndex = -1;
    const totalEntries = initialEntries == null ? 0 : initialEntries.length;

    this.reset();
    while (++currentIndex < totalEntries) {
      const currentEntry = initialEntries[currentIndex];
      this.assign(currentEntry[0], currentEntry[1]);
    }
  }

  reset() {
    this.__storage__ = [];
    this.size = 0;
  }

  remove(targetKey) {
    const storage = this.__storage__;
    const targetIndex = findEntryIndex(storage, targetKey);

    if (targetIndex < 0) {
      return false;
    }
    const finalIndex = storage.length - 1;
    if (targetIndex === finalIndex) {
      storage.pop();
    } else {
      storage.splice(targetIndex, 1);
    }
    --this.size;
    return true;
  }

  retrieve(targetKey) {
    const storage = this.__storage__;
    const foundIndex = findEntryIndex(storage, targetKey);
    return foundIndex < 0 ? undefined : storage[foundIndex][1];
  }

  exists(targetKey) {
    return findEntryIndex(this.__storage__, targetKey) > -1;
  }

  assign(key, value) {
    const storage = this.__storage__;
    const existingIndex = findEntryIndex(storage, key);

    if (existingIndex < 0) {
      ++this.size;
      storage.push([key, value]);
    } else {
      storage[existingIndex][1] = value;
    }
    return this;
  }
}

コンストラクタ

初期化処理ではresetメソッドを呼び出して内部状態を初期化し、渡されたエントリーデータをassignメソッドを使ってキャッシュに追加していきます。resetメソッドは__storage__とsizeプロパティの初期化を担当します。

resetメソッド

reset() {
  this.__storage__ = [];
  this.size = 0;
}

キャッシュをクリアする処理で、ストレージを空の配列に設定し、要素数を0にリセットします。

existsメソッド

exists(key) {
  return findEntryIndex(this.__storage__, key) > -1;
}

指定されたキーを持つデータがキャッシュ内に存在するかを判定します。findEntryIndex関数は二次元配列内で対応する[key, value]ペアのインデックスを検索し、存在しない場合は-1を返します。

assignメソッド

assign(key, value) {
  const storage = this.__storage__;
  const index = findEntryIndex(storage, key);

  if (index < 0) {
    ++this.size;
    storage.push([key, value]);
  } else {
    storage[index][1] = value;
  }
  return this;
}

キャッシュへの値の追加または更新を行います。既存のキーが見つからない場合はサイズを増加させ新しいペアを追加し、既存の場合は値を上書きします。

retrieveメソッド

retrieve(key) {
  const storage = this.__storage__;
  const index = findEntryIndex(storage, key);
  return index < 0 ? undefined : storage[index][1];
}

キャッシュから指定されたキーに対応する値を取得します。存在しない場合はundefinedを返却します。

removeメソッド

remove(key) {
  const storage = this.__storage__;
  const index = findEntryIndex(storage, key);

  if (index < 0) {
    return false;
  }
  const lastPosition = storage.length - 1;
  if (index === lastPosition) {
    storage.pop();
  } else {
    storage.splice(index, 1);
  }
  --this.size;
  return true;
}

指定されたキーを持つエントリを削除します。削除対象が最終要素の場合にはpopメソッドを使用し、それ以外はspliceメソッドを使用することでパフォーマンスを最適化しています。popメソッドはspliceよりも約17%高速であることが確認されています。