miku86

Intro 🌐

Last time, we learned how to get the whole entries (= all key-value pairs) of our Hash Table.

Today, we'll do a small recap of our Hash Table.

Thoughts about the Hash Table 💭

The Hash Table data structure is a very important concept, therefore most languages have (a variation of) a hash table built-in, e.g. JavaScript has an object.

In our daily developer life we use object a lot, because it is an easy-to-grasp concept, that uses a (hopefully human-readable) key that is matched to a value, e.g. the key name is mapped to the value miku86.

In contrast to an array, we don't have to know the index of a value, e.g. person[1]. Instead, we can simply use the human-readable key, e.g. person.name.

Big O

• Access: O(1)
• Insert: O(1)
• Remove: O(1)
• Search: O(N)

As we can see, the Hash Table is very fast. Access, Insert and Remove need constant time to do their job, meaning an increase of the amount of data in the Hash Table doesn't increase the time needed to do the job.

But be mindful of the fact, that these values heavily depend on the quality of our hash function.

If we build a bad hash function (like ours), that doesn't distribute the key-value pairs very well, we'll get a lot of collisions, therefore our hash table could be very slow with a lot of data in it.

So you mostly want to use the built-in hash table of your language, instead of your own implementation, because the built-in one is well-optimized.

Final Implementation 📝

Our Hash Table has these methods:

• hash: to create a hash for our key
• set: to add a key-value pair
• get: to get a specific key-value pair by using the key
• keys: to get all keys
• values: to get all values
• entries: to get all key-value pairs

class Hashtable {
  constructor() {
    this.data = [];
    this.size = 0;
  }

  hash(key) {
    const chars = key.split("");
    const charCodes = chars.map((char) => char.charCodeAt());
    const charCodeSum = charCodes.reduce((acc, cur) => acc + cur);
    return charCodeSum;
  }

  set(key, value) {
    const hash = this.hash(key);

    if (!this.data[hash]) {
      this.data[hash] = [];
    }

    this.data[hash].push([key, value]);
    this.size++;
  }

  get(key) {
    const hash = this.hash(key);

    if (this.data[hash]) {
      for (const item of this.data[hash]) {
        if (item[0] === key) {
          return item;
        }
      }
    }
  }

  keys() {
    const keys = [];

    for (let bucket of this.data) {
      if (bucket) {
        for (let item of bucket) {
          keys.push(item[0]);
        }
      }
    }

    return keys;
  }

  values() {
    const values = [];

    for (let bucket of this.data) {
      if (bucket) {
        for (let item of bucket) {
          values.push(item[1]);
        }
      }
    }

    return values;
  }

  entries() {
    const entries = [];

    for (let bucket of this.data) {
      if (bucket) {
        for (let item of bucket) {
          entries.push(item);
        }
      }
    }

    return entries;
  }
}

Further Reading 📖

• Simple Wiki: Hash Table
• Wikipedia: Hash Table
• Wikibooks: Hash Table

Questions ❔

• Do you understand the concept?
• Can you explain the concept to another person?
• Can you implement the Hash Table on your own without looking at the code?
• Can you think about the Big O of a Hash Table (without looking it up)?

Next ➡️

I hope you learned something about the concept of a Hash Table and tried your best to implement it on your own!

Which data structure should I cover next?