マップ（連想配列）では、キーと値のペアでデータを管理する。キーを一意に識別するために、文字列変換関数を用いることが多い。以下は、シンプルな辞書（Dictionary）クラスの実装例である。

// オブジェクトのキーを文字列に変換する補助関数
function keyToString(item) {
  if (item === null) return "NULL";
  if (item === undefined) return "UNDEFINED";
  if (typeof item === "string" || item instanceof String) return `${item}`;
  return item.toString();
}

// キーと値のペアを表すクラス
class Pair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
  toString() {
    return `[#${this.key}:${this.value}]`;
  }
}

// 辞書クラス
class Dict {
  constructor(toStr = keyToString) {
    this.toStr = toStr;
    this.data = {};
  }

  has(key) {
    return this.data[this.toStr(key)] !== undefined;
  }

  set(key, value) {
    if (key == null || value == null) return false;
    const mappedKey = this.toStr(key);
    this.data[mappedKey] = new Pair(key, value);
    return true;
  }

  delete(key) {
    if (!this.has(key)) return false;
    delete this.data[this.toStr(key)];
    return true;
  }

  get(key) {
    const pair = this.data[this.toStr(key)];
    return pair == null ? undefined : pair.value;
  }

  entries() {
    return Object.values(this.data);
  }

  keys() {
    return this.entries().map(p => p.key);
  }

  values() {
    return this.entries().map(p => p.value);
  }

  forEach(callback) {
    const pairs = this.entries();
    for (let i = 0; i < pairs.length; i++) {
      const p = pairs[i];
      if (callback(p.key, p.value) === false) break;
    }
  }

  size() {
    return Object.keys(this.data).length;
  }

  isEmpty() {
    return this.size() === 0;
  }

  clear() {
    this.data = {};
  }

  toString() {
    if (this.isEmpty()) return "";
    const pairs = this.entries();
    let result = pairs[0].toString();
    for (let i = 1; i < pairs.length; i++) {
      result += `,${pairs[i].toString()}`;
    }
    return result;
  }
}

ハッシュテーブルによる高速な値の検索

ハッシュ関数は、キーからテーブル内のインデックスを計算する。適切なハッシュ関数を選ぶことで、挿入・検索・削除がほぼ定数時間で行える。以下は、文字列の各文字のコードを使ってハッシュ値を生成する実装である。

class HashStore {
  constructor(toStr = keyToString) {
    this.toStr = toStr;
    this.table = {};
  }

  // 内部ハッシュ関数（文字列の各文字コードを利用）
  _hash(key) {
    if (typeof key === "number") return key;
    const str = this.toStr(key);
    let hash = 5381;
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 33) + str.charCodeAt(i);
    }
    return hash % 1013;
  }

  hashCode(key) {
    return this._hash(key);
  }

  put(key, value) {
    if (key == null || value == null) return false;
    const pos = this.hashCode(key);
    this.table[pos] = new Pair(key, value);
    return true;
  }

  get(key) {
    const pos = this.hashCode(key);
    const pair = this.table[pos];
    return pair == null ? undefined : pair.value;
  }

  remove(key) {
    const pos = this.hashCode(key);
    const pair = this.table[pos];
    if (pair == null) return false;
    delete this.table[pos];
    return true;
  }
}

ハッシュ衝突の対処法

異なるキーが同じハッシュ値になる衝突は避けられない。主な解決策として以下の二つがある。

• チェイン法（セパレートチェイニング）：各バケットに連結リストなどを用意し、衝突した要素を同じバケットに格納する。実装は簡単だが、リストの管理のために追加のメモリが必要。
• オープンアドレス法（線形探索法）：衝突が発生した場合、次の空きバケットを順に調べる。データをテーブル内に直接格納するため、メモリ効率は良いが、削除操作が複雑になる。