JavaScript Data Structures: Hash Table: Add data

2020-04-07

Intro 🌐

Last time, we learned how to setup our hash table .

Today, we'll use all of the stuff we learned so far to add data to our Hash Table.

Requirements 💭

We need the following parts to add data to our Hash Table:

a method to add data(set)
data we want to add (a key-value-pair)
a hash function to hash our key (hash)

Starter Code ▶️

We start with the setup code that has the constructor and the hash function.

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

  // a hash function that inputs a key and outputs an array index
  hash(key) {
    const chars = key.split("");
    const charCodes = chars.map((char) => char.charCodeAt());
    const charCodeSum = charCodes.reduce((acc, cur) => acc + cur);
    return charCodeSum;
  }
}

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 NO other key with this hash key: create an empty array at the correct position (= the hashed key), take the key-value-pair, add it as an array to the end of the created new array
if there already is a key with this hash: take the key-value-pair, add it as an array to the end of the existing array (separate chaining)
increase the Hash Table's size by 1

If you are not familiar with separate chaining, re-read this post.

Differences:

if the hashed key is new, add a new empty array at this position; if the hashed key already exists, there will already be an array at this position, so no need to create a new one

Example

// currently empty hash table:
hashTableData = [];

// desired hash table:
hashTableData = [
  [
    ["name", "miku86"], // array in array at index 0
  ],
];

Steps:

// currently empty hash table:
hashTableData = [];

// hash the key (= "name") with our hash function: our imaginary (!) hash function outputs 0 as the hash key
// there is NO other data at index 0 (currently no other key with this hash)
// therefore we create an empty array at the correct position (= the hashed key)
hashTableData = [
  [], // empty array at index 0 (because our imaginary hash function returned 0 as hash)
];

// we take the key-value-pair and make it an array
newKeyValuePair = ["name", "miku86"];

// we add the newKeyValuePair-array to the end of the newly created empty array
hashTableData = [
  [
    ["name", "miku86"], // newKeyValuePair from above
  ],
];

// desired hash table:
hashTableData = [
  [
    ["name", "miku86"], // array in array at index 0
  ],
];

✅

Array in Array in Array? 🤷

If we add a lot of data, there could be some hash collisions (duplicate results of the hashed key). We solve this by separate chaining. In our example, we can simply add a new key-value-pair after our current newKeyValuePair.

hashTableData = [
  [
    ["name", "miku86"], // array in array at index 0
    ["mean", false], // same hash, therefore same array index in parent array (= 0)
  ],
];

In theory, we wouldn't need an array in array in array, if we only would have one key-value-pair at every index (= no collisions or using linear probing instead of separate chaining). But because our custom hash function is really bad and we want to learn the basics, we do it like this.

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

    // if the hashed key is new, add a new empty array at this position
    // if the hashed key already exists, there will already be an array at this position
    // => so no need to create a new one
    if (!this.data[hash]) {
      this.data[hash] = [];
    }

    // save they key-value pair at the hashed array index
    this.data[hash].push([key, value]);

    // increase the hash table's size by 1
    this.size++;
  }
}

Result

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

// hash table should have no data and size 0
console.log(newHashtable);
// Hashtable { data: [], size: 0 } ✅

// add a new key-value pair
newHashtable.set("name", "miku86");
console.log(newHashtable.data);
// [ <417 empty items>, [ [ 'name', 'miku86' ] ] ]
// the hash of 'name' is 417, so it will go to array index 417, all indexes in front (0-416) will be empty

// add a new key-value pair
newHashtable.set("mean", false);
console.log(newHashtable.data);
// [ <417 empty items>, [ [ 'name', 'miku86' ], [ 'mean', false ] ] ]
// 'name' and 'mean' have the same hash (417), so both go to index 417

// add a new key-value pair
newHashtable.set("age", 33);
console.log(newHashtable.data);
// [ <301 empty items>, [ [ 'age', 33 ] ], <115 empty items>, [ [ 'name', 'miku86' ], [ 'mean', false ] ] ]
// 'age' has hash 301, so goes to index 301.
// 'name' and 'mean' go to index 417, therefore there is a gap from 302 to 416, so 115 empty items

Next Part ➡️

Wow, a lot of explanations after our longer break!

Great work if you made it to the end.

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

Need some mentoring? Click here!

Questions ❔

How would you implement the set-function?