Javascript 中的 HashTable 类
web developmentfront end technologyjavascript
以下是 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) {
// 检查两个参数是否都是 HashTable
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;
}
};
