JavaScript Data Structures: Hash Table: Get data

2020-04-08

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!

Questions ❔

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