Javascript 中的自定义 Hashable 实现

Question

我相当愚蠢编程新手。我想在 javascript 中实现一个简单的哈希表（出于教育目的）。一切正常，除了当我尝试覆盖某些值时它保留以前的值。例如，当我尝试 hashTable.set(cherry, 100)，然后 hashTable.set(cherry, 4) 然后 hashTable.get(cherry) 给我 100 而不是 4。我试过它与调试器一起使用，但事实证明，如果您是相当愚蠢的编程新手，调试器将无济于事。代码如下：

    class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }

  set(key, value) {
    const address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    if (Array.isArray(this.data[address])) {
      for (let arr of this.data[address].values()) {
        if (arr[0] === key) {
          const arr1 = arr[1];
          arr[1] === value;
          return;
        }
      }
    }
    this.data[address].push([key, value]);
  }
  get(key) {
    const address = this._hash(key);
    const currentNode = this.data[address];
    if (currentNode) {
      for (let arr of currentNode) {
        if (arr[0] === key) {
          return arr[1];
        }
      }
    }
    return undefined;
  }
}

const myHashTable = new HashTable(2);
myHashTable.set("cherry", 100);
myHashTable.set("cherry", 4);
console.log(myHashTable.get("cherry")); // returns 100 instead of 4
myHashTable.set("peach", 9);
console.log(myHashTable.get("peach"));
myHashTable.set("apple", 2);
console.log(myHashTable.get("apple"));

Answer 1

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }

  set(key, value) {
    const address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }

    for (let el of this.data[address]) {
      if (el[0] === key) {
        el[1] = value;
        return;
      }
    }
    this.data[address].push([key, value]);
  }
  get(key) {
    const address = this._hash(key);
    const currentNode = this.data[address];
    if (currentNode) {
      for (let arr of currentNode) {
        if (arr[0] === key) {
          return arr[1];
        }
      }
    }
    return undefined;
  }
}

const myHashTable = new HashTable(2);
myHashTable.set("cherry", 100);
myHashTable.set("cherry", 4);
console.log(myHashTable.get("cherry")); // returns 100 instead of 4
myHashTable.set("peach", 9);
console.log(myHashTable.get("peach"));
myHashTable.set("apple", 2);
console.log(myHashTable.get("apple"));

您在 set 函数中做了一些奇怪的事情。那就是我改变的。现在，它查看 address 处 this.data 的元素并检查第一个元素以确保密钥不相同。如果是这样，它只是提前更新值和 returns 。我想这就是你的想法。

为了使其成为更好的解决方案，我建议您向底层数组添加一个容量，当密度达到一定百分比时，您增加底层数组以减少哈希冲突。

Javascript 中的自定义 Hashable 实现

Custom Hashable implementation in Javascript

javascript

algorithm

hashtable

data-structures