JavaScript 早期沒有原生的 Map,實作方式通常是用陣列存放 {key, value} 的 entry,再用迴圈比對 key 找到索引。這樣做的好處是可以保留插入順序,也不受「key 只能是字串」的限制。
var Map = function(){
this._entrys = new Array();
this.put = function(key, value){
if (key == null || key == undefined) {
return;
}
var index = this._getIndex(key);
if (index == -1) {
var entry = new Object();
entry.key = key;
entry.value = value;
this._entrys[this._entrys.length] = entry;
}else{
this._entrys[index].value = value;
}
};
this.get = function(key){
var index = this._getIndex(key);
return (index != -1) ? this._entrys[index].value : null;
};
this.remove = function(key){
var index = this._getIndex(key);
if (index != -1) {
this._entrys.splice(index, 1);
}
};
this.clear = function(){
this._entrys.length = 0;
};
this.contains = function(key){
var index = this._getIndex(key);
return (index != -1) ? true : false;
};
this.getCount = function(){
return this._entrys.length;
};
this.getEntrys = function(){
return this._entrys;
};
this._getIndex = function(key){
if (key == null || key == undefined) {
return -1;
}
var _length = this._entrys.length;
for (var i = 0; i < _length; i++) {
var entry = this._entrys[i];
if (entry == null || entry == undefined) {
continue;
}
if (entry.key === key) {
return i;
}
}
return -1;
};
this._toString = function(){
var string = "";
for (var i = 0; i < this.getEntrys().length; i++) {
string += this.getEntrys()[i].key + "::" + this.getEntrys()[i].value;
if(i != this.getEntrys().length - 1){
string += ";";
}
}
return string;
};
};
_getIndex 定位,put 遇到已存在的 key 就覆寫 value,確保 key 不重複。entry.key === key 使用全等,因此 1 與 "1" 視為不同 key。put 與 _getIndex 都先擋掉 null/undefined。_entrys、_getIndex、_toString 表示內部成員,不建議外部直接呼叫。getEntrys() 回傳內部陣列參考,能保留插入順序做迭代。ES6 的 Map 以雜湊為基礎,查詢是 O(1);這份實作每次都要線性掃描,複雜度為 O(n),資料量大時效能差很多。此外原生 Map 的 size 是唯讀屬性、支援 forEach 與各種迭代器、key 可以是任何型別。新專案請優先使用原生 Map;這份程式適合用來理解「鍵值對集合」的內部結構。