一、Dictionary(字典)的 JavaScript 實作
設計思路:
Object.create(null))作為底層儲存結構; (function(){ "use strict"; function Dictionary(){ this._size = 0; this.datastore = Object.create(null); } Dictionary.prototype.isEmpty = function(){ return this._size === 0; }; Dictionary.prototype.size = function(){ return this._size; }; Dictionary.prototype.clear = function(){ for(var key in this.datastore){ delete this.datastore[key]; } this._size = 0; }; Dictionary.prototype.add = function(key, value){ this.datastore[key] = value; this._size++; }; Dictionary.prototype.find = function(key){ return this.datastore[key]; }; Dictionary.prototype.count = function(){ var n = 0; for(var key in this.datastore){ n++; } return n; }; Dictionary.prototype.remove = function(key){ delete this.datastore[key]; this._size--; }; Dictionary.prototype.showAll = function(){ for(var key in this.datastore){ console.log(key + "->" + this.datastore[key]); } }; module.exports = Dictionary; })();
選用裸物件而非 {} 的原因是它能避開原型鏈上的屬性(如 constructor、toString)帶來的誤判風險,這是自己實作字典時最容易忽略的一點。
二、Hashtable(雜湊表)的 JavaScript 實作
設計思路:
valuePair.js
(function(){ "use strict"; function ValuePair(key, value){ this.key = key; this.value = value; } ValuePair.prototype.toString = function(){ return "[" + this.key + ":" + this.value + "]"; }; module.exports = ValuePair; })();
hashtable.js
(function(){ "use strict"; var ValuePair = require("./lib/ValuePair"); var LinkedList = require("./LinkedList"); function Hashtable(){ this.table = Object.create(null); this._size = 0; } Hashtable.prototype.isEmpty = function(){ return this._size === 0; }; Hashtable.prototype.size = function(){ return this._size; }; Hashtable.prototype.remove = function(key){ var index = hashCode(key); if(this.table[index] == null){ return false; }else{ var currNode = this.table[index].getHead(); while(currNode.next){ currNode = currNode.next; if(currNode.element.key == key){ this.table[index].remove(currNode.element); this._size--; return true; } } return false; } }; Hashtable.prototype.get = function(key){ var index = hashCode(key); if(this.table[index] == null){ return null; }else{ var currNode = this.table[index].getHead(); while(currNode.next){ currNode = currNode.next; if(currNode.element.key == key){ return currNode.element; } } return null; } }; Hashtable.prototype.put = function(key, value){ var index = hashCode(key); if(this.table[index] == null){ this.table[index] = new LinkedList(); } var currNode = this.table[index].getHead(); while(currNode.next){ //key 已存在則更新 value currNode = currNode.next; if(currNode.element.key == key){ currNode.element.value = value; break; } } if(currNode.next == null && currNode.element.value != value){ //key 不存在則新增,注意邊界 this.table[index].add(new ValuePair(key,value)); this._size++; } return this; }; Hashtable.prototype.display = function(){ for(var key in this.table){ var currNode = this.table[key].getHead(); while(currNode.next){ currNode = currNode.next; console.log(currNode.element.toString()); } } }; /*********************** Utility Functions ********************************/ function hashCode(key) { //霍納算法,質數取 37 var hashValue = 6011; for (var i = 0; i < key.length; i++) { hashValue = hashValue * 37 + key.charCodeAt(i); } return hashValue % 1019; } module.exports = Hashtable; })();
幾個實作重點:
雜湊函式採用霍納(Horner)法,乘數取質數 37、再對 1019 取模,能讓鍵的分布相對均勻;put 時先在同一桶的鏈中尋找既有鍵,找到就更新值、找不到才新增節點,這是鍵唯一性的保證;桶陣列用 Object.create(null) 建立,避免與 Object 原型屬性混淆。若你要拿這份程式碼上 production,建議再補上「裝載因子達標即擴容」的邏輯,並把鏈串列清河的邊界條件(頭節點哨兵)測一遍。