Implement a Hash Map

Arrays are amazing for looking up elements at specific indices as all elements in memory are contiguous, allowing for O(1) or constant time lookups. But often we don't, or can't, perform lookups via indices. Hash maps and hash tables are a way around this, enabling us to lookup via keys instead.

Can you implement the Map class from scratch? Only two methods are necessary-- get and set. Many programming languages have a built-in hash or dictionary primitive (like Javascript Objects and {} notation), but we don't want to use that for this exercise.

Note: Regular Javascript objects and the Map class are both simple key-value hash tables/associative arrays, with a few key differences:

A Map object can iterate through its elements in insertion order, whereas JavaScript's Objects don't guarantee order. In addition, Objects have default keys due to their prototype, and Maps don't come with default keys. Here's a good breakdown of the two. For the purpose of this exercise, let's assume the same functionality for both.

For the two methods you'll define:

1. get(key: string) should be given a key, and return the value for that key.
2. set(key: string, val: string) should take a key and a value as parameters, and store the pair.

Additionally, we've supplied the below hashing function hashStr. It tries to avoid collision, but is not perfect. It takes in a string value and returns an integer.

function hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
        const charCode = str.charCodeAt(i);
        finalHash += charCode;
    }
    return finalHash;
}

console.log(hashStr('testKey'))

def hashStr(key):
    result = 5381
    for char in key:
        result = 33 * result + ord(char)
    return result

print(hashStr("testKey"))

public class Main {
  public static int hashStr(String str) {
    int finalHash = 0;
    for (int i = 0; i < str.length(); i++) {
      char charCode = str.charAt(i);
      finalHash += (int) charCode;
    }
    return finalHash;
  }

  public static void main(String[] args) {
    System.out.println(hashStr("testKey"));
  }
}

Let's call our new class the Hashmap class, and use it like such:

const m = new Hashmap();
m.set('name', 'Jake');
console.log(m.get('name'));

m = Hashmap()
m.set('name', 'Jake')
print(m.get('name'))

import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    HashMap<String, String> m = new HashMap<>();
    m.put("name", "Jake");
    System.out.println(m.get("name"));
  }
}

Constraints

• Sum of lengths of the string <= 10000
• The string will consist of ASCII characters
• Expected time complexity for inserting a key,value pair and retrieving a value : O(1)
• Expected space complexity : O(n)

```js
class Hashmap {
  constructor() {
    // implement this
  }

  set(key, val) {
    // implement this    
  }

  get(key) {
    // implement this    
  }

  hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      finalHash += charCode;
    }
    return finalHash;
  }
}

const m = new Hashmap();
m.set('name', 'Jake');
console.log(m.get('name'));
```

Let's begin by revisiting how a general hash table works, the theory being what our Hashmap data structure will be based off. As we've noted, in many programming languages, there is a Hashmap class that's based off a legacy Hashtable. Let's step through our suggested implementation of this code.

So we know that hash tables work by storing data in buckets. To access those buckets, we'll need a way to convert a key to an bucket number. (The buckets can be modeled using both arrays and binary search trees, but to keep things simple and maximize speed, we'll stick with using arrays.)

Using keys decouples us from having to know where the data is in the array. Our data structure thus needs a hash function, provided in this case as hashStr, to calculate an index into buckets where the wanted value is stored. We're essentially mapping the key to an array index via our hashStr hash function.

hashStr('r')
// 114

// array = [  _  ,  X  ,  _  ,  _ ]
// index     113   114   115   116

As you can see, all hashStr does is take the key provided in set(), and computes a location for us. We'll thus need another data structure for the actual storage and buckets that the values are placed. Of course, you already know it's an array!

The slots or buckets of a hash table are usually stored in an _______ and its indices.

A good start to writing the class is to initialize it with just the bare minimums. We need a storage array, so let's start there:

class Hashmap {
  constructor() {
    this._storage = [];
  }
}

class Hashmap:
    def __init__(self):
        self.storage = [None for _ in range(16)]
        self.size = 0

public class Hashmap {
  private Object[] _storage;

  public Hashmap() {
    this._storage = new Object[];
  }
}

We'll use the returned index of hashStr to decide where the entered value should go in this._storage.

A word on a collisions: collisions are when a hash function returns the same index for more than one key and are out of the scope of this question. However, there are ways to handle such issues using additional data structures.

Which of the following is a solution for collisions in a hash table implementation?

At this point, we have our building blocks, so let's go ahead and implement the set method. The method will:

1. take the key passed
2. run it through the hash function, and
3. set the value in our storage at that particular index

Notice the way we're storing it as well: each index in this._storage (this._storage[idx]) is itself an array, thereby primitively solving for the collision problem.

set(key, val) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    this._storage[idx] = [];
  }

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

# Optional Node class
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value

# For inclusion in the Hashmap class
def set(self, key, val):
    # We can optionally set the value as a Node
    p = Node(key, val)
    key_hash = self.hashStr(key)
    index = self.position(key_hash)

    if not self.storage[index]:
        self.storage[index] = [p]
        self.size += 1
    else:
        list_at_index = self.storage[index]
        if p not in list_at_index:
            self.storage[index] = [p]
            self.size += 1
        else:
            for i in self.storage[index]:
                if i == p:
                    i.value = val
                    break

public void set(String key, Object val) {
  int idx = hashStr(key);

  if (this._storage[idx] == null) {
    this._storage[idx] = new ArrayList<>();
  }

  this._storage[idx].add(new Object[] {key, val});
}

The set method now seems pretty straightforward, right?

It's the same concept with our get method. What we're doing there is also running the passed key through the hashStr method, but instead of setting, we'll go to the resulting index and retrieve/return the found value.

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }

def get(self, key):
    key_hash = self.hashStr(key)
    index = self.position(key_hash)

    list_at_index = self.storage[index]
    for i in self.storage[index]:
        if i.key == key:
            return i.value
    return None

for (Object[] keyVal : this._storage[idx]) {
  if (keyVal[0].equals(key)) {
    return keyVal[1];
  }
}

One caveat we should note is that it's possible to pass a key that doesn't exist (or has not been set), so we should handle that by returning undefined or None if that's the case.

get(key) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    return undefined;
  }

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }
}

def get(self, key):
    key_hash = self.hashStr(key)
    index = self.position(key_hash)

    if not self.storage[index]:
        return None
    else:
        list_at_index = self.storage[index]
        for i in self.storage[index]:
            if i.key == key:
                return i.value
    return None

public Object get(String key) {
  int idx = hashStr(key);

  if (this._storage[idx] == null) {
    return null;
  }

  for (Object[] keyVal : this._storage[idx]) {
    if (keyVal[0].equals(key)) {
      return keyVal[1];
    }
  }
}

That should about do it! Let's try it out.

Complexity for Final Solution

The hash map data structure grows linearly to hold n elements for O(n) linear space complexity. Assuming a good hash function (one that minimizes collisions!) we usually have O(1) constant get/set complexity. Otherwise, in the worst case where all n entries hash to the same bucket we traverse through for an unfortunate O(n) linear get/set complexity.

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.