Hash Tables

Today, we're going to talk about a very common data structure that is built into almost every programming language. In JavaScript, they are referred to as objects or Maps.

Hash tables are used to store key-value pairs, but do you really know how they work? Before diving into the mechanics, let's start with why we use them.

Why Use Hash Tables?

• Labeling Values: Hash tables are useful for labeling values within a collection.
• Efficient Retrieval: They provide an efficient way to retrieve values based on keys.

Theory

Example Scenario

Imagine working with city coordinates. Storing them in an array might look like this:

const coordinates = ["123.123", "456.456", "789.789"];

Retrieving coordinates from an array requires knowing the index, which isn't user-friendly otherwise we can use the find utility function but then we have a performance issue because every value has to be visited for comparison.

Using a hash table makes retrieval more intuitive:

const cities = { Paris: "123.123", London: "456.456", Amsterdam: "789.789" };

cities["Paris"]; // "123.123"

Hash Tables hash

For each inserted value, a hash is generated. This hash must respect the following rules:

• Deterministic: Produce the same result for the same value every time.
• Fixed Size: The result should always have the same size.
• Avoid Collisions: It should be impossible to have the same hash result for two different inputs.
• Performance: Should be generated in constant time.

Handling Collisions

There are two main options for handling collisions:

• Separate Chaining: Uses another data structure (e.g., an array) to store multiple values at the same index.
• Linear Probing: Finds the next empty slot whenever a key is already taken.

For simplicity, we will use separate chaining.

Implementation

Hash Table Class

The HashTable class represents our custom data structure, which is essentially an array.

class HashTable {
  constructor(size = 30) {
    this.map = new Array(size);
  }
}

This hash table is based on an array of a predefined size. The array can grow past this size, but setting a size allows us to reserve just the amount of memory we need.

Set Function

The set function adds a key-value pair to the hash table.

function set(key, value) {
  const index = hash(key, this.map.length + 1);
  if (!this.map[index]) this.map[index] = [];
  this.map[index].push([key, value]);
  return index;
}

Explanation:

• Generate an index using the hash function.
• Check if there is already a value at that index. If not, initialize it as an empty array.
• Push the key-value pair as an array and return the index.

const hash = new HashTable(5);
hash.length; // 5
hash.set("Paris", "123.123"); // 4
// [null, null, null, [["Paris", "123.123"]], null]

In case of a collision, the next inserted value would also be added at the same index.

hash.set("London", "456.456"); // 4
// [null, null, null, [["Paris", "123.123"], ["London", "456.456"]], null]

Get Function

The get function retrieves a value based on a key.

function get(key) {
  const index = hash(key, this.map.length + 1);
  const results = this.map[index];
  if (!results) return undefined;
  const foundItem = results.find((item) => item[0] === key);
  return foundItem ? foundItem[1] : undefined;
}

Explanation:

• Retrieve the hash based on the key and the length of the hash table.
• Use the index to retrieve the key-value pairs.
• If there is no value at the index, return undefined.
• Otherwise, find the appropriate key-value pair by comparing the key in the subarray.
• Return the value if a match is found; otherwise, return undefined.

So if we tried to retrieve our previously added value:

hash.get("Paris"); // "123.123";

Keys Function

The keys function returns all the keys in the hash table.

function keys() {
  const keys = [];
  for (let i = 0; i < this.map.length; i++) {
    if (this.map[i]) {
      for (let j = 0; j < this.map[i].length; j++) {
        keys.push(this.map[i][j][0]);
      }
    }
  }

  return keys;
}

Explanation:

• Define an array to store the keys.
• Loop over every element in the hash table.
• If there is a value at the current index, loop over the subarray of key-value pairs and push the key to the keys array.

Values

The values function returns all the values in the hash table.

function values() {
  const values = [];
  for (let i = 0; i < this.map.length; i++) {
    if (this.map[i]) {
      for (let j = 0; j < this.map[i].length; j++) {
        values.push(this.map[i][j][1]);
      }
    }
  }
  return values;
}

Explanation:

• Define an array to store the values.
• Loop over every element in the hash table.
• If there is a value at the current index, loop over the array of key-value pairs and push the value to the values array.

Practical Use Cases

Hash tables are incredibly versatile and can be used in various real-world scenarios:

• Caching: Storing computed results to avoid redundant calculations.
• Databases: Indexing data for faster retrieval.
• Object Representation: Representing objects with attributes.

Performance Considerations

Hash tables offer excellent performance for insertion, deletion, and retrieval operations:

• Time Complexity: Average time complexity for insertion, deletion, and retrieval is O(1).
• Space Complexity: Space complexity is O(n) due to the storage required for the key-value pairs.

Conclusion

Hash tables are a fundamental data structure that provides efficient key-value storage and retrieval. While built-in data structures like JavaScript's Map are typically sufficient, understanding how to implement a hash table can be valuable for educational purposes and specific edge cases.

Thanks for reading! If you have any questions or recommendations, please leave a comment. I might learn something new.

Happy coding!