JavaScript中实现键值对应的字典与哈希表结构的示例

字典（Dictionary）的javascript实现
编程思路：

使用了裸对象datastore来进行元素存储；
实现了两种得到字典长度的方法，一种为变量跟踪，一种为实时计算。

代码：

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;}）（）;

散列（hashtable）的javascript实现
编程思路：

以链表来解决实现开链法来解决碰撞，并使用自己写的单链表库LinkedList（详见jb51之前的http://www.jb51.net/article/86394.htm）；
用裸对象来存储；
ValuePair简单封装键值对；
以模块模式组织代码；

代码：
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） {//霍纳算法,质数取37var hashValue = 6011;for （var i = 0; i < key.length; i++） {hashValue = hashValue * 37 + key.charCodeAt（i）;}return hashValue % 1019;}module.exports = Hashtable;}）（）;