本文详细展示了如何在 JavaScript 中从零实现字典和哈希表数据结构。通过裸对象存储元素，分别介绍了基于变量跟踪和实时计算的长度获取方式。哈希表部分重点演示了利用链表解决哈希碰撞的开链法，并结合模块模式封装了键值对与哈希表类，提供了完整的代码实现参考。
JavaScript 字典结构实现
本节介绍如何在 JavaScript 中构建字典（Dictionary）数据结构，并梳理其核心编程思路。
- 底层存储直接采用裸对象（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;
})();
JavaScript 哈希表与碰撞处理
接着介绍 JavaScript 中哈希表（Hashtable）的实现方案，并阐述其设计思路。
- 为解决哈希碰撞问题，采用开链法（Separate Chaining），即通过链表来处理冲突元素。代码中调用了自定义的单链表库 LinkedList（参考 jb51 之前的 https://www.jb51.net/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;
})();