ES6 前 JavaScript 僅有物件 {} 當作鍵值對,鍵限於字串、無序、難以取得長度、原型鏈干擾。ES6 原生 Map 已解決這些問題,但理解手動實作有助於掌握資料結構原理,並在不支援 ES6 的舊環境(如 IE11 無 Polyfill)下使用。
/**
* 簡易 Map 實作(ES5 相容)
* 鍵值支援任意型別、保持插入順序、O(1) 存取
*/
function Map() {
this.elements = []; // 內部陣列儲存 {key, value}
// 取得元素數量
this.size = function() {
return this.elements.length;
};
// 判斷是否為空
this.isEmpty = function() {
return this.elements.length === 0;
};
// 清空所有元素
this.clear = function() {
this.elements = [];
};
// 新增/更新鍵值對
this.put = function(key, value) {
// 先移除同鍵舊值(保持鍵唯一)
this.removeByKey(key);
this.elements.push({ key: key, value: value });
};
// 依鍵移除
this.removeByKey = function(key) {
for (var i = 0; i < this.elements.length; i++) {
if (this.elements[i].key === key) {
this.elements.splice(i, 1);
return true;
}
}
return false;
};
// 依值移除(首個符合)
this.removeByValue = function(value) {
for (var i = 0; i < this.elements.length; i++) {
if (this.elements[i].value === value) {
this.elements.splice(i, 1);
return true;
}
}
return false;
};
// 依鍵取值
this.get = function(key) {
for (var i = 0; i < this.elements.length; i++) {
if (this.elements[i].key === key) {
return this.elements[i].value;
}
}
return null;
};
// 依索引取元素
this.element = function(index) {
if (index < 0 || index >= this.elements.length) return null;
return this.elements[index];
};
// 檢查鍵是否存在
this.containsKey = function(key) {
return this.elements.some(function(el) { return el.key === key; });
};
// 檢查值是否存在
this.containsValue = function(value) {
return this.elements.some(function(el) { return el.value === value; });
};
// 取得所有值陣列
this.values = function() {
return this.elements.map(function(el) { return el.value; });
};
// 取得所有鍵陣列
this.keys = function() {
return this.elements.map(function(el) { return el.key; });
};
// 依值反向查鍵(可能多個)
this.keysByValue = function(value) {
return this.elements
.filter(function(el) { return el.value === value; })
.map(function(el) { return el.key; });
};
// 取得去重鍵陣列
this.keysRemoveDuplicate = function() {
var seen = {};
return this.elements
.filter(function(el) {
if (seen[el.key]) return false;
seen[el.key] = true;
return true;
})
.map(function(el) { return el.key; });
};
}
var map = new Map();
map.put("name", "Alice");
map.put("age", 25);
map.put("city", "Taipei");
map.put("age", 26); // 更新既有鍵
console.log(map.size()); // 3
console.log(map.get("name")); // "Alice"
console.log(map.containsKey("age")); // true
console.log(map.keys()); // ["name", "age", "city"]
console.log(map.values()); // ["Alice", 26, "Taipei"]
map.removeByKey("city");
console.log(map.size()); // 2
// 遍歷
for (var i = 0; i < map.size(); i++) {
var el = map.element(i);
console.log(el.key + " = " + el.value);
}
| 操作 | 當前實作 | 優化方向 |
|---|---|---|
| put/get/containsKey | O(n) 線性搜尋 | 改用雜湊表(Object/ES6 Map)達 O(1) |
| removeByKey | O(n) 搜尋 + O(n) splice | 雜湊表直接 delete |
| keys/values | O(n) map | 維護獨立鍵/值陣列同步更新 |
// 現代專案直接使用原生 Map
const map = new Map();
map.set('key', 'value');
map.get('key');
map.has('key');
map.delete('key');
map.size;
map.clear();
// 迭代
for (let [key, value] of map) { ... }
map.forEach((value, key) => { ... });
// 鍵可為物件、函式、NaN 等任意型別
const objKey = {};
map.set(objKey, 'object as key');