javascript - 使用javascript实现哈希表

Question

我正在尝试使用 javascript 实现哈希表。目前，到目前为止一切正常，但我的 get 方法在给定特定键的情况下检索哈希表中的值时遇到问题。我使用线性探测以避免碰撞。当我散列键“Alejandro”时，我将键映射到 0 索引。然后我将它添加到我的哈希表中。然后我尝试“Rosalby”，它也映射到 0 索引。我使用线性探测来查找下一个可用槽，在我的例子中，空索引为 1，我将 Rosalby 的值放入该槽中。到目前为止，我似乎很好地处理了碰撞。然而;当我尝试在 get 方法中获取值时，我无法获取正确的值，这就是我的哈希表的样子。

另外，我想提一下，我已经使哈希表的大小变得更大，并且在给定特定键的情况下我得到了正确的值，仅仅是因为我没有发生冲突。预先感谢您。

// Hash table implementation
class HashTable {
  // constructor functio
  constructor(size) {
    this.size = size;
    this.buckets = this.initArray(size);
    this.limit = 0;
  }

  // init array function
  initArray(size) {
    // init an array
    const array = [];

    // populate the array base on the size
    for (let i = 0; i < size; i++) {
      // push null to the array
      array.push(null);
    }
    // return the array
    return array;
  }

  // mapping key to index
  hash(key) {
    let total = 0;

    // get unique code of character in the string
    for (let i = 0; i < key.length; i++) {
      let keyCode = key.charCodeAt(i)
      //  console.log("Key code:", keyCode)

      // sum up the unique code
      total += keyCode;
      // console.log(total); 
    }
    // mod the total to the size of the hash table
    const hashIndex = total % this.size;
    // return that index
    return hashIndex;
  }

  // put method
  put(key, value) {
    // throw an erro if hashTable is full
    if (this.limit >= this.size) throw "Hash Table is full";

    // hash the key
    let hashIndex = this.hash(key);
    // console.log(hashIndex);

    // linear probing
    while (this.buckets[hashIndex] != null) {
      hashIndex++;

      hashIndex = hashIndex % this.size;
    }

    // add the value at that key to the buckets array
    this.buckets[hashIndex] = value;

    // increase the limit
    this.limit++;
  }

  // get method
  get(key) {
    // hash the key
    let hashIndex = this.hash(key);
    let value = this.buckets[hashIndex];

    // return the value at that index
    return value;
  }
} // end of hash table

// sanity check
const ht = new HashTable(3);
console.log(ht);
// ht.hash("Rosalby");
console.log();
ht.put("Alejandro", "555-5555");
ht.put("Rosalby", "123-1231");
ht.put("Lalaland", "000-0000");
// ht.put("Lalaland", "919-1919");
console.log();
console.log(ht);
console.log("Alejandro:", ht.get("Alejandro"), "Rosalby:", ht.get("Rosalby"), "Lalaland:", ht.get("Lalaland"));

Hash Table console logs

Answer 1

这是哈希表的快速工作实现:

class HashTable
{
    constructor(getHash)
    {
        if(!getHash) throw "Argument is null: getHash";
        
        this.getHash = getHash;
        this.buckets = {};
        this._count = 0;
    }
    
    //  throws an exception if the key already exists
    add(key, value)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket)
        {
            this.buckets[hashCode] = [{key, value}];
            ++this._count;
            return;
        }
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) throw "Duplicate key.";
        }
        bucket.push({key, value});
        ++this._count;
    }
    
    //  replaces the value if the key already exists
    set(key, value)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket)
        {
            this.buckets[hashCode] = [{key, value}];
            ++this._count;
            return;
        }
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) 
            {
                item.value = value;
                return;
            }
        }
        bucket.push({key, value});
        ++this._count;
    }

    get(key, defaultValue)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket) return defaultValue;
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) return item.value;
        }
        return defaultValue;
    }

    has(key)
    {
        const hashCode = this.getHash(key);
        const bucket = this.buckets[hashCode];
        if(!bucket) return false;
        for(let length = bucket.length, i = 0; i < length; ++i)
        {
            const item = bucket[i];
            if(item.key == key) return true;
        }
        return false;
    }
    
    get count()
    {
        return this._count;
    }
}

HashTable.unitTests = function()
{
    function getHash(value)
    {
        const stringValue = String(value);
        let result = 0;
        for(let length = stringValue.length, i = 0; i < length; ++i) result ^= stringValue.charCodeAt(i);
        return result;
    }
    
    let ht;
    
    //  empty
    ht = new HashTable(getHash);
    if (ht.count != 0) throw "failed";
    if (ht.has(null)) throw "failed";
    if (ht.has("")) throw "failed";
    if (ht.get(null) != void (0)) throw "failed";
    if (ht.get("") != void (0)) throw "failed";
    if (ht.get(null, 1) != 1) throw "failed";

    //  add new
    ht = new HashTable(getHash);
    ht.add("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  set new
    ht = new HashTable(getHash);
    ht.set("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  add duplicate
    ht = new HashTable(getHash);
    ht.add("a", 1);
    try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }

    //  add+set duplicate
    ht = new HashTable(getHash);
    ht.add("a", 1);
    ht.set("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  set+add duplicate
    ht = new HashTable(getHash);
    ht.set("a", 1);
    try { ht.add("a", 1); throw "failed"; } catch (ex) { if (ex != "Duplicate key.") throw "failed"; }

    //  set duplicate
    ht = new HashTable(getHash);
    ht.set("a", 1);
    ht.set("a", 1);
    if (ht.count != 1) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (ht.get("a") != 1) throw "failed";

    //  add multiple
    ht = new HashTable(getHash);
    ht.add("a", 1);
    ht.add("b", 2);
    if (ht.count != 2) throw "failed";
    if (!ht.has("a")) throw "failed";
    if (!ht.has("b")) throw "failed";
    if (ht.get("a") != 1) throw "failed";
    if (ht.get("b") != 2) throw "failed";

    //  add with collision
    ht = new HashTable(getHash);
    ht.add("ab", 1);    //  hash code 3
    ht.add("ba", 2);    //  hash code 3
    if (ht.count != 2) throw "failed";
    if (!ht.has("ab")) throw "failed";
    if (!ht.has("ba")) throw "failed";
    if (ht.get("ab") != 1) throw "failed";
    if (ht.get("ba") != 2) throw "failed";

    //  set with collision
    ht = new HashTable(getHash);
    ht.set("ab", 1);    //  hash code 3
    ht.set("ba", 2);    //  hash code 3
    if (ht.count != 2) throw "failed";
    if (!ht.has("ab")) throw "failed";
    if (!ht.has("ba")) throw "failed";
    if (ht.get("ab") != 1) throw "failed";
    if (ht.get("ba") != 2) throw "failed";
}

HashTable.unitTests();
console.log("OK");

<html>
<head>
<script src="HashTable.js"></script>
</head>
<body>
</body>
</html>

一些说明:

• 特意提供哈希函数作为哈希表的配置；使类更具可重用性；
• 使用 this._count 是强制执行容量限制的更好方法(未实现，但易于添加)；
• 单元测试可以进一步扩展。不过，我们这里所拥有的足以表明 HashTable 类是可操作的；
• ^ 运算符(按位异或)通常可以更好地分配生成的哈希码。请参阅Why are XOR often used in java hashCode() but another bitwise operators are used rarely? .