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;
};
};
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 節點或私有資料,避免記憶體洩漏。