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) 操作,刪除频繁時性能不佳。這些正是原生 Map 要解決的問題:它支持任意類型作鍵、用 SameValueZero 演算法判斷鍵相等、並保證遍歷順序為插入順序。今天的項目裡直接用 new Map() 就好,手寫一遍的價值主要在於理解底層取捨。