Simple Explanation of HashMap, HashSet, ArrayLists and Big O: O(n), O(1)
ฝัง
- เผยแพร่เมื่อ 14 ต.ค. 2024
- An explanation of algorithm growth rates (Big O) and different collection types: HashMap, HashTable, and ArrayList. In this video, I show how ArrayList fetch and insert at the beginning operations have O(n) growth rate performance, while the add, remove, contains, and size operations of a HashSet/HashMap have a more preferable constant, or O(1) performance. I explain how this works: through HashCodes, and what a hash code is. I perform a live example by showing a magnet collection, stored in a theoretical array, versus stored in a HashMap.
Hashcode Details from this video example:
New Zealand :: -244247871
Queens :: -1864844631
Isle of Man :: 449363438
London :: -2013264328
Coventry :: -287223480
Rio :: 82168
Monterrey :: 702301905
Peru :: 2483992
Zurich :: -1606791497
Sydney :: -1803913660
R: 82
i: 105
o: 111
Space 0 :: -2013264328 :: -1819295312
Space 1 :: -1819295312 :: -1625326296
Space 2 :: -1625326296 :: -1431357280
Space 3 :: -1431357280 :: -1237388264
Space 4 :: -1237388264 :: -1043419248
Space 5 :: -1043419248 :: -849450232
Space 6 :: -849450232 :: -655481216
Space 7 :: -655481216 :: -461512200
Space 8 :: -461512200 :: -267543184
Space 9 :: -267543184 :: -73574168
Space 10 :: -73574168 :: 120394848
Space 11 :: 120394848 :: 314363864
Space 12 :: 314363864 :: 508332880
Space 13 :: 508332880 :: 702301896
Source code is freely available on GitHub: github.com/dis...
This video is part of a playlist on Microservices and Spring Boot with IntelliJ IDEA: • IntelliJ IDEA, Git, Gi...
I have scoured the internet and let me tell you that this example is the most accessible, thoroughly explained, and context provided / derived answer I have found on this topic. If the other videos on this channel are in the same ballpark, then I think I found the best edu source for me on coding concepts. Thank you so much for this well put together video.
Wow! This is one of the nicest compliments I've received on my channel. Thanks so much for your feedback! That helps me to improve future videos. I encourage you to check out my channel and let me know what you think of them.
I hope you're building something amazing! If so, let me know!
The intelligent thinking that has laid all the groundwork for computing is simply amazing.
I absolutely agree. Computing is based on many generations of compound knowledge.
One of the best explanations of hash map computing :) love it. Thank you
Thanks! It's a great concept, and it's easy to explain... at least, I think so.
This is the 5th video today I am watching to understand time complexities and somehow none of the other videos explained these details in such a simplified way. I have been following you for a long time, your videos have been helping me a lot with the topics that are not explained easily by the rest of the internet. A big big thanks to you for grasping all the concepts correctly and then explaining them to us in such an amazing way.
Thanks so much! I really appreciate the feedback!
This was one of my favorite videos to record.
I ended up making several more videos about Big O algorithm growth as well. Let me know if I can help you find a topic of interest!
@@discospiff I am trying to master DSA to become a better programmer. I an currently exploring DS, will explore algorithms soon. I have an interview in 4 days that I really want to dominate. I will be exploring your channel for related topics
@@james00783 excellent, and great idea!
I have a playlist with Data Structures and Algorithms videos only. Have a look, and let me know if you have any questions. I'm happy to help!
Sounds great. Thanks. Any doubt, I'll let you know.
This video was fantastic, really cleared all of my doubts! (what really is a hashcode, difference between hashset and hashmap, how time complexity stays at O(1) always) Thank you very much! 👍
You're welcome! Thanks for watching. I'm happy to know that this video is doing what I had hoped it would do - make HashCode, HashMap, HashSet, and Big-O notation easier to understand.
A phenomenal video and explanation for these concepts. It is amazing how easy some concepts are using real-world objects. Thank you for sharing your knowledge with us.
Thanks for watching. This is one of my favorite videos!
Amazing video, explained it very well. I was scratching my head trying to grasp the concept, but now I understand it perfectly.
Excellent! Thanks for the feedback. That helps me to plan future videos. Several more on this topic coming soon!
Wow! wow! Excellent clarification!
Great introduction also to this video: "Static Hashing, Array vs Hash, Collisions, Overflow Chains, Rehash".
Thanks for sharing!
Thank you, your video made understanding HashMap runtime quick, easy, and enjoyable
I'm happy to hear that! It was a fun video to make.
One of the best explanations I saw. Thank you Sir.
Thanks! I really appreciate your feedback. It keeps me motivated to make more, and better, videos!
Very good and straight forward explanation without compromising on the whole concept! Thank you for making me appreciate hash tables!
Thanks! I'm glad you appreciate the video. Understanding Big O is fundamental to being an expert software architect.
Great peek into the depth of Collections jungle and all without a machete or a chopper! Bravo! The transient mustache and repeated mention of the "Bureau of Murderous Vehicles" were nice touches for making sure one's attention does not wander.
Thanks! That was my goal when I made the video: explain HashMaps and big O in a simple way, and do something subtle to keep attention. I'm glad you noticed!
The perfect video on Hashset. I found everything I was looking for. Thankyou sir!!
That's great to hear! This is one of my favorite videos. What we're you looking for? :)
@@discospiff I wanted to know why time complexity of hashset is that low and if it is because of hashcode then how does it function which I understood because of you so thankyou once again 🤜🤛
Very good demonstration of hashing and bucketing
Thanks for watching! I'm glad it helped.
It is definitely the best video about HashMaps I have found so far.
Thanks! I'm glad you found it. :)
I kept wondering why hashMap is so fast under neath it, i couldn't comprehend it just memorize it. Thank you mr brandan, you helped me.
Glad it helped! It's a very powerful concept, especially when growth of data is unpredictable. I think it makes a lot of sense once you understand it.
Love the layman explanation, Understood to the core … this kind of explanation rare in world of fancy jargon that i frequent always...
Thanks! That's really good feedback. I'm glad this video helped you to understand the big-O concept. It's very powerful!
great explanation , Thank you
Thanks! Big O is an important concept in programming for scalability, and this was one of my most fun videos to make. I'm glad you enjoyed it!
damn. i was not expecting to see a so good explanation. thank you very much for sharing this, the didacticism is spectacular! greetings from brazil.
Thanks! I appreciate your feedback. I enjoyed making this video.
I've been to Brazil, and I currently work with two people who live in Brazil!
Thanks for this video. The explanation technique is very nice and simple. I got the concepts very quickly. Keep sharing such videos 👍
Thanks! I really enjoyed making this video. Comments like yours give me the motivation I need to make more. Stay tuned!
Beyond brilliant. Thank you so much. I understand visually much better than by reading so this was really useful.
Thanks! I appreciate the feedback. When I planned this video, I thought visuals / analogy would be a good way to describe a complicated concept. ;)
one of the best explainations of hash map/set. seems like you made a lot of effort in making this over several weeks. thank you
I really enjoyed making the video. I appreciate your feedback... glad you found it helpful!
This is how you explain things. Brilliant! Thanks
Thanks for the feedback! I'm happy that you found the explanation helpful.
Became a fan of your lucid and practical explanations ! Thanks for sharing!
Excellent! I appreciate the feedback. If you keep watching, I'll keep making videos. :)
Very nice explanation, Great Video. Thank you
Thanks! What did you like about it?
Very helpful. Smooth explanation.
Glad it was helpful! It was a fun video to make.
Thank you Mr.Jones for this great video
You're welcome! Thanks for watching and commenting.
Thank you so much for this great video. Much appreciated your work.
Thanks! I'm glad you like it. This is one of my favorite videos... and understanding HashMap and hash codes is very important!
Very nice explanation, good use of visuals as well. Thanks!
Thanks! I think this subject is best explained visually, so it's great to hear that feedback. Did you notice my growing beard? ;)
Great explanation, but....nobody's going to talk about the gradually increasing facial hair throughout the whole video? Very fun addition!
LOL, thanks for noticing. I do that in all of my videos.
While it's not as obvious in low light, I shaved 5 times to make this video.
Amazing explanation
Thanks, I'm glad you enjoyed it! That's exactly what I was trying to achieve with this video.
Brilliant explanation!
The moustache took me by surprise tho!
Tusks for noticing. I shaved 5 times while recording this video, so there are 5 different transitions. Unfortunately, some are in low light, so it's hard to tell. :)
@@discospiff The full beard at the end looks the best, really suits you!
@@SamBebbington That's what my wife says. :) Naturally, I had to record the video on reverse order, which was a little tricky. Here's another one I did, where the lighting is a bit better: th-cam.com/video/l6O2oewO43g/w-d-xo.html
Thank you for the nice explanation Mr.Jones
Thanks! Do you have a favorite part?
Very excellent explanation sir. Thank you very much
Thanks for watching! I'm happy you found it useful.
thank you very much for this explanation
I'm glad it helped! What did you learn from it?
Love from india ,so easily explained
Thanks! That is wonderful feedback.
Thank you for a very educative tutorial)
Glad it was helpful! Big-O is one of my favorite topics: how you can get more growth with the same amount of hardware. It's also a neat intersection of math and computing, IMHO. So, for those who like programming, and not math, I think Big-O is a good way to show how they relate.
I am newbie in Big O topic, looking forward for more Big O tutorials)
Excellent. Here's one I made a month ago, which is the part 2 to the video you're watching: th-cam.com/video/mTpsxbplg14/w-d-xo.html
I know I made them out of order. :)
Thank you! This video explains A LOT.
I'm really happy to hear that feedback! That was my goal for this video.
thank you for your efforts, i loved your way of presentation so much.
Thanks! This is one of my favorites. :)
Great teaching with good examples. Loved it, Thank you :)
Thanks! This is one of my favorite videos. I enjoyed making it.
really good explanation and really good visualisation.
LOVE IT
Thanks! I think visualizations help understand complicated topics like Big-O notation and algorithms. I'm glad you liked it.
Great Video! Thank you very much!
Thanks! This is one of my favorites. ;)
Thank You! This was really helpful.
Thanks! I'm glad it helped. Understanding big-O is fundamental to understanding scalability, in my opinion.
best explanation everrrr
Thanks! I had a lot of fun making this video. I'm glad you found it useful!
Just a side note, at 2:55 you say we typically think worst case for big O notation. Big O notation states that the complexity is less than or equal to the expression given. Little o is strictly less than, Omega notation is greater than, and theta notation is equal to
Really good info! Thanks! I simplified things a bit in this video... and your explanation really helps.
Great explanation! I do have one question: how does multiple objects residing in the same bucket affects time complexity, if at all?
If I have a bucket with 100ths of objects, will it change things? Or will the buckets just get auto-split?
It will impact performance, yes. There are three options if multiple objects end up in the same bucket:
1) Put a List in that bucket, and store them in the list.
2) Put the objects in the next empty bucket.
3) Increase the capacity of the HashMap/HashSet, and reallocate buckets.
If you really had 100 objects in the same bucket, #3 is the most likely scenario.
This is a one time performance hit, during reallocation, where #1 and #2 would have a slight performance impact on every lookup and retrieval.
This is super good. Thank you for your time
I'm glad it helped! It was a fun video to make. Thanks for the comment!
Great Explanation.
Thanks! I really like hearing that feedback.
Thanks so much this was excellent.
Thanks! What did you like about the video?
one of the beautiful videos I have seen on this topic. But what happens when at a particular index we have two values??
Thanks! I'm glad you liked it. Is there anything specific you like about it? Your feedback helps me improve future videos.
I'll say, this is one of my favorite videos. ;)
Thanks, I feel like I know everything now:)
Thanks for the comment! I'm happy to know that this video has helped many people.
Amazing video!!
Thanks! It's one of my favorites.
Amazing video sir , you earned my subscribe.
That's great to hear! It's always nice to have another subscriber.
What did you like about the video?
I had a lot of fun making it. :)
Excellent!
Thanks! This is one of my favorite videos. :)
This is amazing, very very good work. Suscribed.
Excellent, I'm glad to like it! Thanks for watching.
Really really good stuff. Keep it up
I'm glad you found it. I'm thinking of making a video on Huffman encoding. Any other ideas... let me know! Thanks.
@@discospiff That sounds super interesting. Would for sure watch! :D
Your incredible.it was a great explanation.
Thanks! It was a fun video to make.
Thank you!
You're welcome! I'm glad you enjoyed it.
golden. Thank you boss
You're welcome! It was a fun video to make. Thanks for watching!
thank you great explanation!!!
Thanks! I'm glad you found it useful. I appreciate the comment.
@@discospiff cool mustache too my friend
@@Ash-so2sr Thanks. I had planned that one for while. I actually did it in 5 steps, but the ones with the magnets are hard to see, due to the lighting.
Great video!
Glad you enjoyed it. I enjoyed making it. :)
12:00 lost me here... I'm a visual person.
Can someone please type out the math in a programmatic way?
For example: This is the way I understood it
bucketNum = (hashcode - lowestPossibleHashcode) / Total number of buckets?
Is this correct? And how do you determine the lowest possible hashcode?
why is it 31? The method I would have came up with to determine the bucket would be to use floor(fmod(golden ratio * key's binary representation), 1) * number of buckets)
You got me thinking...
When I taught Data Structures and Algorithms, I recall the text mentioned that 31 just happened to work out well, as it is an odd prime number. I often wondered why 31. Maybe it has something to do with the number of letters in the alphabet? No, probably not, because uppercase and lowercase are treated differently. Plus there are special characters and symbols.
I never knew the answer, so I just searched. I found an interesting answer on Stack Overflow, which references the book Effective Java. Here it is:
"The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i
@@discospiff using the golden ratio probably wouldn't perform as well. But I bet I'd get a more even distribution. Maybe mine could have fewer collisions. Might test some day.
Can you paste the formula on how you are reaching 12th element ,,I'm finding it difficult if we subtract 2.1 billion with 450million how would we reach 2.5 billion can you please paste the formula with an example ,,but what an awesome way to teach the Order of () in a simple approach ,,kudos 👍🏻💯
ِِDoesn't it take O(logn) to find the span in which to put the new City in HashMap? I mean it would be a binary search to locate where should put the City by it's number.
Can anybody explain???
I tend to see log in Big-O when something recursive happens, like a Merge Sort. There's nothing recursive here; it's simply navigating directly to the location in the HashMap based on an algorithm, so that's O(1).
Things get a bit more complicated if you are inserting something, and there is already something in that spot, or when you have to reallocate the HashMap. But, if you're just inserting into a compartment where nothing else exists, you're not bothering the other elements, so it's a simple O(1).
Does that make sense? Or is my math incorrect? That's completely possible, too. :)
See this video for an explanation on Big-O that has a logarithm: th-cam.com/video/mTpsxbplg14/w-d-xo.html
Yo great video man
Thanks! I had a lot of fun making it. :)
why there is no HashList? o.O
Because a list would indicate an ordered collection. A hash would indicate but an ordered collection. That's why it's a set or a map.
I have the same magnets
Which ones? I have a lot of magnets. :)
Please put your mic on your body for a better production quality. Thank you.
I don't have a wireless mic, but since I'm doing more standup videos, I do want to get one!
hi beard work tho.
Thanks for noticing! I do that in several of my videos.
@@discospiff 😍