ES6 內建 Map 物件提供鍵值對集合,鍵可為任意型別。本文示範如何**從零手寫一個 Map 類別**,涵蓋增刪改查、迭代、擴充方法,深入理解雜湊表與鏈結清單結合的實作原理。
hashmap:物件雜湊表,key -> value 快速查找 O(1)。keys[]、vals[]、entrys[]:維持插入順序的陣列,支援疊代。index:記錄 key -> 陣列索引,實現 O(1) 刪除/更新。size:當前元素數量。var Map = function() {
// 私有儲存
var hashmap = {}, keys = [], vals = [], entrys = [], size = 0, index = {};
// 內部 Entry 類別
var Entry = function(key, value) {
this.getKey = function() { return key; };
this.getValue = function() { return value; };
};
// 基礎方法
this.put = function(key, value) {
if (!this.get(key)) { // 新增
var entry = new Entry(key, value);
entrys.push(entry);
keys.push(key);
vals.push(value);
index[key] = size++;
} else { // 更新
var i = index[key];
entrys[i] = new Entry(key, value);
vals[i] = value;
}
hashmap[key] = value;
};
this.get = function(key) { return hashmap[key]; };
this.remove = function(key) {
if (!this.get(key)) return undefined;
var i = index[key];
var val = vals[i];
// 陣列移除 (O(n) 但 size 通常較小)
entrys.splice(i, 1);
vals.splice(i, 1);
keys.splice(i, 1);
// 更新後續索引
for (var k = i; k < keys.length; k++) index[keys[k]] = k;
delete hashmap[key];
size--;
return val;
};
this.clear = function() {
hashmap = {}; keys = []; vals = []; entrys = []; index = {}; size = 0;
};
this.size = function() { return size; };
this.isEmpty = function() { return size === 0; };
this.keySet = function() { return keys.slice(); };
this.values = function() { return vals.slice(); };
this.entrySet = function() { return entrys.slice(); };
this.containsKey = function(key) { return key in hashmap; };
};
// 原型擴充 (可選)
Map.prototype.putAll = function(map) {
map.entrySet().forEach(function(e) { this.put(e.getKey(), e.getValue()); }, this);
};
var m = new Map();
m.put('a', 10);
m.put('b', 20);
m.put('c', 30);
console.log(m.size()); // 3
console.log(m.get('b')); // 20
console.log(m.containsKey('a')); // true
m.remove('b');
console.log(m.size()); // 2
console.log(m.keySet()); // ["a", "c"]
console.log(m.values()); // [10, 30]
// 疊代
m.entrySet().forEach(function(e) {
console.log(e.getKey() + ':' + e.getValue());
});
class MyMap {
constructor() {
this._map = {};
this._keys = [];
this._vals = [];
this._index = {};
this._size = 0;
}
put(key, value) {
if (!(key in this._map)) {
this._keys.push(key);
this._index[key] = this._size++;
}
this._map[key] = value;
this._vals[this._index[key]] = value;
}
get(key) { return this._map[key]; }
has(key) { return key in this._map; }
delete(key) {
if (!this.has(key)) return false;
const i = this._index[key];
this._keys.splice(i, 1);
this._vals.splice(i, 1);
delete this._map[key];
// 重建索引
this._keys.forEach((k, idx) => this._index[k] = idx);
this._size--;
return true;
}
get size() { return this._size; }
keys() { return [...this._keys]; }
values() { return [...this._vals]; }
entries() { return this._keys.map(k => [k, this._map[k]]); }
clear() { this._map={}; this._keys=[]; this._vals=[]; this._index={}; this._size=0; }
*[Symbol.iterator]() { for (const k of this._keys) yield [k, this._map[k]]; }
}
| 特性 | 手寫 Map | 內建 Map |
|---|---|---|
| 鍵型別 | 字串化 (物件鍵會 toString) | 任意型別 (物件參考) |
| 順序保證 | 插入順序 | 插入順序 |
| 效能 | O(1) 平均,但刪除 O(n) 因陣列搬移 | 高度優化 O(1) |
| 可疊代 | 手動實作 | 內建 for...of, forEach |
| 序列化 | 需自行實作 | 需自行實作 |
手寫 Map 能深入理解「雜湊表 + 陣列維持順序」的經典設計模式。實務專案**請直接使用內建 Map**,它支援物件鍵、效能更強、API 完整。本文實作適合教學、面試準備或特殊環境 (如極舊瀏覽器無 Polyfill 空間) 參考。