javascript - 如何在 JavaScript 中的哈希表上实现这个“计数器”？

Question

我正在用 JavaScript 创建这个哈希表，我希望每次在数组中添加现有值时它都会警告我。我尝试了自己的实现，但它不起作用。

function hashFunction(s,tableSize){
    let hash = 17;

    for(let i = 0; i<s.length; i++){
        hash = (13*hash * s.charCodeAt(i)) % tableSize;
    }

    return hash; 
};

class HashTable {

    table = new Array(2000);
    numItems  = 0;
    loadFactor = this.numItems/this.table.length;

    setItem = (key,value)=>{
        const idx = hashFunction(key, this.table.length);
        if(this.table.includes(key)){
            return "already exists"
        }else this.numItems++
        if(this.table[idx]){
            this.table[idx].push([key,value])
        }else this.table[idx]=[[key,value]];

    };

    getItem = (key)=>{
        const idx = hashFunction(key,this.table.length);
        if(!this.table[idx]){
            return "Key doesn't exist";
        }else
         return this.table[idx].find(x=>x[0]===key)[1];
    };
};

let myHash = new HashTable

myHash.setItem("first","daniel")
myHash.setItem("last","esposito")
myHash.setItem("age","21")
myHash.setItem("height","1,90")

标签： javascriptarrayshashtable

Answer 1

回顾实现伪代码和现有实现将是有益的。有许多错误可以概括为原始实现未能正确处理存储桶中的对。

这是一个工作更新，它挽救了一些结构，同时丢弃了大部分不一致和/或不正确的实现——我留下了评论作为参考点，以了解为什么原来的不正确。代码的结构是为了说明存储桶的访问/创建、存储桶内对的访问/创建以及根据情况选择的行为。

YMMV。

function hashFunction(s, tableSize){
    let hash = 17;

    for (let i = 0; i < s.length; i++){
        hash = (13 * hash + s.charCodeAt(i)) % tableSize;
        //                ^-- Ry suggests the original * is a typo.
    }

    return hash; 
};

class HashTable {

  // I've eliminated 'load factor' to cover a basic implementation.
  // See rebalancing, good table size selection, alternative collision
  // resolution strategies, etc.
  // This implementation might pass a CS101 course.

  // Yes, for THIS EXAMPLE the TABLE SIZE IS CHOSEN AS 2.
  // This ensures that there are multiple items per bucket
  // which guarantees the collision resolution paths are invoked.
  // This is a terrible choice in practice.
  table = new Array(2);
  numItems = 0;

  setItem = (key, value)=>{
    const idx = hashFunction(key, this.table.length);
    // set/get should ONLY access simple properties or
    // a BUCKET from the hash code as top-level structures.
    // (Using table.includes(..) here is fundamentally INCORRECT.)
    let bucket = this.table[idx];
    if (bucket) {
      // Existing bucket. Search in HERE to see if the key exists.
      // This should generally be the same code as the "get".
      let pair = bucket.find(x => x[0] === key);
      if (pair) {
        // Same pair, update value.
        pair[1] = value;
        return false; // "existing"
      } else {
        // Add new pair to bucket.
        bucket.push([key, value]);
        this.numItems += 1;
        return true; // "new"
      }
    } else {
      // Create a new bucket and item pair.
      this.table[idx] = [[key, value]];
      this.numItems += 1;
      return true; // "new"
    }
  };

  getItem = (key) =>{
    const idx = hashFunction(key, this.table.length);
    // Code should match close to 'set'
    let bucket = this.table[idx];
    if (bucket) {
      let pair = bucket.find(x => x[0] === key);
      if (pair) {
        // Bucket exists and key exists within bucket.
        return pair[1];
      }
    }

    // The result should be the same if the key doesn't exist because
    // bucket is not found, or if the bucket is found and the
    // key does not exist within the bucket..
    return undefined;
  };
}

let myHash = new HashTable

var items = [
  ["first", "daniel"],
  ["last", "esposito"],
  ["age", 21],
  ["height", 1.9]
]

// Insert multiple values:
// Check to see inserted report true/not,
// and that the numItems is increased appropriately.
for (let run of [1, 2]) {
  for (let i of items) {
   let [k, v] = i;
   var inserted = myHash.setItem(k, v);
   var found = myHash.getItem(k) === v;
   console.log(`run=${run} key=${k} value=${v} inserted=${inserted} numItems=${myHash.numItems} found=${found}` )
  }
}

输出：

run=1 key=first value=daniel inserted=true numItems=1 found=true
run=1 key=last value=esposito inserted=true numItems=2 found=true
run=1 key=age value=21 inserted=true numItems=3 found=true
run=1 key=height value=1.9 inserted=true numItems=4 found=true
run=2 key=first value=daniel inserted=false numItems=4 found=true
run=2 key=last value=esposito inserted=false numItems=4 found=true
run=2 key=age value=21 inserted=false numItems=4 found=true
run=2 key=height value=1.9 inserted=false numItems=4 found=true