Hash Tables in JavaScript

Hash tables are a type of data structure that let you store information using a "key" and a "value" pair. They're kind of like a phone book, where you can look up a name (the key) and find the corresponding phone number (the value).

Compared to a regular list, where you have to search through every item to find what you're looking for, hash tables make it much faster to find a specific item. This is because the hash function can quickly jump to the spot in memory where the data is stored, based on the key you're searching for.

When we have a large amount of data and we want to look up specific values, it can be very inefficient to search through all the data. Hash tables provide a more efficient way to store and look up data because they use a mathematical function called a hash function to map keys to specific locations in memory.

By using a hash function, we can avoid the need to search through the entire dataset to find the value we are looking for. Instead, we can use the key to compute the memory address where the value is stored and retrieve it directly. This means that we can look up values much more quickly than we could using a traditional list or array.

Hash tables are commonly used in programming because they provide a fast and efficient way to store and retrieve data. They are used in a wide range of applications, from databases and search engines to web servers and operating systems. In particular, hash tables are often used in cases where we need to quickly look up data based on a specific key, such as in a dictionary or phone book.

Here's a simple implementation of a hash table in JavaScript:

// Define a HashTable function that takes an optional "size" parameter with a default value of 100.
function HashTable(size = 100) {
  // Create an empty array with the specified size or default size.
  const buckets = new Array(size);

  // Define a hash function that takes a "key" parameter and returns a hash code.
  function hash(key) {
    let hash = 0;
    // Loop over each character in the key and add its Unicode value to the hash code.
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    // Return the hash code modulo the number of buckets, which ensures the hash code maps to a valid index.
    return hash % buckets.length;
  }

  // Define a set function that takes a "key" and "value" parameter and adds a key-value pair to the hash table.
  function set(key, value) {
    // Get the index of the bucket where the key-value pair should be stored.
    const index = hash(key);
    // If the bucket at the index is empty, create a new array to store the key-value pair.
    if (!buckets[index]) {
      buckets[index] = [];
    }
    // Add the key-value pair to the bucket.
    buckets[index].push([key, value]);
  }

  // Define a get function that takes a "key" parameter and returns the value associated with that key, or null if the key is not found.
  function get(key) {
    // Get the index of the bucket where the key-value pair should be stored.
    const index = hash(key);
    // If the bucket at the index is empty, the key is not in the hash table, so return null.
    if (!buckets[index]) {
      return null;
    }
    // Loop over each key-value pair in the bucket and check if the key matches the requested key.
    for (let i = 0; i < buckets[index].length; i++) {
      if (buckets[index][i][0] === key) {
        // If the key matches, return the value.
        return buckets[index][i][1];
      }
    }
    // If the key is not found in the bucket, it is not in the hash table, so return null.
    return null;
  }

  // Return an object with the set and get functions, which can be used to interact with the hash table.
  return { set, get };
}

This implementation uses an array of arrays to store key-value pairs. The _hash method is used to compute an index in the array for a given key. The set method stores a key-value pair in the array, and the get method looks up a value by its key.

A Use-Case: Counting Word Frequencies

Here's an example of how hash tables can be used to count word frequencies in a text:

// Define a function that takes a string of text and returns a hash table of word frequencies.
function countWordFrequencies(text) {
  // Split the text into an array of words.
  const words = text.split(" ");
  // Create a new hash table to store word frequencies.
  const frequencies = HashTable();

  // Loop over each word in the array.
  for (let i = 0; i < words.length; i++) {
    const word = words[i].toLowerCase();

    // Check if the word is already in the hash table.
    const count = frequencies.get(word) || 0;

    // Increment the frequency count for the word.
    frequencies.set(word, count + 1);
  }

  // Return the hash table of word frequencies.
  return frequencies;
}

// Example usage:
const text = "The quick brown fox jumps over the lazy dog";
const frequencies = countWordFrequencies(text);
console.log(frequencies.get("the")); // Output: 2
console.log(frequencies.get("fox")); // Output: 1
console.log(frequencies.get("cat")); // Output: null

This code creates a hash table to store word frequencies. It uses the split method to break up the text into words, and then loops over the words, incrementing their frequency counts in the hash table. Finally, it looks up the frequencies of the words "the" and "fox" using the get method.

Alternative Implementations

JavaScript does not have a built-in implementation of a hash table, but there are several libraries and modules that provide similar functionality. One such example is the "Map" object in JavaScript.

The Map object in JavaScript is similar to a hash table in that it allows you to store key-value pairs and retrieve them by key. Here is an example of using a Map object to count the frequency of words in a string:

function countWord(data, word) {
  // Create a new Map object to store the word count
  const wordCount = new Map();

  // Split the input text into an array of words, then loop over each word
  data.split(" ").forEach((currWord) => {
    // Check if the current word is equal to the word to be counted
    if (currWord === word) {
      // Check if the word is already in the Map; if so, get its current count, otherwise set the count to 0
      const count = wordCount.get(word) || 0;
      // Increment the count by 1 and update the Map
      wordCount.set(word, count + 1);
    }
  });

  // Return the Map of word counts
  return wordCount;
}

// Define the input text to be analyzed
const text =
  "The road not taken, by Robert Frost. Two roads diverged in a yellow wood, And sorry I could not travel both And be one traveler, long I stood And looked down one as far as I could To where it bent in the undergrowth; Then took the other, as just as fair, And having perhaps the better claim, Because it was grassy and wanted wear; Though as for that the passing there Had worn them really about the same, And both that morning equally lay In leaves no step had trodden black. Oh, I kept the first for another day! Yet knowing how way leads on to way, I doubted if I should ever come back. I shall be telling this with a sigh Somewhere ages and ages hence: Two roads diverged in a wood, and I— I took the one less traveled by, And that has made all the difference.";

// Count the word "road" in the input text and output the Map of word counts
console.log(countWord(text, "road"));