DIV CSS 佈局教程網

用 JavaScript 手寫一個 Map 集合(附 modern 版本對照)
編輯:關於JavaScript     

專案裡常需要「鍵值對 + 可走訪 + 可查尺寸」的資料結構。ES6 之前沒有原生 Map,只能拿物件硬湊;下面先手寫一版理解原理,再對照原生 Map 的寫法。

手寫實作

var Map = function () {
  /************ 內部狀態 ************/
  var hashmap = {};   // key => value,負責快速取值
  var keys = [];      // 鍵的集合
  var vals = [];      // 值的集合
  var entrys = [];    // Entry 物件集合,保留插入順序
  var size = 0;
  var index = {};     // key => 在 entrys 中的索引,供刪除時定位

  // 單一鍵值對的包裝
  var Entry = function (key, value) {
    var entryKey = key;
    var entryValue = value;
    this.getKey = function () { return entryKey; };
    this.getValue = function () { return entryValue; };
  };

  /************ 基本方法 ************/
  this.clear = function (key) {
    hashmap[key] = undefined;
    var i = index[key];
    entrys.splice(i, 1);
    vals.splice(i, 1);
    keys.splice(i, 1);
    size--;
  };

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

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

  this.keySet = function () { return keys; };

  this.put = function (key, value) {
    if (!this.get(key)) {
      entrys.push(new Entry(key, value));
      keys.push(key);
      vals.push(value);
      index[key] = size;
      size++;
    } else {
      var i = index[key];
      entrys[i] = new Entry(key, value);
      vals[i] = value;
    }
    hashmap[key] = value;
  };

  this.size = function () { return size; };
  this.values = function () { return vals; };
};

/************ 擴充方法 ************/
Map.prototype = {
  containsKey: function (key) {
    return this.get(key) !== undefined;
  },
  putAll: function (set) {
    for (var e in set) {
      if (set[e]) this.put(e, set[e]);
    }
  },
  remove: function (key) {
    var v = this.get(key);
    this.clear(key);
    return v;
  }
};

/************ 使用示範 ************/
var h = new Map();
h.put('a', 10);
h.put('b', 11);
h.put('c', 3);
h.put('d', 5);
console.info(h.size());          // 4

h.clear('a');
console.info(h.containsKey('a')); // false
console.info(h.containsKey('b')); // true
console.info(h.size());           // 3

console.log(h.entrySet());
console.log(h.keySet());
console.log(h.values());

for (var i in h.entrySet()) {
  var obj = h.entrySet()[i];
  console.log(obj.getKey() + ":" + obj.getValue());
}

這個實作的兩個缺陷

用 truthy 判斷存在性。if (!this.get(key)) 在值為 0、""、false、null 時會誤判成「不存在」,導致重複寫入而讓 size 與 index 錯亂。正確做法應該是 if (!(key in hashmap)) 或檢查 index 是否有該鍵。

clear 之後索引沒有重排。用 splice 從 entrys 移除一項後,後面所有元素的索引都往前移了,但 index 對應表並未同步更新,之後的 put/clear 就會指到錯誤位置。要修正得在 splice 之後重跑一次索引重建,而這又是 O(n) 的代價。

原生 Map 才是正解

ES6 之後完全不需要自己造輪子。原生 Map 解決了上述所有問題,還支援任意型別作為鍵(物件、函式都可以):

var m = new Map();
m.set('a', 10);
m.set(0, 'zero');          // 數字鍵
m.set(objRef, 'obj');      // 物件也能當鍵,這是普通物件做不到的

m.get('a');                // 10
m.has('a');                // true,判斷存在性不會被 falsy 值誤導
m.size;                    // 屬性,不是函式
m.delete('a');             // true
m.clear();

// 可迭代,且保證插入順序
for (var entry of m) {
  console.log(entry[0], entry[1]);
}
m.forEach(function (value, key) { /* ... */ });

// 從 entries 或物件轉入
new Map([['x', 1], ['y', 2]]);
new Map(Object.entries({ x: 1, y: 2 }));

選擇建議:鍵為字串且資料要序列化成 JSON 時,普通物件夠用;鍵可能是非字串、需要保證順序、或會頻繁增刪時,直接用 Map。手寫版本的價值在於理解「雜湊表 + 索引對應表」這個基本設計思路。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved