JavaScript中实现键值对应的字典与哈希表结构的示例
字典（Dictionary）的javascript实现
编程思路：
- 使用了裸对象datastore来进行元素存储；
- 实现了两种得到字典长度的方法，一种为变量跟踪，一种为实时计算。
代码：
function(){
"usestrict";
functionDictionary(){
this._size=0;
this.datastore=Object.create(null);
}
Dictionary.prototype.isEmpty=function(){
returnthis._size===0;
};
Dictionary.prototype.size=function(){
returnthis._size;
};
Dictionary.prototype.clear=function(){
for(varkeyinthis.datastore){
deletethis.datastore[key];
}
this._size=0;
};
Dictionary.prototype.add=function(key,value){
this.datastore[key]=value;
this._size++;
};
Dictionary.prototype.find=function(key){
returnthis.datastore[key];
};
Dictionary.prototype.count=function(){
varn=0;
for(varkeyinthis.datastore){
n++;
}
returnn;
};
Dictionary.prototype.remove=function(key){
deletethis.datastore[key];
this._size--;
};
Dictionary.prototype.showAll=function(){
for(varkeyinthis.datastore){
console.log(key+"->"+this.datastore[key]);
}
};
module.exports=Dictionary;
})();
散列（hashtable）的javascript实现
编程思路：
- 以链表来解决实现开链法来解决碰撞，并使用自己写的单链表库LinkedList（详见jb51之前的https://www.nhooo.com/article/86394.htm)；
- 用裸对象来存储；
- ValuePair简单封装键值对；
- 以模块模式组织代码；
代码：
valuePair.js
(function(){
"usestrict";
functionValuePair(key,value){
this.key=key;
this.value=value;
}
ValuePair.prototype.toString=function(){
return"["+this.key+":"+this.value+"]";
};
module.exports=ValuePair;
})();
hashtable.js
(function(){
"usestrict";
varValuePair=require("./lib/ValuePair");
varLinkedList=require("./LinkedList");
functionHashtable(){
this.table=Object.create(null);
this._size=0;
}
Hashtable.prototype.isEmpty=function(){
returnthis._size===0;
};
Hashtable.prototype.size=function(){
returnthis._size;
};
Hashtable.prototype.remove=function(key){
varindex=hashCode(key);
if(this.table[index]==null){
returnfalse;
}else{
varcurrNode=this.table[index].getHead();
while(currNode.next){
currNode=currNode.next;
if(currNode.element.key==key){
this.table[index].remove(currNode.element);
this._size--;
returntrue;
}
}
returnfalse;
}
};
Hashtable.prototype.get=function(key){
varindex=hashCode(key);
if(this.table[index]==null){
returnnull;
}else{
varcurrNode=this.table[index].getHead();
while(currNode.next){
currNode=currNode.next;
if(currNode.element.key==key){
returncurrNode.element;
}
}
returnnull;
}
};
Hashtable.prototype.put=function(key,value){
varindex=hashCode(key);
if(this.table[index]==null){
this.table[index]=newLinkedList();
}
varcurrNode=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(newValuePair(key,value));
this._size++;
}
returnthis;
};
Hashtable.prototype.display=function(){
for(varkeyinthis.table){
varcurrNode=this.table[key].getHead();
while(currNode.next){
currNode=currNode.next;
console.log(currNode.element.toString());
}
}
};
/***********************UtilityFunctions********************************/
functionhashCode(key){//霍纳算法,质数取37
varhashValue=6011;
for(vari=0;i<key.length;i++){
hashValue=hashValue*37+key.charCodeAt(i);
}
returnhashValue%1019;
}
module.exports=Hashtable;
})();