JavaScript Data Structures: Hash Table: Get data

Intro 🌐

Last time, we learned how to add data to our hash table .

Today, we'll learn how to get data out of our Hash Table.


Requirements 💭

We need the following parts to get data from our Hash Table:

  • a method to get data(get)
  • a key we want to search for (key)
  • a hash function to hash our key (hash)

Starter Code ▶️

We start with the code from the last lesson, so that we can use the set method to add some data.

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++;
  }
}

If you are not familiar with the hash function, re-read this post.


Thoughts 💭

First, we should think about the constraints and possibilities:

  • first, we have to hash the key with our hash function
  • if there is data at this specific array index (= the hashed key), iterate over this data, search for the key and return the key-value pair
  • if there is data at this specific array index (= the hashed key), but not with our desired key, return null
  • if there is no data at the array index of the hashed key, return null

Example

We want to get the key-value pair with the key name.

// current hash table data:
hashTableData = [
  [
    ["name", "miku86"],
    ["mean", false],
  ],
  [["age", 33]],
];

// desired data:
["name", "miku86"];

Steps

// current hash table data:
hashTableData = [
  [
    ["name", "miku86"],
    ["mean", false],
  ],
  [["age", 33]],
];

// we hash the key (= `name`) with our imaginary (!) hash function
0;

// we go to the specific array index (= 0)
[
  ["name", "miku86"],
  ["mean", false],
];

// we go to the first key-value pair in this array
["name", "miku86"];

// this is the key (= "name") we search for, therefore we return the key-value pair
["name", "miku86"];

// desired data:
["name", "miku86"];


Implementation ⛑

// a Hash Table class
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) {
    // hash the key
    const hash = this.hash(key);

    // look if there is any data at this specific array index
    if (this.data[hash]) {
      // iterate over this data
      for (const item of this.data[hash]) {
        // look if the first value of the array is the desired key, e.g. name
        if (item[0] === key) {
          // if so, then return the key-value pair
          return item;
        }
      }
    }

    // if there is no data at this specific array index
    // OR if there is data, but not with the correct key
    // then return null
    return null;
  }
}

Note: I'm using a for ... of-loop. If you don't know how this works, you can read about it on MDN. You can use whatever you want to use, a default for-loop, a for ... in-loop, a functional approach etc.


Result

// create a new hash table
const newHashtable = new Hashtable();

// add three new key-value pairs
newHashtable.set("name", "miku86");
newHashtable.set("mean", false);
newHashtable.set("age", 33);
console.log(newHashtable.data);
// [ <301 empty items>, [ [ 'age', 33 ] ], <115 empty items>, [ [ 'name', 'miku86' ], [ 'mean', false ] ] ]

console.log(newHashtable.get("name"));
// [ 'name', 'miku86' ] ✅

console.log(newHashtable.get("mean"));
// [ 'mean', false ] ✅

console.log(newHashtable.get("age"));
// [ 'age', 33 ] ✅

console.log(newHashtable.get("nothing to see"));
// null, because wrong array index ✅

console.log(newHashtable.get("naem"));
// null, because correct array index, but wrong key ✅


Next Part ➡️

We managed to write a simple function that gets us our data, great work!

Next time, we'll learn how to get all keys from our Hash Table.

Need some mentoring? Click here!


Further Reading 📖


Questions ❔

  • How would you implement the get-function?
  • How would you write this code in a functional style?