2

I am trying to implement a hash table using javascript. At the moment, everything is working so far, but I am having trouble with my get method to retrieve a value in the hash table given a specific key. I am using linear probing in order to avoid collisions. When I hash the key "Alejandro" I map the key to the 0 index. Then I add it into my hash table. Then I try "Rosalby" which also maps to 0 index. I used linear probing to find the next available slot, in my case the empty index is 1 and I put Rosalby's value in that slot. So far it seems that I am managing my collision well. However; when I try to get the values in my get method, I am unable to get the right values here is what my hash table looks like.

Also, I would like to mention that I have made my hash table bigger in size and I get the right value given specific key, simply because I do not have collision. Thank you in advance.

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

Improve this question

2 Answers 2

Reset to default
1

Here is a quick working implementation of a hash 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>

Some clarifications:

  • The hashing function is intentionally provided as a configuration for the hash table; makes the class more reusable;
  • Using this._count is a better way to enforce capacity limit (not implemented, easy to add, though);
  • The unit tests could be extended a bit more. What we have here is, though, sufficient to show that the HashTable class is operational;
  • The ^ operator (bitwise XOR) usually provides a better distribution of the generated hash codes. See Why are XOR often used in java hashCode() but another bitwise operators are used rarely?.
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thank you so much Daniel, really went above and beyond answering my question. The clarifications helped me understand the parts I did not understand from your solution. Again, thank you so much!
1 

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()

Improve this answer

1 Comment

Nice, thank you. Question what does the underscore character ( _variableName ) in front of the variable means?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.