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