Hash Tables in Javascript

Hash tables are a data structure that allows for fast insertion, deletion and retrieval of data.

The hash tables work by storing data in an array and using the hash function to map the data to a specific index in the array. This allows for constant time access to the data, regardless of the size of the dataset. 

In Javascript, we can implement a hash table using an object. Each key is the object that represents a specific index in the array, and the value associated with that key is the data stored at that index. Let’s take a look at the key, hash function and buckets(index). 

Key

In a hash table, a key is a unique identifier for a piece of data. The key is used to access the data stored in the table, and it is also used by the hash function to determine the index at which the data should be stored.

Hash function

The hash function is a mathematical function that takes in a key and returns an index for the hash table. The index is used to determine the location in the table where the data associated with the key should be stored. The hash function should be designed such that it generates a unique index for each unique key, and it should be fast to compute. 

Buckets

Buckets are the actual storage locations in the hash table. Each bucket corresponds to a specific index in the table, and it is used to store the data associated with the key that maps to that index. In the example above, the object this.table represents the bucket array, and each key in the object represents a specific index in the array.

Here is an example of how to implement a hash table in JavaScript:

class HashTable {
  constructor() {
    this.table = {};
  }

  /*The hash function will take in a key and return an index for the table*/
  hash(key) {
    let total = 0;
    for (let i = 0; i < key.length; i++) {
      total += key.charCodeAt(i);
    }
    return total % this.table.length;
  }

   /* The set function will take in a key and a value, 
    and store the value at the index determined by the hash function */
  
  set(key, value) {
    let index = this.hash(key);
    this.table[index] = value;
  }

  /* The get function will take in a key and return 
   the value stored at the index determined by the hash function */
  get(key) {
    let index = this.hash(key);
    return this.table[index];
  }
}

To use this hash table, we can create a new instance and add key-value pairs using the set function. For example:

let myAssets = new HashTable();
hashTable.set('name', 'Bitcoin');
hashTable.set('rank', 1);
hashTable.set('price', 16000);

console.log(hashTable.get('name')); // Output: 'Bitcoin'
console.log(hashTable.get('rank')); // Output: 1
console.log(hashTable.get('price')); // Output: 16000

In this example, we have created a new hash table and added three key-value pairs to it. The key is used as the input to the hash function, which determines the index at which the value is stored. We can then retrieve the value for a given key using the get function, which also uses the key to determine the index and return the value stored at that index.

This is just a basic implementation of a hash table in JavaScript. There are many ways to improve upon this design, such as using separate chaining to handle collisions (when two keys map to the same index) or implementing a resizing mechanism to dynamically adjust the size of the table as the data set grows.

Find me on GitHub Twitter Dribbble