2
\$\begingroup\$

I recently tried to implement a simple hash table using Javascript. Could anyone help me review my implementation?

//Hash Table Implementation
var HashEntry = function(key, value) {
    this.key = key;
    this.value = value;
    this.nextEntry = undefined;
};
HashEntry.prototype = {
  getKey : function() {
    return this.key;
  },
  getValue : function() {
    return this.value;  
  },
  setNext : function(entry) {
    this.nextEntry = entry;
  },
  getNext : function() {
    return this.nextEntry;
  }

};

var HashTable = function(){
  this.tableSize = 100;
  this.table = []; //this will be holding HashEntry(s)
};

HashTable.prototype = {
  hashFunction: function(input) {
    //return an hash
    return input % this.tableSize;
  },
  put : function(key, value) {
    var hash = this.hashFunction(key);
    var table = this.table;
    if(table[hash] === undefined) {
       table[hash] = new HashEntry(key, value);
    } else {
       var curr = table[hash];
       while(curr.getNext()!==undefined) {
         curr = curr.getNext();
       }
       curr.setNext(new HashEntry(key, value));
    }
  },
  get : function(key) {
     var hash = this.hashFunction(key);
     var table = this.table;
     var currEntry = table[hash];
     if(currEntry === undefined) return null;
     if(currEntry.getKey() === key) {
       return currEntry.getValue();
     } else {
       while(currEntry.getNext()!==undefined) {
         currEntry = currEntry.getNext();
         if(currEntry.getKey() === key) {
           return currEntry.getValue();
         } 
       }
     }
  }
};

var hashTable = new HashTable();
hashTable.put(123, "thomas");
hashTable.put(12, "luis");
hashTable.put(112,"linda");

console.log(hashTable.get(12));
console.log(hashTable.get(123));
console.log(hashTable.get(112));//linked
console.log(hashTable.get(134));//not exist

In my implementation, my hash function is to get the remainder of the key divided by the size of hash table. Per the solution to collision, I used linked list to store entries which have the collided hashes.

\$\endgroup\$
  • \$\begingroup\$ What problem are you trying to solve that is not already solved by the keys on a Javascript object? \$\endgroup\$ – jfriend00 Jan 12 '15 at 4:25
  • \$\begingroup\$ @jfriend00 Yes, Javascript has Object and can save key-value pair information, and it is easily retrieving value by passing key. But what I was trying to do is to simulate an hash table using javascript. Basically, it converts the input into an hash table's index where I can put the entry. I am using it to practice the implementation of hash-table data structure. \$\endgroup\$ – zhujy_8833 Jan 12 '15 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.