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

前端之家收集整理的这篇文章主要介绍了JavaScript中实现键值对应的字典与哈希表结构的示例前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

字典(Dictionary)的javascript实现

编程思路:

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

代码

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.jb51.cc/article/86394.htm);
  • 用裸对象来存储;
  • ValuePair简单封装键值对;
  • 以模块模式组织代码

代码

valuePair.js

function ValuePair(key,value){
this.key = key;
this.value = value;
}

ValuePair.prototype.toString = function(){
return "[" + this.key + ":" + this.value + "]";
};

module.exports = ValuePair;

})();

hashtable.js

"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若已经存在,<a href="https://www.jb51.cc/tag/xiugai/" target="_blank" class="keywords">修改</a>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;

})();

原文链接:https://www.f2er.com/js/47946.html

猜你在找的JavaScript相关文章