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
Object
s and {}
notation), but we don't want to use that for this exercise.
This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.
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 Object
s don't guarantee order. In addition, Object
s have default keys due to their prototype, and Map
s 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:
-
get(key: string)
should be given a key, and return the value for that key. -
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'))
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'));
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!
Fill In
The slots or buckets of a hash table are usually stored in an _______ and its indices.
Solution: Array
A good start to writing the class is to initialize it with just the storage array:
class Hashmap {
constructor() {
this._storage = [];
}
}
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.
Multiple Choice
Which of the following is a solution for collisions in a hash table implementation?
- There is no good solution for collisions, the hash function must be unique
- Use separate chaining, often with a linked list, where the index of the array consists of a chain of values
- Use a trie to store values at every index
- Concatenate all the values as one single string at that bucket
Solution: Use separate chaining, often with a linked list, where the index of the array consists of a chain of values
At this point, we have our building blocks, so let's go ahead and implement the set
method. The method will:
- take the
key
passed - run it through the hash function, and
- 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]);
}
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 the value.
for (let keyVal of this._storage[idx]) {
if (keyVal[0] === 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
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];
}
}
}
That should about do it! Let's try it out.
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;
}
for (let keyVal of this._storage[idx]) {
if (keyVal[0] === key) {
return keyVal[1];
}
}
}
}
This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.
Top comments (1)
Good guide lots of useful information for interview prep.