DIV CSS 佈局教程網

用 JavaScript 手寫實現 Map 集合類
編輯:JavaScript綜合知識     

ES6 之前 JavaScript 沒有原生的 Map,開發者常用普通對象冒充鍵值集合。但對象的鍵只能是字符串,且 for...in 會枚舉到原型上的屬性。本文動手實現一個更接近 Java Map 語義的結構,這個過程對理解哈希表很有幫助。

實現代碼

var Map = function () {
  /************ 內部狀態 ************/
  var hashmap = {};   // 用對象做哈希索引,負責 O(1) 查找
  var keys = [];      // 鍵數組,保證遍歷順序
  var vals = [];      // 值數組
  var entrys = [];    // Entry 對象數組
  var size = 0;
  var index = {};     // 鍵到數組下標的映射

  // Entry 用閉包實現私有字段
  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);
  },
  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());
}

設計思路與缺陷

核心取捨是「用空間換遍歷順序」:同時維護哈希表和有序數組,查找走哈希達到 O(1),遍歷走數組保持插入順序。

不過這個實現有幾處明顯不足,值得注意:

  • if (!this.get(key)) 用真假值判斷鍵是否存在,當值為 0、空字符串或 false 時會誤判為不存在。
  • clear() 用 splice 刪數組元素是 O(n) 操作,刪除频繁時性能不佳。
  • 鍵被強制成字符串,對象鍵會變成 "[object Object]"。

這些正是原生 Map 要解決的問題:它支持任意類型作鍵、用 SameValueZero 演算法判斷鍵相等、並保證遍歷順序為插入順序。今天的項目裡直接用 new Map() 就好,手寫一遍的價值主要在於理解底層取捨。

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