Man! You are just amazing! I have coding interviews in a few days, and you just saved my ass. You have implemented almost all DS, and they are so neat and clean, the way it should be! Thanks man!
Hi there, how do i search for the other same key? for example : HT.insertTable(99, "Jim"); HT.insertTable(99, "Tim"); how do i search for value "Tim"? cause if i search for key 99 it displays "Jim"
isEmpty can be implemented in a better way (O(1) as opposed to O(hashGroups)), You could create a variable that stores number of empty hashGroups. So, numEmptyHashGroups = hashGroups initially. On insert, decrement numEmptyHashGroups if it is the first node in the list. Similarly when removing the item, increment numEmptyHashGroups if it is the last value. Implementation of isEmpty will become as simple as numEmptyHashGroups == hashGrorups. Also, in current implementation you don't need to calculate the sum, you could just return false if at any point the list is not empty. Aggregating the sum can cause overflow.
thanks a lot. But I think using C sytle array is bad practice. The books always say use vector: I mean instead of this: list table[hashGroups]; isn't this better ? : using listType = list; vector table; Maybe, I am wrong, what do you think ?
Using vector is less efficient than using stack-allocated arrays as allocating memory in heap is slower. This is just an example, but I guess when making a class you'd indeed use a vector so it's more flexible. Can't recall if stl uses Red-Black tree for unordered_map tho.
Great video! Especially in covering effective collision handling, since not all tutorials do that very well. FWIW, 1:25 should be "what it looks like" or just "how it looks". "Like" sounds a bit redundant if you pair it with "How". One of the best tutorials on this topic in any case.
Thanks man, I have searched google, youtube, your video is the only source of hashmap implementation in c++. But one thing is that as we are using for loops in this code, it doesnot mean O(1) operations, right?
for loop gets used when there is collision and the worst case time complexity for collision is actually O(n), i.e. when all the values have collided. It would be O(logn) if implemented with an AVL tree.
Just what I was looking for. Amazing explanation. However, I can see that some beginners can get confused because of list, iterators and i{}. Nonetheless, it was a great video. PS: That keypresses and mouse clicks were hypnotic.
I was actually afraid that people would not like the typing sound and it would annoy them. But people seem to love it. I have another video coming out on Wednesday at 5:30 CST with more typing sounds. :D
@@austintaylor5372 int x declares x but doesn't initialise it. By that I mean that 'x' has junk in it, and by junk I mean it can have anything in it. int x{} default-initialises x to int's default value, that being 0. Iterators are like pointers in a sense, except they are used on collections and there are several types of them. They allow you to iterate over a collection and, in some cases (non-const iterators), modify the contents of that collection. Hope this helped.
Very helpful! I do have one question tho: you are saying in the beginning, that this would be hashing with seperate chaining. But wouldnt you append the value to the list of the other ones of the same hash value instead of replacing them in seperate chaining? Line 46 in your code. Or am i missing something there?
didn't understood why list::erase() can lead to segfault....even if last item is erased it will simply return container end ....how getting next itr position can lead to error?
I really love this. One thing I am not able to understand is why the code will not work if you don't put a "&" operator in front of cell = hashFunction(key). Can anybody explain it to me?
@@CodingJesus I can't believe you replied!! I didn't know the concept of references in c++ so I didn't understand why you used a & operator in front of a variable. Well I understood it now but I do have a few doubts. Is this method faster than using a plain vectors? What is the best scenario in which I should use this?
@@aryanparekh9314 You should use references when you want to change the value stored in the hash-table. Not aliasing the hash-table element with a reference will lead to you crating a copy of it. When you go to assign cell = something, it won't be stored in the hashtable, because 'cell' isn't a reference.
Hi , I learned a lot from this video but i did not understand why you defined variable and then placed a curly bracket after it. Why not just leave it blank. thanks!
i have a c++ project of storing 500 books from a .txt file in which there are details about the author,ISBN ,title, etc. and I have to find a convenient data structure for that to do insertion, deletion,searching can you help me out plz?
For the private member variable list hashTable, this is just a containter that is in an index of the array right? If so, are we able to use a vector or a linked list instead?
Hi Jesus, Does Separate changing mean Open addressing? What is the point of checking HT isempty( )or not at start of int main? We are creating Ht from start so of course it will be empty before inserting....
bItr points to key-value pair. bItr->first points to the key. bItr->second points to the value. We are checking whether the key exists, so we need to use bItr->first
@@alexvallex5487 maybe wrong dash, maybe wrong 'bigger then'-sign - u can use (*variablenameBeforeArrow).variableAfterArrow instead, its just a different representation of the same concept
I gave it a try, seems to work, if its the best piece of code - i dont think so. string HashTable::searchTable(int key){ int hashValue = hashFunction(key); auto& cell = table[hashValue]; auto bItr = begin(cell); bool keyExists = false; string searchValue; for (; bItr != end(cell); bItr++) { if (bItr->first == key) { keyExists = true; searchValue = bItr->second; cout
@@CodingJesus And one more thing is here we use separate chaining method. But when we insert, if there's a conflict. You just erase the original value but not adding the value into next node of list. So maybe it is wrong here?
amazing explanation thanks a lot but tell me why use & in auto& cell = table [hashvalue]; to give you the address of each hash value or what explain with my all respect
We take a reference to that have because we want to alter it, as opposed to altering a copy of it. Hastable[hashKey] returns a reference to the item being held at that index.
thanks for the video, but i think in worst case time complexity for searching the value be O(n) in your code which is violating the concept of hash table , if yes ,can it be improved for getting the value in constant time.
I don't understand the purpose of the for loop for the insert function if you're just replacing the value. Why would you need to iterate the cell if you just look at the first value of cell to see if it's the key and if it is replace the second value with the value. Seems unnecessary to me.
Audio volume needs to be at least 30% higher, better 40%. It's easy for us to turn the volume lower to acceptable levels, but it's impossible for us to go beyond 100% on both youtube and system volume. Lowering the volume always allows to reach acceptable levels, but the opposite doesn't.
Man! You are just amazing! I have coding interviews in a few days, and you just saved my ass. You have implemented almost all DS, and they are so neat and clean, the way it should be! Thanks man!
what did u do
@@noemanakram6581 he is the ceo of google now
@@Snake-ez1kl LMAO
Did you pass?
@@goofygrass yes been three years now.
love the perfection. the way you type and your explanation
thanks
Thank you!! This was so helpful. Supplementing my classes with your videos now - my teacher only reads from the book.
This was incredibly helpful. You explain each step clearly which is hard to find! Thank you:)
Very useful and clear video, thank you for helping me understand hash tables better.
No problemo
super amazing work man, props! you're a great programmer and teacher.
This is actually ASMR lol
Thanks guy! Very nice tutorial. Here's my go at the search function:
string HashTable::searchTable(int key) {
int hashValue = hashFunction(key);
auto& cell = table[hashValue];
auto bItr = begin(cell);
bool keyExists = false;
for (; bItr != end(cell); bItr++) {
if (bItr->first == key) {
keyExists = true;
return bItr->second;
}
}
if (!keyExists)
return "Result Not Found";
}
Hi there, how do i search for the other same key?
for example :
HT.insertTable(99, "Jim");
HT.insertTable(99, "Tim");
how do i search for value "Tim"? cause if i search for key 99 it displays "Jim"
@@ilanogaming5034 you can't have 2 different values with the same key, that's why your value gets overridden
in isEmpty, you dont need a sum. Just return true whenever the size is non zero in the loop, it will on average save a lot of execution time
Yeah, others have brought it up below. That's a good approach.
@@CodingJesus oof, didn't catch that. Well, great video anyways! Thanks for it.
isEmpty can be implemented in a better way (O(1) as opposed to O(hashGroups)), You could create a variable that stores number of empty hashGroups. So, numEmptyHashGroups = hashGroups initially. On insert, decrement numEmptyHashGroups if it is the first node in the list. Similarly when removing the item, increment numEmptyHashGroups if it is the last value. Implementation of isEmpty will become as simple as numEmptyHashGroups == hashGrorups. Also, in current implementation you don't need to calculate the sum, you could just return false if at any point the list is not empty. Aggregating the sum can cause overflow.
You can keep count of the amount of items successfully added and removed. Call isEmpty() will check whether itemCount is 0 or not.
The keyboard sounds like asmr. relaxing..
thanks a lot. But I think using C sytle array is bad practice. The books always say use vector:
I mean instead of this: list table[hashGroups];
isn't this better ? : using listType = list;
vector table;
Maybe, I am wrong, what do you think ?
std::vector will be slower than C style array's.
Using vector is less efficient than using stack-allocated arrays as allocating memory in heap is slower. This is just an example, but I guess when making a class you'd indeed use a vector so it's more flexible. Can't recall if stl uses Red-Black tree for unordered_map tho.
That was a neat explanantion!
thanks a lot, man!
welcome
thanks for helping me write my first working hash function. test on this tomorrow in 12 hours...
Best of luck!
Thank you, this was quite helpful, and quite catchy too XD. Keep up the good work, and all the very best
Thanks
@@CodingJesus welcome
amazing lecture man. crystal clear.
Thanks, please consider subscribing for more.
Great video! Especially in covering effective collision handling, since not all tutorials do that very well. FWIW, 1:25 should be "what it looks like" or just "how it looks". "Like" sounds a bit redundant if you pair it with "How". One of the best tutorials on this topic in any case.
Muito obrigado Jesus Cristo dos códigos, você é o cara, a main.
Great tutorial, this will help me for my interview
One question: can we use this hash class in std::unordered_set ?
Great video, thanks!!
You would not have to go over all the table to check if is empty, if you found one element - return false.
What keyboard are you using? It sounds good!
Why do you put return at the end of functions that have void as their return value?
Thanks man, I have searched google, youtube, your video is the only source of hashmap implementation in c++. But one thing is that as we are using for loops in this code, it doesnot mean O(1) operations, right?
for loop gets used when there is collision and the worst case time complexity for collision is actually O(n), i.e. when all the values have collided. It would be O(logn) if implemented with an AVL tree.
Just what I was looking for. Amazing explanation. However, I can see that some beginners can get confused because of list, iterators and i{}. Nonetheless, it was a great video.
PS: That keypresses and mouse clicks were hypnotic.
I was actually afraid that people would not like the typing sound and it would annoy them. But people seem to love it. I have another video coming out on Wednesday at 5:30 CST with more typing sounds. :D
Yeah could you explain the i{} and how he did the iterator. I'm also trying to learn c++ i only code in c#
@@austintaylor5372 int x declares x but doesn't initialise it. By that I mean that 'x' has junk in it, and by junk I mean it can have anything in it. int x{} default-initialises x to int's default value, that being 0.
Iterators are like pointers in a sense, except they are used on collections and there are several types of them. They allow you to iterate over a collection and, in some cases (non-const iterators), modify the contents of that collection. Hope this helped.
@@CodingJesus yeah that makes alot of sense thank you :)
Very helpful! I do have one question tho: you are saying in the beginning, that this would be hashing with seperate chaining. But wouldnt you append the value to the list of the other ones of the same hash value instead of replacing them in seperate chaining? Line 46 in your code. Or am i missing something there?
Thank u this question was asked in sprinklr interview
didn't understood why list::erase() can lead to segfault....even if last item is erased it will simply return container end ....how getting next itr position can lead to error?
Umm... How do you overcome Hash Collision?
I can't find it. How to overcome Hash Collision in this code
Just using a list. Cell.emplace_back(key, value)
is this code also considers the collison problem?
I really love this. One thing I am not able to understand is why the code will not work if you don't put a "&" operator in front of cell = hashFunction(key). Can anybody explain it to me?
What do you mean? Paste the code into Godbolt and share the generated link with me
@@CodingJesus I can't believe you replied!! I didn't know the concept of references in c++ so I didn't understand why you used a & operator in front of a variable. Well I understood it now but I do have a few doubts. Is this method faster than using a plain vectors? What is the best scenario in which I should use this?
@@aryanparekh9314 I still don't know what part of the video you're talking about.
@@CodingJesus Okay I'm sorry for being unclear, here is the time stamp 6:52 line:40
When you used cell as a reference
@@aryanparekh9314 You should use references when you want to change the value stored in the hash-table. Not aliasing the hash-table element with a reference will lead to you crating a copy of it. When you go to assign cell = something, it won't be stored in the hashtable, because 'cell' isn't a reference.
Hi ,
I learned a lot from this video but i did not understand why you defined variable and then placed a curly bracket after it. Why not just leave it blank. thanks!
Google the difference between defining a variable and initializing it.
Thanks so much for this, it helped a lot!
Glad it helped! Please consider subscribing for more help :D
Why are you using {} instead of = in the variables initialization? To make your code harder to comprehend?
better convention for OOP , it's recommended to use it this way by the standard because it reduce time complexity by avoiding useless operation
@
>> recommended to use it this way by the standard >because it reduce time complexity by avoiding useless operation
@ please please tell more or put a link when to use variable{} for initialization or @Coding Jesus please explain.
i have a c++ project of storing 500 books from a .txt file in which there are details about the author,ISBN ,title, etc. and I have to find a convenient data structure for that to do insertion, deletion,searching can you help me out plz?
did you pass?
Did you not implement SearchTable function?
Very good explanation!! what IDE is that?
Visual Studio Code
@@CodingJesus thanks
@ welcome
Great Video !!
Great Job :D
Question: Do you actually need the keyExists bool? Couldn't you just return in the for loop if the key exists after replacing it?
this is a great video
Thank you! Make sure to check out my other videos.
should have added a key-value pair that gets the same hash!
excellent work though!
great tutorial! I encountered a problem for using the function emplace_back(), IDE says it "no member named 'emplace_back' in 'std::__1::list
May need to tell your compiler to use c++11
For the private member variable list hashTable, this is just a containter that is in an index of the array right? If so, are we able to use a vector or a linked list instead?
We want to have a set number of groupings, hence we want a container that cannot be resized. An array communicates that intent.
great video man! you explained amazing!!
(p.s. you forgot const on the print function)
how would I change this if I wanted each key to hold all of the different names instead of replacing the value
Since perfect hashing function is assumed, why use the for loops. Doesn't that make the time complexity greater than O(1)?
would you have used templates
what keyboard are you using ?!??!?!
this guy is doing god's work
what is iterator ? im almost at fourth cicle and still without recognise some words
Hi Jesus, Does Separate changing mean Open addressing? What is the point of checking HT isempty( )or not at start of int main? We are creating Ht from start so of course it will be empty before inserting....
Just checking whether IsEmpty is coded correctly. And yes, separate chaining and open addressing are different.
is the video completely corrupted for anyone else?
Did he forget to write the code for the search function?
in line 44 , dont you need to check if Bitr->first == hashFunction(key) instead of key?
bItr points to key-value pair. bItr->first points to the key. bItr->second points to the value. We are checking whether the key exists, so we need to use bItr->first
coding jesus man that name does suit you well
awesome video
What's that IDE he's using?
P.S. Kinda new to C++
thats visual studio code (VSC)
@@jamespolaroid4856 do you know why my VSC does not like pointers? everytime i use -> it breaks
@@alexvallex5487 maybe wrong dash, maybe wrong 'bigger then'-sign - u can use (*variablenameBeforeArrow).variableAfterArrow instead, its just a different representation of the same concept
@@jamespolaroid4856 thank youu
display function?? i didnt see it
nice, video. Wish I had contrast, so I can see () {} [] better.
how can I implement the searchTable function?
I gave it a try, seems to work, if its the best piece of code - i dont think so.
string HashTable::searchTable(int key){
int hashValue = hashFunction(key);
auto& cell = table[hashValue];
auto bItr = begin(cell);
bool keyExists = false;
string searchValue;
for (; bItr != end(cell); bItr++) {
if (bItr->first == key) {
keyExists = true;
searchValue = bItr->second;
cout
Lmao this guy is called Coding Jesus
great video! Thank you!
welcome
hi, could I know if you miss writing the search function
Yes, I left it as homework for you in particular. But only for you, not for anyone else.
@@CodingJesus And one more thing is here we use separate chaining method. But when we insert, if there's a conflict. You just erase the original value but not adding the value into next node of list. So maybe it is wrong here?
bruh I copy line by line and it doesn't run at all.... tells me there's a lot of errors... I don't understand why it doesn't work..
can anyone tell me which IDE is this?
can anyone please tell me what is that sum followed by { }.
Brace initialization. It sets sum to 0. Please consider subscribing for more content!
Great tutorial!
thx
Thank you @Coding Jesus
How do you implement an iterator class for this? anyone got ideas?
great video!
amazing explanation thanks a lot
but tell me why use & in auto& cell = table [hashvalue];
to give you the address of each hash value or what explain with my all respect
We take a reference to that have because we want to alter it, as opposed to altering a copy of it. Hastable[hashKey] returns a reference to the item being held at that index.
Hey u ever get a gpu?
thanks for the video, but i think in worst case time complexity for searching the value be O(n) in your code which is violating the concept of hash table , if yes ,can it be improved for getting the value in constant time.
I have the same setup as you! VS code with ubuntu subsytem terminal
no string searchTable(int key) function?
Nope, that's homework for you. ;)
@@CodingJesus lol,
You sound like me. I just noticed the difference in signatures. Great work and discussion.
@@telecastersanity Subscribe if you want to see more. What would you be interested in? Concurrent queue?
Nice n quick...thanks
So no one is going to talk bout that double intro?
Haahaha, I'll crop the intro out. I mentioned in the description to start at 0:16
Good content tho..keep it up bro.
Man, can you make videos like this for java...?
hola buenas tu video me sirvio mucho, pero me gustaria saber como implementar un sistema de busqueda atravez de la key
For remove function, Doesn't this work?
value_at_index.remove_if([&](std::pair capture) -> bool { if(capture.first == key){return true;} else{return false;} });
Why don't you try it out and test for yourself? That's the essence of learning :)
Thank you Jesus
Should've zoomed in the screen a little bit......
plz attach the source file for helping out
where is the search function?
It's homework. If you subscribe I may consider making a data structure with ONLY search ability, nothing else. Not even insert.
now next tutorial CPP CON 17: ua-cam.com/video/ncHmEUmJZf4/v-deo.html
can someone code it in c++ ?
Your teaching is amazing, but the Tabla that you are playing while typing is somewhat irritating.
I don't understand the purpose of the for loop for the insert function if you're just replacing the value. Why would you need to iterate the cell if you just look at the first value of cell to see if it's the key and if it is replace the second value with the value. Seems unnecessary to me.
Same with the remove function* Unless you are using chaining what is the point of the for loop?
Audio volume needs to be at least 30% higher, better 40%. It's easy for us to turn the volume lower to acceptable levels, but it's impossible for us to go beyond 100% on both youtube and system volume. Lowering the volume always allows to reach acceptable levels, but the opposite doesn't.
You Didn't Implemented the SearchTable method😄
Is that your real name?
Yes, my first name is Coding and my last name is Jesus
Can we get the source code?
No. The point is to watch and learn, not watch and copy-and-paste.
Awesome.
hello sir,
in line 86 the second operand (
csrc.nist.gov/csrc/media/publications/fips/180/3/archive/2008-10-31/documents/fips180-3_final.pdf
use #include instead of #include
Not see clearly plz zoom the screen
Amen
Big thanks :))
Thanks so much!!
rip Rick
rip Bob
Amazing
ikr
you like pressing buttons dont you