Javascript中的HashTable类
这是HashTable类的完整实现。当然，这可以通过使用更有效的数据结构和冲突解决算法来改善。
示例
class HashTable {
constructor() {
this.container = [];
//用空数组填充容器
//添加更多元素
//发生碰撞的情况
for (let i = 0; i < 11; i++) {
this.container.push([]);
}
}
display() {
this.container.forEach((value, index) => {
let chain = value
.map(({ key, value }) => `{ ${key}: ${value} }`)
.join(" --> ");
console.log(`${index}: ${chain}`);
});
}
put(key, value) {
let hashCode = this.hash(key);
for (let i = 0; i < this.container[hashCode].length; i++) {
//用给定的键替换现有值
//如果已经存在
if (this.container[hashCode][i].key === key) {
this.container[hashCode][i].value = value;
return;
}
}
//将线对推到阵列的末端
this.container[hashCode].push(new this.KVPair(key, value));
}
get(key) {
let hashCode = this.hash(key);
for (let i = 0; i < this.container[hashCode].length; i++) {
//在链中找到元素
if (this.container[hashCode][i].key === key) {
return this.container[hashCode][i];
}
}
return undefined;
}
remove(key) {
let hashCode = this.hash(key);
for (let i = 0; i < this.container[hashCode].length; i++) {
//在链中找到元素
if (this.container[hashCode][i].key === key) {
this.container[hashCode].splice(i, 1);
return true;
}
}
return false;
}
hash(key) {
return key % 11;
}
forEach(callback) {
//对于每个链
this.container.forEach(elem => {
//对于KV对上每个链调用回调中的每个元素
elem.forEach(({ key, value }) => callback(key, value));
});
}
static join(table1, table2) {
//检查两个参数是否都是HashTables-
if (!table1 instanceof HashTable || !table2 instanceof HashTable) {
throw new Error("Illegal Arguments");
}
let combo = new HashTable();
table1.forEach((k, v) => combo.put(k, v));
table2.forEach((k, v) => combo.put(k, v));
return combo;
}
}
HashTable.prototype.KVPair = class {
constructor(key, value) {
this.key = key;
this.value = value;
}
};