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; })();