One Pager Cheat Sheet

• You can implement a Hashmap class from scratch, with the get and set methods for retrieving and storing key and value pairs, and a hashing function for converting strings to integers, to enable O(1) lookups.
• We are creating a Hashmap data structure based off a legacy Hashtable, taking advantage of a hash function to map keys to buckets and store our data in the corresponding index of an array.
• The key provided to set() is used to compute a location in the hashStr() function, and an array is needed for the actual value storage.
• The slots of a hash table are typically stored in an array whose indices refer to the computed location given by the hash function, and whose buckets refer to the data structure in which the key-value pairs are stored for efficient insertion and retrieval.
• Creating a class with a storage array as the bare minimum is a good initialization step.
• We will hashStr to determine the appropriate index to store the value in this._storage, and handle any possible collisions using additional data structures.
• Hash tables can use a linked list structure to store multiple values at the same index to prevent collisions.
• We can implement the set method by converting the key to an index in this._storage and setting the value using an array to primitively solve for the collision problem.
• Both get and set methods take a key as an argument and use the hashStr method to find the appropriate index in a data structure; get returns the value located at the index, while set stores a key-value pair at the indexed location.
• When using these methods, we should always check to see if a key exists and handle any cases where it doesn't by returning undefined or None.
• The hash map data structure grows linearly with O(n) space complexity, with O(1) constant get/set complexity in most cases, and O(n) linear get/set complexity in the worst case.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require("assert");

​

class Hashmap {

  constructor() {

    this._storage = [];

  }

​

  hashStr(str) {

    let finalHash = 0;

    for (let i = 0; i < str.length; i++) {

      const charCode = str.charCodeAt(i);

      finalHash += charCode;

    }

    return finalHash;

  }

​

  set(key, val) {

    let idx = this.hashStr(key);

​

    if (!this._storage[idx]) {

      this._storage[idx] = [];

    }

​

    this._storage[idx].push([key, val]);

  }

​

  get(key) {

    let idx = this.hashStr(key);

​

    if (!this._storage[idx]) {

      return undefined;

    }

Great job getting through this. Let's move on.

If you had any problems with this tutorial, check out the main forum thread here.