loading...

JavaScript Data Structures: Hash Table: Recap

miku86 profile image miku86 ・3 min read

JavaScript Data Structures (40 Part Series)

1) JavaScript Data Structures: Singly Linked List 2) JavaScript Data Structures: Singly Linked List: Setup 3 ... 38 3) JavaScript Data Structures: Singly Linked List: Push 4) JavaScript Data Structures: Singly Linked List: Pop 5) JavaScript Data Structures: Singly Linked List: Unshift 6) JavaScript Data Structures: Singly Linked List: Shift 7) JavaScript Data Structures: Singly Linked List: Get 8) JavaScript Data Structures: Singly Linked List: Set 9) JavaScript Data Structures: Singly Linked List: Insert 10) JavaScript Data Structures: Singly Linked List: Remove 11) JavaScript Data Structures: Singly Linked List: Recap 12) JavaScript Data Structures: Doubly Linked List: Intro and Setup 13) JavaScript Data Structures: Doubly Linked List: Push / Add data to the end 14) JavaScript Data Structures: Doubly Linked List: Pop / Remove data from the end 15) JavaScript Data Structures: Doubly Linked List: Unshift / Add data to the beginning 16) JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning 17) JavaScript Data Structures: Doubly Linked List: Get a specific node by its index 18) JavaScript Data Structures: Doubly Linked List: Set / Update a specific node 19) JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index 20) JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index 21) JavaScript Data Structures: Doubly Linked List: Recap 22) JavaScript Data Structures: Stack: Intro 23) JavaScript Data Structures: Stack: Push / Add a new node 24) JavaScript Data Structures: Stack: Pop / Remove the last node 25) JavaScript Data Structures: Stack: Recap 26) JavaScript Data Structures: Queue: Intro 27) JavaScript Data Structures: Queue: Enqueue 28) JavaScript Data Structures: Queue: Dequeue 29) JavaScript Data Structures: Queue: Recap 30) JavaScript Data Structures: Recap: Lists, Stack, Queue 31) JavaScript Data Structures: Hash Table: Intro 32) JavaScript Data Structures: Hash Table: Hash Function 33) JavaScript Data Structures: Hash Table: Collisions 34) JavaScript Data Structures: Hash Table: Setup 35) JavaScript Data Structures: Hash Table: Add data 36) JavaScript Data Structures: Hash Table: Get data 37) JavaScript Data Structures: Hash Table: Get keys 38) JavaScript Data Structures: Hash Table: Get values 39) JavaScript Data Structures: Hash Table: Get all entries 40) JavaScript Data Structures: Hash Table: Recap

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 📖


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?

JavaScript Data Structures (40 Part Series)

1) JavaScript Data Structures: Singly Linked List 2) JavaScript Data Structures: Singly Linked List: Setup 3 ... 38 3) JavaScript Data Structures: Singly Linked List: Push 4) JavaScript Data Structures: Singly Linked List: Pop 5) JavaScript Data Structures: Singly Linked List: Unshift 6) JavaScript Data Structures: Singly Linked List: Shift 7) JavaScript Data Structures: Singly Linked List: Get 8) JavaScript Data Structures: Singly Linked List: Set 9) JavaScript Data Structures: Singly Linked List: Insert 10) JavaScript Data Structures: Singly Linked List: Remove 11) JavaScript Data Structures: Singly Linked List: Recap 12) JavaScript Data Structures: Doubly Linked List: Intro and Setup 13) JavaScript Data Structures: Doubly Linked List: Push / Add data to the end 14) JavaScript Data Structures: Doubly Linked List: Pop / Remove data from the end 15) JavaScript Data Structures: Doubly Linked List: Unshift / Add data to the beginning 16) JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning 17) JavaScript Data Structures: Doubly Linked List: Get a specific node by its index 18) JavaScript Data Structures: Doubly Linked List: Set / Update a specific node 19) JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index 20) JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index 21) JavaScript Data Structures: Doubly Linked List: Recap 22) JavaScript Data Structures: Stack: Intro 23) JavaScript Data Structures: Stack: Push / Add a new node 24) JavaScript Data Structures: Stack: Pop / Remove the last node 25) JavaScript Data Structures: Stack: Recap 26) JavaScript Data Structures: Queue: Intro 27) JavaScript Data Structures: Queue: Enqueue 28) JavaScript Data Structures: Queue: Dequeue 29) JavaScript Data Structures: Queue: Recap 30) JavaScript Data Structures: Recap: Lists, Stack, Queue 31) JavaScript Data Structures: Hash Table: Intro 32) JavaScript Data Structures: Hash Table: Hash Function 33) JavaScript Data Structures: Hash Table: Collisions 34) JavaScript Data Structures: Hash Table: Setup 35) JavaScript Data Structures: Hash Table: Add data 36) JavaScript Data Structures: Hash Table: Get data 37) JavaScript Data Structures: Hash Table: Get keys 38) JavaScript Data Structures: Hash Table: Get values 39) JavaScript Data Structures: Hash Table: Get all entries 40) JavaScript Data Structures: Hash Table: Recap

Posted on Apr 15 by:

miku86 profile

miku86

@miku86

Mentor & Educator & Web Developer - I help people to reach their (career) goals. => https://miku86.com/mentoring

Discussion

markdown guide