快捷導(dǎo)航

JavaScript中實(shí)現(xiàn)鍵值對(duì)應(yīng)的字典與哈希表結(jié)構(gòu)的示例

更新時(shí)間：2016年06月12日 17:03:16 作者：zhoutk

字典或者哈希表這樣的鍵值對(duì)應(yīng)結(jié)構(gòu)在其他很多語言中都有內(nèi)置,非常好用,這里我們來看一下JavaScript中實(shí)現(xiàn)鍵值對(duì)應(yīng)的字典與哈希表結(jié)構(gòu)的示例:

字典（Dictionary）的javascript實(shí)現(xiàn)
編程思路：

使用了裸對(duì)象datastore來進(jìn)行元素存儲(chǔ)；
實(shí)現(xiàn)了兩種得到字典長(zhǎng)度的方法，一種為變量跟蹤，一種為實(shí)時(shí)計(jì)算。

代碼：

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實(shí)現(xiàn)
編程思路：

以鏈表來解決實(shí)現(xiàn)開鏈法來解決碰撞，并使用自己寫的單鏈表庫(kù)LinkedList（詳見jb51之前的http://www.fzitv.net/article/86394.htm)；
用裸對(duì)象來存儲(chǔ)；
ValuePair簡(jiǎn)單封裝鍵值對(duì)；
以模塊模式組織代碼；

代碼：

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若已經(jīng)存在,修改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) {        //霍納算法,質(zhì)數(shù)取37
    var hashValue = 6011;
    for (var i = 0; i < key.length; i++) {
      hashValue = hashValue * 37 + key.charCodeAt(i);
    }
    return hashValue % 1019;
  }

  module.exports = Hashtable;

})();

您可能感興趣的文章: