The Hashtable

What is a Hashtable?#

A hashtable is a data structure allowing for key-value mapping using an associative array abstract data type. A hashtable uses a hash function to generate an index at which the key value pair will be inserted into the hashtable. Therefore, the hashing function should compute a unique and constant index for each value, but some hashing functions can generate the same index for different keys. This is what is called a hash collision which we won’t get into here as we will only implement a simple hashtable.

fig. 01

Benefits#

The hashtable allows for a very efficient access to the data, as there is no need to iterate on every items of the hashtable to find the target. This direct access makes it a good data structure for lookup objects in Javascript / Typescript to avoid nested loops. On each data access, only the required key is computed in order to retrieve the index.

Practical uses in web development#

Hashtables have many uses in web development, one of my favourite is a lookup object to avoid nested loops and prevent performance issues. In Javascript and Typescript, object can be used as a very basic hashtable to store values with unique keys. Such pattern is very helpful for query batching in the dataloader pattern to avoid n+1 issues with graphql relations.

While not implemented as a Javascript hashtable in the following example the lookup object acts as one and uses the item id as key for its value in the lookup object. This lookup is then used for direct data access in the returned array.map function. This allows this batchQueries function to avoid using a nested loop in the return array map function. It means that we only iterate on the data and ids arrays once.

export async function batchQueries<T extends Document>(
  model: Model<T>,
  ids: Array<string>,
) {
  const data = await model.find({ _id: { $in: ids } })
  const lookup: Record<string, T> = data.reduce((acc: Record<string, T>, item: T) => {
    acc[item.id] = item
    return acc
  }, {})
  return ids.map((id) => lookup[id] || null) 
}

In Javascript and Typescript, the unique key constraint of the object makes it a good candidate for basic hashtable usages such as lookup objects.

Basic hashtable#

We will now implement a hashtable using Typescript class syntax.

First we need to create a hashing function that will output the same value for the same key:

function hashingFn(string: string, number: number) {
  let sum = 0
  for (let i = 0; i < string.length; i++) {
    sum += string.charCodeAt(i) * 3
  }
  return sum % number
}

Then the hashtable properties and initialization. This hashtable will be given a size parameter used in the hashing function and hold the data in a storage array.

export class HashTable<T> {
  size: number
  storage: Array<Array<[string, T]>>
  constructor(size: number) {
    this.size = size
    this.storage = []
  }
}

Basic methods#

• Insert()

The insert method first creates an index for the given key and then inserts the value at the given index in the storage as a [key, value] array.

insert(key: string, value: T) {
    const index = hashingFn(key, this.size);

    if (!this.storage[index]) {
      this.storage[index] = [];
    }
    this.storage[index].push([key, value]);
  }

• Get()

The get method is quite simple as it first computes the index for target key, gets the storage value reference at the given index and then iterates on the array value to return nested array index 1 (the value).

get(key: string) {
    const index = hashingFn(key, this.size);
    let arrayAtIndex = this.storage[index];
    if (!arrayAtIndex) return null;

    for (let i = 0; i < arrayAtIndex.length; i++) {
      if (arrayAtIndex[i] && arrayAtIndex[i][0] === key) {
        return arrayAtIndex[i][1];
      }
    }
    return null;
  }

• Remove()

The remove method does the same as the get method but then deletes the nested array whose key matches the given key.

remove(key: string) {
    const index = hashingFn(key, this.size);
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      for (let i = 0; i < arrayAtIndex.length; i++) {
        arrayAtIndex[i][0] === key && delete arrayAtIndex[i];
        break;
      }
    }
  }