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