專案裡常需要「鍵值對 + 可走訪 + 可查尺寸」的資料結構。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) 的代價。
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。手寫版本的價值在於理解「雜湊表 + 索引對應表」這個基本設計思路。