DIV CSS 佈局教程網

用 JavaScript 實作 Map 集合工具類
編輯:關於JavaScript     

JavaScript 在 ES6 之前沒有原生的 Map,很多時候只能用物件暫代。但物件有兩個先天問題:鍵只能是字串、無法可靠地取得長度。這個實作用陣列保存 Entry 物件的方式模擬出一套完整的 Map,包含 put、get、remove、size、clear 等方法,是理解資料結構封裝的好例子。

完整程式碼

var Map = function(){

  // 內部 entry 結構:一組鍵值對
  var Entry = function(key, value){
    this.key = key;
    this.value = value;
  };

  this.entries = new Array();

  // 放入一筆;鍵已存在則不覆寫,回傳 false
  this.put = function(key, value){
    for (var i = 0; i < this.size(); i++) {
      if (this.entries[i].key === key) { return false; }
    }
    this.entries.push(new Entry(key, value));
    return true;
  };

  // 依鍵取值,找不到回傳 null
  this.get = function(key){
    for (var i = 0; i < this.size(); i++) {
      if (this.entries[i].key === key) { return this.entries[i].value; }
    }
    return null;
  };

  // 取得鍵所在的下標,找不到回傳 -1
  this.indexOf = function(key){
    var index = -1;
    for (var i = 0; i < this.size(); i++) {
      if (this.entries[i].key === key) { index = i; break; }
    }
    return index;
  };

  // 刪除一筆
  this.remove = function(key){
    var index = this.indexOf(key);
    if (index != -1) { this.entries.splice(index, 1); }
  };

  // 取得長度
  this.size = function(){ return this.entries.length; };

  // 重新設定某鍵的值
  this.setValue = function(key, value){
    var index = this.indexOf(key);
    if (index != -1) { this.entries[index].value = value; }
  };

  // 是否為空
  this.isEmpty = function(){ return this.size() <= 0; };

  // 清空
  this.clear = function(){ this.entries = []; };

  // 依索引取得 entry
  this.getEntry = function(index){
    if (index >= 0 && index < this.size()) { return this.entries[index]; }
    return null;
  };

  // 轉為字串,形如 [key1=value1,key2=value2]
  this.toString = function(){
    var str = "[";
    for (var i = 0; i < this.size(); i++) {
      str += this.getEntry(i).key + "=" + this.getEntry(i).value + ",";
    }
    str = str.substring(0, str.length - 1);   // 去掉最後一個逗號
    str += "]";
    return str;
  };
};

原始版本的三個 bug,已在上文修正

1. setValue 用錯索引變數。原碼寫成 this.entries[i].value = value,但 i 是迴圈內的 var,在函數結束後已不在作用域,會拋出錯誤或直接寫到全域。應改為 this.entries[index]。

2. toString 在空集合時會出錯。entries 為空時 str 只有 "[",substring(0, 0) 之後變成空字串,輸出會變成 "]",少了一個左括號。建議先判空處理。

3. put 的行為與原生 Map 不同。原生 Map 遇到重複鍵會覆寫,這裡卻是放棄並回傳 false。若希望行為一致,把 put 改成「找到就更新、找不到才新增」。

效能上的關鍵差別

這套實作的所有查詢都是線性掃描,時間複雜度 O(n)。原生 Map 基於雜湊表,平均是 O(1)。資料量小(幾十筆)時差異不明顯,但上千筆以上差距會非常可觀。

今天該怎麼寫

ES6 已內建 Map,直接用就好,而且功能比這個自製版完整得多:

const m = new Map();
m.set('a', 1);            // 鍵可以是任意型別,包含物件與函數
m.set({}, 'object key');  // 這是用物件模擬時做不到的
m.has('a');               // true
m.get('a');               // 1
m.delete('a');
m.size;
m.clear();

// 可直接迭代,順序即插入順序
for (const [key, value] of m) { console.log(key, value); }
m.forEach((value, key) => console.log(key, value));

那麼自己實作還有什麼意義?三點:一、理解底层資料結構的封裝方式;二、需要客製行為時(例如 LRU 淘汰、鍵的重複覆寫策略)仍得自己寫;三、面試常考。

另外提醒,若要「鍵為物件」的字典行為,ES6 另有 WeakMap:它不會阻止鍵物件被垃圾回收,適合拿來快取 DOM 節點或私有資料,避免記憶體洩漏。

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