Guru on Rails

if you don’t sacrifice for your dream then your dream becomes your sacrifice.
Sydney, Sat 01 Jun 2019
Hash Table data structure
Wed 24 Oct 2018

You might know, algorithm almost needs data structure. Any data structure is born with at least one reason. What problems does it solve? Speaking of hash table, it's efficient for complex structure of data. It also makes the index of array is readable. We can combine array with other data structure such as linked list, binary search tree, binary heaps or even other arrays.

Hash table is not new. Let's have a look on Wikipedia.

Hence, we should define two main behaviors.

set get
  • Accepts a key and a value.
  • Hashes the key.
  • Stores the key-value pair in the hash table array via separate chaining.
 
  • Accepts a key.
  • Hashes the key.
  • Retrieves the key-value pair in the hash table.
  • If the key isn't found, returns undefined.

We implement two parts:

  • initializing an array with an input size in order to contain the separating chain.
  • implementing separating chain (we choose array or linked list).

For example, below is the array with size is 5 and separating chain is linked list.

The matter here is how we know that we should put "Sue" to index 1? That is hash function. In fact, it depends on how we want to convert key to a number. The hash table is simple like that. Let's go to implement it.

Constructor

class HashTable {
    // size is array size to store key value - keyMap (converted to number)
    // weirdPrime for making it different
    constructor(size = 53, options = {}){
      this.keyMap = new Array(size);
      this.weirdPrime = options.weirdPrime || 31;
      this.maxKeyLength = options.maxKeyLength || 100;
    }
}

We initialize a table with an array to contains separating chain. We will convert the keys to numbers but what happen if the key is too long? We should limit the length whatever it is. The weird prime is the constant that we want to make it different. The same set of keys but if we input another weird prime, the order in array will be different.

Hash function & Setter & Getter

    // convert key to number which is in range: 0..size
    // maximum length is 100 characters of key
    _hash(key) {
      let total = 0;
      for (let i = 0; i < Math.min(key.length, this.maxKeyLength); i++) {
        let value = key[i].charCodeAt(0);
        total = (total * this.weirdPrime + value)
      }
      total = total % this.keyMap.length;
      return total;
    }

Obviously we have to use "%" operator to make the index in range of 0..size. For the total number, feel free to implement.

    // we use another array for separate chain (same index)
    set(key,value){
      let index = this._hash(key);
      if(!this.keyMap[index]){
        this.keyMap[index] = [];
      }
      this.keyMap[index].push([key, value]);
    }

The last line we use an array as separating chain or subchain put as element in parent array. From setter we will implement corresponding setter (based on structure of separating chain).

    // get key correspoding with the sort of separate chain
    get(key){
      let index = this._hash(key);
      if(this.keyMap[index]){
        for(let i = 0; i < this.keyMap[index].length; i++){
          if(this.keyMap[index][i][0] === key) {
            return this.keyMap[index][i][1]
          }
        }
      }
      return undefined;
    }

Furthermore, we can implement more two methods to get collection of keys and values if necessary.

    // get collection of keys
    keys(){
      let keysArr = [];
      for(let i = 0; i < this.keyMap.length; i++){
        if(this.keyMap[i]){
          for(let j = 0; j < this.keyMap[i].length; j++){
            if(!keysArr.includes(this.keyMap[i][j][0])){
              keysArr.push(this.keyMap[i][j][0])
            }
          }
        }
      }
      return keysArr;
    }

    // get collection of values
    values(){
      let valuesArr = [];
      for(let i = 0; i < this.keyMap.length; i++){
        if(this.keyMap[i]){
          for(let j = 0; j < this.keyMap[i].length; j++){
            if(!valuesArr.includes(this.keyMap[i][j][1])){
              valuesArr.push(this.keyMap[i][j][1])
            }
          }
        }
      }
      return valuesArr;
    }

Full code here.

https://github.com/nctruong/master-problem-solving/blob/master/data-structures/hash-table.js