这是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; } };