萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 實作 Map 集合資料結構完整教學

前言

ES6 內建 Map 物件提供鍵值對集合,鍵可為任意型別。本文示範如何**從零手寫一個 Map 類別**,涵蓋增刪改查、迭代、擴充方法,深入理解雜湊表與鏈結清單結合的實作原理。

核心資料結構設計

  • hashmap:物件雜湊表,key -> value 快速查找 O(1)。
  • keys[]、vals[]、entrys[]:維持插入順序的陣列,支援疊代。
  • index:記錄 key -> 陣列索引,實現 O(1) 刪除/更新。
  • size:當前元素數量。

完整實作代碼 (ES5 風格)

var Map = function() {
  // 私有儲存
  var hashmap = {}, keys = [], vals = [], entrys = [], size = 0, index = {};

  // 內部 Entry 類別
  var Entry = function(key, value) {
    this.getKey = function() { return key; };
    this.getValue = function() { return value; };
  };

  // 基礎方法
  this.put = function(key, value) {
    if (!this.get(key)) { // 新增
      var entry = new Entry(key, value);
      entrys.push(entry);
      keys.push(key);
      vals.push(value);
      index[key] = size++;
    } else { // 更新
      var i = index[key];
      entrys[i] = new Entry(key, value);
      vals[i] = value;
    }
    hashmap[key] = value;
  };

  this.get = function(key) { return hashmap[key]; };

  this.remove = function(key) {
    if (!this.get(key)) return undefined;
    var i = index[key];
    var val = vals[i];
    // 陣列移除 (O(n) 但 size 通常較小)
    entrys.splice(i, 1);
    vals.splice(i, 1);
    keys.splice(i, 1);
    // 更新後續索引
    for (var k = i; k < keys.length; k++) index[keys[k]] = k;
    delete hashmap[key];
    size--;
    return val;
  };

  this.clear = function() {
    hashmap = {}; keys = []; vals = []; entrys = []; index = {}; size = 0;
  };

  this.size = function() { return size; };
  this.isEmpty = function() { return size === 0; };
  this.keySet = function() { return keys.slice(); };
  this.values = function() { return vals.slice(); };
  this.entrySet = function() { return entrys.slice(); };
  this.containsKey = function(key) { return key in hashmap; };
};

// 原型擴充 (可選)
Map.prototype.putAll = function(map) {
  map.entrySet().forEach(function(e) { this.put(e.getKey(), e.getValue()); }, this);
};

使用範例

var m = new Map();
m.put('a', 10);
m.put('b', 20);
m.put('c', 30);
console.log(m.size());        // 3
console.log(m.get('b'));      // 20
console.log(m.containsKey('a')); // true
m.remove('b');
console.log(m.size());        // 2
console.log(m.keySet());      // ["a", "c"]
console.log(m.values());      // [10, 30]

// 疊代
m.entrySet().forEach(function(e) {
  console.log(e.getKey() + ':' + e.getValue());
});

ES6 類別寫法 (現代語法)

class MyMap {
  constructor() {
    this._map = {};
    this._keys = [];
    this._vals = [];
    this._index = {};
    this._size = 0;
  }

  put(key, value) {
    if (!(key in this._map)) {
      this._keys.push(key);
      this._index[key] = this._size++;
    }
    this._map[key] = value;
    this._vals[this._index[key]] = value;
  }

  get(key) { return this._map[key]; }
  has(key) { return key in this._map; }
  delete(key) {
    if (!this.has(key)) return false;
    const i = this._index[key];
    this._keys.splice(i, 1);
    this._vals.splice(i, 1);
    delete this._map[key];
    // 重建索引
    this._keys.forEach((k, idx) => this._index[k] = idx);
    this._size--;
    return true;
  }
  get size() { return this._size; }
  keys() { return [...this._keys]; }
  values() { return [...this._vals]; }
  entries() { return this._keys.map(k => [k, this._map[k]]); }
  clear() { this._map={}; this._keys=[]; this._vals=[]; this._index={}; this._size=0; }
  *[Symbol.iterator]() { for (const k of this._keys) yield [k, this._map[k]]; }
}

與 ES6 內建 Map 比較

特性手寫 Map內建 Map
鍵型別字串化 (物件鍵會 toString)任意型別 (物件參考)
順序保證插入順序插入順序
效能O(1) 平均,但刪除 O(n) 因陣列搬移高度優化 O(1)
可疊代手動實作內建 for...of, forEach
序列化需自行實作需自行實作

總結

手寫 Map 能深入理解「雜湊表 + 陣列維持順序」的經典設計模式。實務專案**請直接使用內建 Map**,它支援物件鍵、效能更強、API 完整。本文實作適合教學、面試準備或特殊環境 (如極舊瀏覽器無 Polyfill 空間) 參考。

copyright © 萬盛學電腦網 all rights reserved