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

• 用裸对象来存储；

• 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) {        //霍纳算法,质数取37
   var hashValue = 6011;
   for (var i = 0; i < key.length; i++) {
     hashValue = hashValue * 37 + key.charCodeAt(i);
   }
   return hashValue ％ 1019;
 }
module.exports = Hashtable;
})();