HashMap 是應用面極廣的資料結構,核心是「鍵 → 值」的一對一映射。JavaScript 沒有內建的 Map 之前(ES6 以前),大家通常用普通物件來模擬。以下是一個功能相當完整的實作,把常見操作都包好了。
/**
* hashmap:以物件模擬 Map
*
* 介面:
* size() 取得元素個數
* isEmpty() 是否為空
* clear() 清空
* put(key, value) 放入一組鍵值
* remove(key) 刪除指定鍵
* get(key) 取值,不存在回傳 null
* containsKey(key) 是否含指定鍵
* containsValue(value) 是否含指定值
* keys() / values() 取得全部鍵 / 值
* entrys() 取得 {key, value} 陣列
*/
function hashmap() {
this.data = new Object();
/** 放入一組鍵值 */
this.put = function(key, value) {
this.data[key] = value;
};
/** 取值 */
this.get = function(key) {
return this.containsKey(key) ? this.data[key] : null;
};
/** 刪除 */
this.remove = function(key) {
delete this.data[key];
};
/** 遍歷,執行 callback(key, value, index) */
this.each = function(fn){
if (typeof fn != 'function') return;
for (var key in this.data) {
if (this.data.hasOwnProperty(key)) fn(key, this.data[key]);
}
};
/** 取得鍵值對陣列,類似 Java 的 entrySet() */
this.entrys = function() {
var entrys = [];
for (var key in this.data) {
if (this.data.hasOwnProperty(key)) {
entrys.push({ key: key, value: this.data[key] });
}
}
return entrys;
};
this.isEmpty = function() {
return this.size() === 0;
};
this.size = function() {
return this.keySet().length;
};
/** 轉成 JSON 字串 */
this.toString = function() {
var s = "[";
var keys = this.keySet();
for (var i = 0; i < keys.length; i++) {
s += "{'key':'" + keys[i] + "','value':'" + this.data[keys[i]] + "'},";
}
if (s != "[") { s = s.substring(0, s.length - 1); }
return s + "]";
};
/** 全部的值 */
this.values = function(){
var _values = [];
for (var key in this.data) {
if (this.data.hasOwnProperty(key)) _values.push(this.data[key]);
}
return _values;
};
/** 全部的鍵 */
this.keySet = function(){
var _keys = [];
for (var key in this.data) {
if (this.data.hasOwnProperty(key)) _keys.push(key);
}
return _keys;
};
/** 是否含指定鍵 */
this.containsKey = function(_key) {
return (_key in this.data);
};
/** 清空 */
this.clear = function(){
this.data = new Object();
};
}
網路上流傳的版本常用 this.data.length 來算元素數量,但 data 是物件而非陣列,length 永遠是 undefined,所以 size() 與 isEmpty() 都會失效。上面已改為透過 keySet().length 計算。另外 each() 用索引取值在物件上也不成立,已改成 for...in 並加上 hasOwnProperty 過濾原型鏈上的屬性。
ES6 之後 JavaScript 已有真正的 Map,鍵可以是任意型別(物件、函式都可以當鍵),也有 size 屬性與 forEach,並不會有原型鏈汙染的問題:
const m = new Map();
m.set('name', 'tom');
m.set({ id: 1 }, 'object key works too');
console.log(m.size); // 2
console.log(m.get('name')); // tom
console.log(m.has('name')); // true
m.delete('name');
console.log([...m.keys()]);
除非需要支援非常舊的環境,否則新專案請直接用 Map 與 Set,它們在效能與語意上都優於自行實作。