How to Implement a Hash Table in JavaScript

Learn how a map/dictionary/hash table works underneath the hood by implementing your own version in JavaScript.

​
----
#benawad

[kzakaria]

i actually like this kind of videos more than frameworks, being self taught always feels like im missing on cs fundamentals even though i can set up graphql with the newest hip frontend framework LOL.
keep em coming ben, appreciate the great work

[Akshatgiri]

I was asked to create a hash table ( in js ) from scratch in an interview and I bombed it. Thanks for the vid. 👍

[hnasr]

I like your videos Ben, unique content and always questioning how things are made.

[lsamax]

when you call a setItem again with same key, the output will like as [[["firstName", "bob"], ["firstName", "sam"]]],
after that, you call the getItem will get "bob", cus you just return the first element in table.
so, you need to adjust the setItem method as below (O(n)):
if (this.table[idx]) {
const item = this.table[idx].find(x => x[0] === key);

if (item) {
item[1] = value;
} else {
this.table[idx].push([key, value]);
}
} else {
this.table[idx] = [[key, value]];
}

[RandomLifter]

great tip on Quokka. It feels like a jupyter notebook or something for js in vscode. I'm loving it.

[stephenyin]

Amazing video! I use dict/object/hashtable a lot in my daily programming, but never have a thought how it works. This video just gives me a great intro of the principle behind the hashtable under the hood! Keep working Ben! You should deserved to have millions of subscribers!

[Jason_Lucero]

Damn ben, never really watched you for your tutorials but damn, this was clean

[IlhanNegis]

very nice one, funfact, in js actually object is base, array is derived from object, so actually arrays are hashmap with number keys.

[bits]

Nice tutorial. One note though: at 12:24 you should’ve checked if(this.table[idx] === undefined) instead because if someone has set the value to 0 or an empty string it will not evaluate to true.

[nstwin]

Yessss! More data structures and algorithm videos please 🙏🙏🙏🙏🙏🙏🙏🙏🙏

[purdysanchez]

Great job on a sample implementation of a hashtable in JS!

[lukehatcher]

Great video. I implemented a bottom threshold where if the table is less than .25% full, create a new table of half the length and rehash

[YaohanChen]

One way to simplify resize() is to just save the current table in a variable, assign this.table to the resized one, and then call setItem() for all the pairs in the old table.

[MrREALball]

2001 isnt prime, cuz 2+0+0+1 % 3 = 0, so u could divide it by 3

[tajpouria]

I suggest you to make a series about functional programming pattern in TS/JS. That's one of the most popular concepts that's not any proper content on YouTube about it, best regards...

[ditoorkodashvili]

Correct me if I am wrong but the way the setItem is implemented you may get a duplicate keys, because you are not replacing a pair if the key already exists in the array.

[RomanWaves]

great breakdown, thanks a lot! i have one question though... at 8:10 you modulo each time in the for loop, shouldnt it be done just once, after the hash was run through all loops
[for loop (hash= hash*charCodeAt(i) )] % tableLength ?
In other words, after the loop modulo through tableLength just once ? or am i missing something here ?

Edit: ahh it doesnt matter, right, since modulo just returns a devision "remainer", so either you do it each loop or just once, the result should be the same.

[MachiriReviews]

This is a really good guide. From this I was also able to write a function that reassigns values.

[JaspreetSingh-eqyk]

Inside the loop in your hashStringtoInt function should it be hash += ?? Your solution has hash = (....) instead of hash+=

[TadesseDev]

I am dancing now 😎, because I know the error that happens as you type it. 21:00, Great content buddy. Subscribed.