ES6 之前,JavaScript 沒有原生的 Map 資料結構,工程師只能用物件或陣列硬湊鍵值對。若想理解 Map 的底層思維,自己動手實作一次是最快的方式。以下示範如何用陣列包裝出一個具備 put、get、remove、size、isEmpty 的 Map。
核心很單純:用一個陣列保存多個 { key, value } 結構。新增時先搜尋是否已有相同 key,有的話就覆寫值;沒有的話就附加到尾端。查詢則是線性掃描,找到就回傳對應值,找不到回傳 null。
/**
* 描述:以陣列模擬 Map 的鍵值對結構
* @returns {Map}
*/
function Map(){
var struct = function(key, value) {
this.key = key;
this.value = value;
};
// 新增鍵值對:key 已存在則更新,否則附加
var put = function(key, value){
for (var i = 0; i < this.arr.length; i++) {
if ( this.arr[i].key === key ) {
this.arr[i].value = value;
return;
}
};
this.arr[this.arr.length] = new struct(key, value);
};
// 依 key 取值,找不到回傳 null
var get = function(key) {
for (var i = 0; i < this.arr.length; i++) {
if ( this.arr[i].key === key ) {
return this.arr[i].value;
}
}
return null;
};
// 依 key 刪除
var remove = function(key) {
var v;
for (var i = 0; i < this.arr.length; i++) {
v = this.arr.pop();
if ( v.key === key ) {
continue;
}
this.arr.unshift(v);
}
};
// 取得鍵值對數量
var size = function() {
return this.arr.length;
};
// 判斷是否為空
var isEmpty = function() {
return this.arr.length <= 0;
};
this.arr = new Array();
this.get = get;
this.put = put;
this.remove = remove;
this.size = size;
this.isEmpty = isEmpty;
}
呼叫習慣刻意對齊 Java 的 Map,遷移過來幾乎零成本:
<script type="text/javascript">
var map = new Map();
map.put("num", 1);
map.put("ss", "wss");
alert(map.size()); // 2
alert(map.get("num")); // 1
map.remove("num");
alert(map.size()); // 1
alert(map.get("num")); // null
</script>
這個版本以教學為目的,時間複雜度是 O(n):查詢與刪除都要線性掃過整個陣列,資料量大時效能會是瓶頸。另外 remove 用 pop/unshift 反覆搬移元素,寫法雖然直觀,但每次 unshift 都會造成陣列重新索引。
若要在正式專案中使用,建議直接採用 ES6 的 Map;若必須相容舊環境,則可考慮改用「平行陣列 + 雜湊表」的雙結構,把查詢降到接近 O(1)。理解這個原型之後,你會更明白原生 Map 為什麼那樣設計。