使用 javascript 的哈希 Table 实现

Question

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

另外，我想提一下，我已经使我的散列 table 变大了，并且在给定特定键的情况下我得到了正确的值，这仅仅是因为我没有冲突。提前谢谢你。

// 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

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

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>

一些说明：

散列函数是有意作为散列的配置提供的table；使 class 更可重用；
使用 this._count 是实施容量限制的更好方法（未实施，但易于添加）；
单元测试可以再扩展一点。不过，我们这里所拥有的足以表明 HashTable class 是可操作的；
^ 运算符（按位异或）通常可以更好地分布生成的哈希码。参见 Why are XOR often used in java hashCode() but another bitwise operators are used rarely?。

Answer 2

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

  _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) {
    let address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }

  get(key){
    const address = this._hash(key);
    const currentBucket = this.data[address]
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++){
        if(currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    }
    return undefined;
  }
  
  keys(){
    const keysArray = [];
    console.log(this.data.length);
    for (let i = 0; i < this.data.length; i++){
      if(this.data[i]){
        keysArray.push(this.data[i][0][0])
      }
    }
    return keysArray;
  }
}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')
myHashTable.keys()

使用 javascript 的哈希 Table 实现

Hash Table implementation using javascript

javascript

hash

hashtable

data-structures