JavaScript 沒有像 Java 那樣原生的 Map 結構(ES6 之前)。本文分享一個用 Array 加 Object 組合實現 Map 的思路,並在原版基礎上完善了 remove、indexOf、values、clear 等方法,使其功能更完整。
實現原理:用一個數組 this.keys 記錄所有鍵(保持插入順序),用一個對象 this.data 存放鍵值對,通過鍵直接定位值。由於對象存儲,put/get 達到接近 O(1) 的效率。
function Map(){ this.keys = new Array(); this.data = new Object(); var toString = Object.prototype.toString; this.size = function(){ return this.keys.length; } this.put = function(key, value){ if(this.data[key] == null){ this.data[key] = value; } this.keys.push(key); } this.get = function(key){ return this.data[key]; } this.remove = function(key){ var index = this.indexOf(key); if(index != -1){ this.keys.splice(index, 1); } this.data[key] = null; } this.clear = function(){ for(var i=0, len = this.size(); i < len; i++){ var key = this.keys[i]; this.data[key] = null; } this.keys.length = 0; } this.containsKey = function(key){ return this.data[key] != null; } this.isEmpty = function(){ return this.keys.length === 0; } this.entrySet = function(){ var size = this.size(); var datas = new Array(size); for (var i = 0, len = size; i < len; i++) { var key = this.keys[i]; datas[i] = { 'key' : key, 'value':this.data[key] }; } return datas; } this.each = function(fn){ if(toString.call(fn) === '[object Function]'){ for (var i = 0, len = this.size(); i < len; i++) { var key = this.keys[i]; fn(i, key, this.data[key]); } } return null; } this.indexOf = function(key){ var size = this.size(); if(size > 0){ for(var i=0, len=size; i < len; i++){ if(this.keys[i] == key) return i; } } return -1; } this.toString = function(){ var str = "{"; for (var i = 0, len = this.size(); i < len; i++, str+=",") { var key = this.keys[i]; str += key + "=" + this.data[key]; } str = str.substring(0, str.length-1); str += "}"; return str; } this.values = function(){ var size = this.size(); var values = new Array(); for(var i = 0; i < size; i++){ values.push(this.data[this.keys[i]]); } return values; } }
這個 Map 提供了 put、get、remove、clear、containsKey、isEmpty、entrySet、each、indexOf、values、toString 等一系列方法,基本覆蓋了日常所需。其中 each 用 Object.prototype.toString 判斷回調是否為函數,entrySet 模擬 Java 的 entrySet 返回鍵值對數組。若環境支持 ES6,直接用原生 Map 會更高效,但理解這種手工實現有助於掌握底層數據結構的封裝思想。