How to Implement a Hash Table in JavaScript
Vložit
- čas přidán 22. 12. 2019
- Learn how a map/dictionary/hash table works underneath the hood by implementing your own version in JavaScript.
Code: gist.github.com/benawad/7a71d...
----
Follow me online: voidpet.com/benawad
#benawad - Věda a technologie
I was asked to create a hash table ( in js ) from scratch in an interview and I bombed it. Thanks for the vid. 👍
It had to be Google、Facebook、Amazon interview i guess XD
Some non-JS developer comes as a JS interviewer and ask all these questions about the hash map and hash table and create a big deal out of it. Basically, the JS object serves the purpose of the hash table and there is a high chance that most of the JS developers never heard about the hash map.
Really bro
I like your videos Ben, unique content and always questioning how things are made.
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
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!
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]];
}
Jep. Been couple of weeks now, and not too many people who noticed this, it seems.
Good catch idk how I forgot about this
Yessss! More data structures and algorithm videos please 🙏🙏🙏🙏🙏🙏🙏🙏🙏
great tip on Quokka. It feels like a jupyter notebook or something for js in vscode. I'm loving it.
Great job on a sample implementation of a hashtable in JS!
Great video, thanks. I would love a video comparing different hash functions.
Damn ben, never really watched you for your tutorials but damn, this was clean
Great video as always Ben!!
I finally understood hash tables. thank you
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
very nice one, funfact, in js actually object is base, array is derived from object, so actually arrays are hashmap with number keys.
oh really, that's interesting, so how does the object work underneath?
that I'm not sure, but all bit at the metal. but on language itself the base is object, do not quote me but firefox engine has a native array implementation for performance afaik.
Entering typeof([ ]) in the console of all my browsers confirms your claim. Have been using the object as hashtable in Javascript since day one and never felt the necessity of the implementing one. I believe the dense array is the way to go when possible cuz it's just a wrapper for a C array.
Pretty sure object derives from an array, and all arrays are actually fixed in size, so the object just computes indexes with a hash function
In others langages(like java): object use hash table internally but with the V8 engine it use another technique. And for optimization purpose object are transformed in array (pre "turbofan" at least, not sure with the new "turbofan" compiler)
Really enjoyed this!
This is a really good guide. From this I was also able to write a function that reassigns values.
dude this is golden, appreciated that
watching you code is fun
Hey Ben, do you have other tutorials for other Data Structures? Man you explained this very nicely and easily
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.
need to be careful about recursion in that case
Very cool stuff. Love your channel :)
Thanks!
That's very clear ! Thanks buddy
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 CZcams about it, best regards...
Awesome video.Thank you so much.
Very cool video, thanks!
2001 isnt prime, cuz 2+0+0+1 % 3 = 0, so u could divide it by 3
I love the explanation. It would be great if you could give an example where this would be useful , because I can’t come up with one by myself
It's useful as a teaching example of a basic hashtable implementation
What he said, because Objects in JS already do this by default and are faster than the manual implementation. This is just an example of how it works underneath the hood, which is very fascinating. Btw, this is probably way more useful in lower-level languages, especailly those without an existing hashmap object.
Thank you, Ben!!! :-)
Yes !!! DS thanks Ben .👍
Good one Ben
You mention that a hash table (object) is implemented as an array, but it was originally the other way around -- the first implementation of javascript lacked "real" arrays and implemented them by adding a "length" method to an object that used number converted to strings as keys. Not sure about the underlying implementation though...
Also, I don't think this is technically a hash function as the hashStringToInt function's run time is dependent upon string length and not constant.
I want to add, however, that I recently discovered your channel and I really like the stuff you're doing here! Keep up the good work!
Why does the hash function have to be constant? How to achieve this?
@@31redorange08 it doesn't.
Hash tables are not constant time with respect to key length only with respect to number of elements.
@@marcossidoruk8033 I know. I just wanted to bust their "knowledge" in a nonconfrontational way. 🙂
Good. But keep in mind that Hash tables despite perform fast with insertion, deletion and fetching, are really bad for searching wise operations, in the later case is better to use binary search tree structures.
Other issue that comes to mind is that choosing odd primes for multiplier, in order to reduce collisions, are better suited for English words as is empirically taken with that language in mind.
Great video!
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.
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.
good catch
Bad catch. There will either be an array or undefined, never 0 or an empty string.
redorange Check again. He is checking if the value is set for a given key. The value could be anything including 0 or an empty string not just an array or undefined.
What's wrong with having a 0 or empty string? Maybe I'm mistaken for reasons, but if I stored a 0 or '', i'd prefer for someone to NOT overwrite it because they feel it shouldn't exist. can anyone explain? they're legal values, after all, though they may not make much sense without context. we should PROTECT our values :D not destroy them
ok never mind I get it now, took a moment :D
do we need to create this hashtable implementation on our own or there is efficient library/ implementatiom existed already? just want to know the best practices
Small improvement suggestion. The `setItem` function should probably take into account of update on same key (i.e. when an item with the same key already exists). After that, `this.numItems++` should only happen when a new key is inserted. Otherwise we can do `setItem("sameKey",123)` multiple times and keep increasing the hash table when it doesn't need to be bigger.
Another improvement is to use a linked list instead of a generic array for the "bucket" in each indices. This will become useful when there is a need to delete items from the hashmap (which wasn't part of this implementation), since linked-list deletion is O(1).
I want to point out that this was an excellent intro to hash tables by Ben Awad, and he implemented one of the solutions for hash collision (Separate Chaining), but there are other strategies that can be used. I found GeeksForGeeks Hashing Set 1~3 videos helpful for learning about different strategies if you are curious. You can find them on CZcams.
In this implementation, we used an array to generate a hash value, so our performance is directly proportional to the length of key name we chose?
thanks for this course
Thank you so much this video is benefitfull i appreciate it .
Inside the loop in your hashStringtoInt function should it be hash += (13*hash*s.charCodeat(i))%tableSize ?? Your solution has hash = (....) instead of hash+= (.....)
Yes, his bad, because rn it only hashes the last character
thanks for sharing!
Thanks man. 🙏🏽
This is cool and all but how would you use this in a real word app? Would I persist this to a DB?
You can use //? to show the output at the end of the line number instead of console.log
I think that's only in the premium version
what extension or shortcut did you use to auto input ;
Is there a more optimized way to resize the hash table? 🤔
Hi , I currently using react hooks is there any way that use call back after setting the state using useState hook
what do you mean?
great video... also what is your vs code's font name? I'd like to set for mine too...
At 19:50, why did you change to foreach instead of using a for loop? Was it for readability, or is there a deeper reason for this choice?
This is good.
This is crazy!!! ❤❤❤❤
at 20:40 what command did you do to copy the line like that?
Very nice video
sometimes I got the impression that ben is always laughing on the inside. hahaha.
I am dancing now 😎, because I know the error that happens as you type it. 21:00, Great content buddy. Subscribed.
Thank you!
which extension is he using for this auto onscreen console
there is a bug in hashStringToInt func's logic : in For loop you're re-assigning Hash variable every circle. Someone suggested in the comment section to use += which is right but we also need to move the modulus out of the loop, otherwise we go outside of the array's length so
And what's the bug?
My DS class got so easy
. Js can get quite complicated. But it work
you can also do ```person['lastName'] //?``` and get the same result as the console.log
premium?
@@ugurcoskun5195 I didnt realize before, but yes, its available in pro version. I will recommend Pro version, it has useful features.
But why would you want to do this when we have Map?
Do you or does anyone know if places like Google will ask you to do this in an interview?
Nope
How high is ur monitor?
can you go through the other extensions you have installed in vs code? what's the one that shows you the green boxes on the left?
That’s just a visual extension for uncommitted/unsaved changes
@@kjl3080 what's it called?
@@Tonestire idk what that specific theme is called, but you should be able to find it in the extensions marketplace iirc
I have a dumb question. In some other languages like c#, if the array`s length is 10, but your hash function calculated the index to be 13 then how can you set value to that index because the index can only be from 0 to 9? Looks like in javascript the array is a dictionary right?
that's why we mod by the length of the array so we never get a number bigger
@@bawad Thanks! I did not noticed that.
3:55 well you can use string as an index there in JavaScript.
Do you know this? The way you assign the (arrow)-methods is equivalent to assigning via *this.getItem = expression* , which means its bound to the HashTable instance and not prototype. Means, each HashTable method will create new method instances, instead of those methods being instantiated once on prototype. That is the difference between the syntax-sugared *getItem(key) {}* and *getItem = (key) => {}* (ignoring the this context on arrow function). The former is on prototype, the later on instance. Does not make much difference here though, but good to know if you have a lot of instantiations of those types.
Thank you for explaining that
That means that in the second form (arrow) I can access the instance properties directly, like table instead of this.table, isn’t it?
@@mihaimanole2643 no, you can not because table is not a local variable. also when desugared. So you will still need this.
Thanks :)
Your hash function only takes the last char
This was super helpful. Small question about the time complexity. Since the resizing only occurs at a certain point, will the time complexity still remain O(n) at the worst? Great video though thank you.
This video was all over the place.
Although this was uploaded in 2019, I noticed something while using new Array(this.size), If the size of our array is 100 and add an item to 200 your array automatically increases to 201. Therefore, no need to resize the array.
If the new item has a collision, the size will not increase. Also, depending on which part of the video your referring to, he is not always just pushing items to the end, so again, your not increasing the size.
The way I would prefer to do it is to make a internal method getsize () and call it only if needed to avoid unnecessary computation.
1:27 , 2:55 Ctrl + Shift + P on Windows machine to get the menu to Start Quokka on Current File.
Seems to be a bug?
Your hush function will only be based on the last character of your string. Not a function of the entire string!
What you may want to do is create a running sum of your salt + charCodeAt(i)
Do you think someone will ever need to create their own hash table in JS like that? Because github/npm etc are full of somebody else's made hash tables
In the beginning, re-using existing modules is fine, but eventually it's good to understand what's happening under the hood. Building your own is the often best way to get there.
For example, after lightly using MVC frameworks I decided I needed to understand them better, so I built my own. It's nothing special and certainly nothing I'll put into production, but when I was done I had a full, solid grasp of the concepts and mechanics of MVC, as well as some of the tradeoffs/pitfalls involved in using the pattern.
@@candfsolutions indeed for self learning I guess this is ideal, probably these type of stuff you don't want to use in production just, unless you want to be responsible for maintaining it, bug fixing, and adding features
99.9999% of the time you won't need to implement your own hash table.
I've always used the one already implemented for me
is there a difference between obj.foo and obj['foo'] ?
No in terms of expected result. Yes if you are e.g, Trying to make a object key from the value of foo. obj.foo won't work but obj['foo'] will work.
The 2nd option allows for more property names possibilities with characters that wouldn't be allowed with the 1st option. Take for instance:
var obj = {'//bar': 'This property name is only possible with quotations'};
obj.//bar is not valid while obj['//bar'] is allowed.
@@ericlarson7740 ya... Thanks for a better clarification. :)
Under the hood its the same operation. But syntactically the former does not allow you to use space or other tokens, because it would be indistinguishable, so you have the later syntax, which is distinguishable.
@10:16 for lines 4 to 6, why would you want to use a for loop that runs i many times, to finally generate a single number (hash) at the end,
seems a bit unnecessary as lets say our string is "firstName" - all that matters is charCodeAt('e') (the last letter) and that determines our hash, all the other letters "firstNam" when run through the for loop, get overwritten by the last iteration.
Hey man, great video!
Just a question, what font are you using on VSCode? On Windows my fonts look really pixelated and ugly. Thanks!
I think I'm using the default one
Try ClearType or increasing your font size
How do you show console.log in real time?
Quippa I think
*quokka it’s not free
thanks
Subscribed
welcome :)
Noticed, there is probably a bug (did not test it, just from watching the video) with empty string passed as key, the length will be zero and so the returned int key will be 17, which is out of bounds of the initial table of length 3 :)
nice find!
@@bawad I like your interesst in understanding how things work. I also like to do stuff like that myself for fun and it helps understand things better and being more creative in finding solutions for problems. Especially, like in this case, when its actually part of language, but do it more *low level* (if that is the correct term here..) yourself. For example some ui & interaction rendered on canvas, including event handling - you can obviously not add event listeners to drawn objects natively on a canvas. Layouting system to arrange ui elements, etc.
Delicious :)
Can someone pls explain the difference between a hash map and a hash table ?
Here's the way I understand it:
Hash Table: what we call the concept in Computer Science
Hash Map: what it is called in Java
Hash Set (HashSet): the case where we only care about the unique keys (or you can see it as a Hash Table where we ignore the values, we just want to know what is the set of unique keys)
Or simply,
Hash Table (CS) = HashMap (Java) = Dictionary (Python)
Hash Set (CS) = HashSet (Java) = Set (Python)
@@obetreyes9187 thank you very much
I laugh so LOUD after he says to himself at 22:13 * Oh yeah I`m just a NOOB *, but I was crying inside because I have no idea what was happening and needed to pause while(myUnderstanding < 1)
I don't understand... why are we making these with Arrays again and not objects?
Me too, like, why not just use objects as shown in the beginning of the vídeo? Why do all that extra work?
Not that anybody asked, but I always watch your videos at 2x speed. Cool stuff though :) I would have liked a few sentences about why and when to use something like this or is it just a fun little exercise.
the load factor of HashMap in Java is 0.75 :)
Java or JS?
rick ross It’s very handy to peek the implementation of HashMap from Java then the one from V8 or other JavaScript engine. Which, of course, will be not implemented in JavaScript, but most likely in C++.
Google better not ask me to code one of these entirely from scratch in my phone screen tomorrow, because I guarantee I can't do it
The problem with this data structure courses is that no one like to take deep dive in more hard structures like trees(but no binary or n-ary trees) etc.. and more complicated alghortims that are used in AI and are tightly connected with trees and similar structures.
haha . yea
@@Rei-m3g Metallicaaaaaa
or you could use a map
I miss the old Ben
We now know why you had to wear glasses
Why use a hash when you can use an object?
I guess it's just to show how it works under the hood.
@@jeromesnail but actually which one is used more often??
What do you mean by “spreading out the keys” ?you’ll have to excuse me im a dummy
My bookmarks:
5:48
or… and mark my words…
let table;
table[“key”] = value;
Why would you need a hashtable in Javascript when you have JSON?
I wouldn't actually use this, it's more for learning purposes