Hash Tables and Hash Functions

This computer science video describes the fundamental principles of the hash table data structure which allows for very fast insertion and retrieval of data. It covers commonly used hash algorithms for numeric and alphanumeric keys and summarises the objectives of a good hash function. Collision resolution is described, including open addressing techniques such as linear and quadratic probing, and closed addressing techniques such as chaining with a linked list.

Пікірлер: 1 500

  • @ryanbutterfield5038
    @ryanbutterfield50386 жыл бұрын

    You deserve my data structures professor's salary

  • @ComputerScienceLessons

    @ComputerScienceLessons

    6 жыл бұрын

    Why not send him a link to my channel :)

  • @annellysemathison2179

    @annellysemathison2179

    6 жыл бұрын

    mine too. serves no purpose

  • @tushar6742

    @tushar6742

    6 жыл бұрын

    Ha ha ha rofl

  • @SamKhan-kb3kg

    @SamKhan-kb3kg

    6 жыл бұрын

    Bang on, I was thinking the same :-)

  • @alexanderbergkvist9224

    @alexanderbergkvist9224

    6 жыл бұрын

    Haha x) Great video Kevin!

  • @ThePandaGuitar
    @ThePandaGuitar6 жыл бұрын

    Your voice sounds like a National Geographic documentary. Amazing explanation! Subscribed.

  • @Wow55579

    @Wow55579

    4 жыл бұрын

    This guy taught me ict when i was little trust me he sounds just like it

  • @joerj2460

    @joerj2460

    4 жыл бұрын

    ThePandaGuitar he’s my computer science teacher

  • @Peter-wm7fj

    @Peter-wm7fj

    3 жыл бұрын

    His British accent sounds so cool!

  • @rmapatipandey9217

    @rmapatipandey9217

    3 жыл бұрын

    😂😂😂😂😂😂😂

  • @coob404

    @coob404

    3 жыл бұрын

    he sounds a little bit like Tom Scott

  • @MartinBojmaliev
    @MartinBojmaliev6 жыл бұрын

    Before 14 minutes, I thought I will never understand Hash Tables. Good work and Thank you.

  • @ComputerScienceLessons

    @ComputerScienceLessons

    6 жыл бұрын

    They are actually quite simple in principal aren't they! Thanks for the comment.

  • @MartinBojmaliev

    @MartinBojmaliev

    6 жыл бұрын

    We got the reason here why they are used and how ... then it's very easy to use them in the right way !

  • @maybecrazy6934

    @maybecrazy6934

    3 жыл бұрын

    same here, this video is so cool.

  • @stefanshapkarov184

    @stefanshapkarov184

    Жыл бұрын

    Exactly sir, very good video indeed.

  • @atanasatanasov5119

    @atanasatanasov5119

    Жыл бұрын

    He is a life saver isn't he?!

  • @hotlinkster123
    @hotlinkster1233 жыл бұрын

    "indices are calculated from the data" thats literally all I needed to understand hash tables but surpirsingly I've never heard it once when people have mentioned them. Of course the bit on how to handle collisions was useful as well

  • @ComputerScienceLessons

    @ComputerScienceLessons

    3 жыл бұрын

    Exactly - that is the essence of a hash table - it's that simple. A basic understanding of how physical RAM works explains why one memory location can can be accessed just as quickly as any other. :)KD

  • @saikumar2385

    @saikumar2385

    Жыл бұрын

    Same for me

  • @das6109

    @das6109

    Жыл бұрын

    For me that part was intuitive, but I didn't understand how you would deal with that process creating multiple entries in the same index. This video was a big aha moment.

  • @Fandrir

    @Fandrir

    11 ай бұрын

    That is exactly what i thought. Exactly that one piece of information that i was missing. I have no idea why that was never made clear anywhere else i looked.

  • @joegarza8391
    @joegarza83913 жыл бұрын

    Years after, this video is still immensely valuable. This is what teaching is supposed to look like. Thank you for your amazing work!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    3 жыл бұрын

    Thank you. Crikey! that was uploaded nearly 5 years ago! :)KD

  • @ThunderAppeal

    @ThunderAppeal

    Жыл бұрын

    There are so many things wrong with this 'explanation' I'm not surprised that a half wit like you is impressed by this video. You defininetly have no idea what he is saying here. And he is talking utter nonsense.

  • @TheeSlickShady

    @TheeSlickShady

    Жыл бұрын

    This video So clear and easy to understand Thank you 🏆🏆🏆

  • @ThunderAppeal

    @ThunderAppeal

    Жыл бұрын

    @@TheeSlickShady You understood nothing so you can stop pretending.

  • @TheeSlickShady

    @TheeSlickShady

    Жыл бұрын

    @@ThunderAppeal haha got me!

  • @mrwess1927
    @mrwess19275 жыл бұрын

    This is what youtube is for. Just a clear explanation of interesting ideas. +1

  • @MisterWessells

    @MisterWessells

    2 жыл бұрын

    CAKE BAKING kzread.info/dash/bejne/dqdtrMquZaiXo6w.html&ab_channel=MisterWessells

  • @nap163020
    @nap1630202 ай бұрын

    Why did I spend all that money on an engineering degree, when all I needed was this channel!!!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    2 ай бұрын

    Thanks for the complement. University does have it's benefits :)KD

  • @tweedyburd007
    @tweedyburd007 Жыл бұрын

    You actually explain it as if we've never heard of the concept before! Something a lot of CS professors seem to not understand...

  • @utsabshrestha277
    @utsabshrestha2775 жыл бұрын

    Now this is a real education , so well described, you got the real tallent sir, really appreciating. You teaching approach can make anyone from zero to hero

  • @Lexoka
    @Lexoka5 жыл бұрын

    The video is very, very, very well made. That's a great deal of information in just under 14 minutes, and it is very clearly presented. You've more than earned a new subscriber.

  • @abdullahakram4942
    @abdullahakram49425 жыл бұрын

    you basically summarized 3 whole lectures of class into just 14 minutes. You're a life saver!

  • @kubamaruszczyk4043
    @kubamaruszczyk40435 жыл бұрын

    The best explanation I have encountered so far. Thank you!

  • @tinojaa6749
    @tinojaa6749 Жыл бұрын

    In a perfect world every teacher would be as clear as this guy :)

  • @ComputerScienceLessons

    @ComputerScienceLessons

    Жыл бұрын

    You are very kind :)KD

  • @samanthacrespo5745

    @samanthacrespo5745

    Жыл бұрын

    Agreed!

  • @kola844
    @kola8444 жыл бұрын

    Professors should just play videos like this at the start of class. Would improve student performance immensely.

  • @navidmohammadzadeh2141
    @navidmohammadzadeh21415 жыл бұрын

    I liked what you have prepared to introduce what is clearly hashing algorithms is. Of course, I would watch it again and again.

  • @BorlandC452
    @BorlandC4525 жыл бұрын

    I've been watching quite a few hash table videos lately. This is the best one I've come across.

  • @WaqasAhmadVlogs
    @WaqasAhmadVlogs5 жыл бұрын

    Holy shit! You made it sound like a piece of cake. I've been hearing about hash tables for so long and always thought it must be a rocket science until now. Hats off to you sir

  • @lucianojadur
    @lucianojadur3 жыл бұрын

    I've never thought I could find such well presented and easy-to-follow explanaition about this topic in less tan 15 minutes. It's a gem among stones.

  • @insofcury
    @insofcury4 жыл бұрын

    This just cleared every possible doubt that I could possibly have related to hash tables.

  • @felizdeannemayao4811
    @felizdeannemayao48114 жыл бұрын

    I love how excited, eccentric and passionate he sounds. Sounds very motivating for me!

  • @sujithav8871
    @sujithav88715 жыл бұрын

    very good explanation. after a long time, i found a good lecture for hash table. thank you so much for your wonderful lecture

  • @ryanbarry7670
    @ryanbarry76705 жыл бұрын

    Better explanation than my tutor did in 3 hours! So cool, thanks for posting the video!

  • @zhechen4814
    @zhechen48145 жыл бұрын

    Demonstrated the concepts incredibly well!

  • @AshishSingh-gb1yv
    @AshishSingh-gb1yv5 жыл бұрын

    This is neat, well structured and excellent video for any developer to understand HashTable and gives a fair idea about HashMap concepts. Absolutely fabulous work done !!!

  • @monishagowda8928
    @monishagowda89285 жыл бұрын

    And that's how you teach!!! Thank you so much for such a clear explanation 😊

  • @lanat4260
    @lanat42605 жыл бұрын

    I spent hours trying to understand this for my final exam tomorrow to no avail. Until i came across your video! Thank you so much for this :)

  • @ironbob11
    @ironbob113 жыл бұрын

    Described way better than all the other videos I've seen on this topic. Thank you

  • @tigerslashii7097
    @tigerslashii70975 жыл бұрын

    This was incredibly straightforward and easy to follow.

  • @charlesbaldo
    @charlesbaldo4 жыл бұрын

    I just found this. As a professional with 30 year experience with data analysis you are spot on, well explained. I subscribed and set notifications on, hope to see plenty more from you.

  • @arielspalter7425
    @arielspalter74254 жыл бұрын

    Fantastic tutorial. Just perfect pace, perfect intonation, perfect graphics and perfect depth to explain the topic to non-educated programmers like me. Subscribed!

  • @jorgeramos9350
    @jorgeramos93505 жыл бұрын

    I have reviewed several KZread explanations about hash tables and hash functions, and none come close to this one. It was clear and to the point. Great job and thank you!

  • @TaylorColpitts
    @TaylorColpitts5 жыл бұрын

    Great breakdown and very well illustrated - it's been a while since I've used these. Thanks!

  • @polomame
    @polomame5 жыл бұрын

    I don't normally like videos on youtube, but you helped me understand this concept.

  • @jannesvanquaillie9151
    @jannesvanquaillie91515 жыл бұрын

    This is a SUPER good video. I've always wondered how hash table worked. But I didn't think it was this genius.

  • @yukeyang5735
    @yukeyang57355 жыл бұрын

    Very hard-core stuff, yet very easy to digest. You are a genius.

  • @patrickd791
    @patrickd7914 жыл бұрын

    Really eloquent description of the subject. This is the first time I feel like I actually know something about Hash Tables. Thank you.

  • @victorboateng5449
    @victorboateng54492 жыл бұрын

    This was posted 5 years ago but I can say it is still relevant today. Appreciate the wonderful explanation

  • @ComputerScienceLessons

    @ComputerScienceLessons

    2 жыл бұрын

    Thank you :)KD

  • @safedupkid
    @safedupkid5 жыл бұрын

    Excellent explanation. Appreciated the clarity and succinctness

  • @neonoply2205
    @neonoply22056 жыл бұрын

    A wonderful explanation which resolves all my questions.

  • @ashutoshmane3513
    @ashutoshmane35135 жыл бұрын

    it was one of the easiest explanation i had witnessed to something, without letting go the jargons. great subscribed

  • @LandNfan
    @LandNfan4 жыл бұрын

    Excellent video! I spent the last half of my 34 years in IT working with the Advanced Pick and Unidata databases which depend heavily upon hashed access. The key to efficiency is selecting the right modulus when creating your file. Too small and you get too many collisions, too large and you waste space. The multivalue database concept goes back to the mid-60’s, but it is still hard to beat for efficiency and ease of use.

  • @cogs11
    @cogs114 жыл бұрын

    This was a great explanation ! I was even imaging how this could be coded.

  • @CarlNeuDitters
    @CarlNeuDitters4 жыл бұрын

    Fantastic. Not only did you lay out the problem well, and explain how hash tables work but you even set a good example of what any kind of teaching should be.

  • @m.l.c.m.madhawa4649
    @m.l.c.m.madhawa4649 Жыл бұрын

    This is the clearest and most concise explanation I've come across

  • @VolkWasHere
    @VolkWasHere5 жыл бұрын

    Give this man a Medal, thank you!

  • @jenjen3
    @jenjen35 жыл бұрын

    Great video, I'm totally new to this and actually understand hashmaps now. Thank you so much!

  • @FidelSantana87
    @FidelSantana876 жыл бұрын

    The best professor I've ever listen in my entire life!!!!

  • @martesegoosby9085
    @martesegoosby90855 жыл бұрын

    I appreciate that you provide multiple collision resolutions

  • @deancj1
    @deancj12 жыл бұрын

    This is the clearest, most concise explanation of this structure I've come across. Thank you! A lot of people really muddy this subject up.

  • @ComputerScienceLessons

    @ComputerScienceLessons

    2 жыл бұрын

    Thank you :)KD

  • @m.l.c.m.madhawa4649

    @m.l.c.m.madhawa4649

    Жыл бұрын

    Yes I was also going to tell that, this is the clearest and most concise explanation I've come across

  • @stephan553
    @stephan5534 жыл бұрын

    One _very important_ case against open addressing is that any case where the key is not contained in the hash map can only be resolved in O(n) time, that is a time linear to the length of the whole map. Closed addressing can resolve this by simply traversing the much shorter list at the respective key. No matter if databases, caches or many other use cases, looking up a missing key is a very common situation.

  • @your-mom-irl

    @your-mom-irl

    Жыл бұрын

    That shouldn't matter much if the load factor is kept low and the hash function has a good distribution, but yeah it is a possibility lol A uniform distribution with 50% load factor will give you an average of just 1 miss

  • @viniciusqueiroz2713
    @viniciusqueiroz27132 жыл бұрын

    Finally a comprehensive explanation! Thank you so much!

  • @jsonslim
    @jsonslim2 жыл бұрын

    After checking several hashmap lessons I want to say that this is the best one

  • @neeyatiajmera869
    @neeyatiajmera8694 жыл бұрын

    By far one the best explanation videos I've ever watched. The most useful 14 minutes of my life. Thanks!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    4 жыл бұрын

    Glad to be of help. Thanks for the lovely comment. :)KD

  • @herokim5113
    @herokim51134 жыл бұрын

    You are the best voice actor in CS. You deserves it!

  • @kalanaherath3076
    @kalanaherath30764 жыл бұрын

    I absolutely LOVE your channel! it really helps me with my A level ICT studies! Thank you! I am eternally grateful!

  • @kardelenbuz450
    @kardelenbuz4504 жыл бұрын

    ı've been listening for a whole year from my professor and couldnt understand any of these... now even i cant believe that i got the point . thank you so much

  • @casanovavzla
    @casanovavzla5 жыл бұрын

    You just got me like 1:30 hour of sleeping instead of having to search the entire internet.... Thanks a lot! Suscribed!

  • @daniloradulovic7646
    @daniloradulovic76464 жыл бұрын

    Basically i listened 2min of your video and i understood everything good job man!

  • @lucianorosset4112
    @lucianorosset41124 жыл бұрын

    Finally! A good, didactic explanation of hash tables! Thank you :)

  • @kevin_machine_learning
    @kevin_machine_learning5 жыл бұрын

    Some Profs can, of course, explain what is hash table, but you just do that in about 10 mins!!! Your explanation is so clear and easy to understand, I think that is what students are looking for! Thank you Sir!

  • @kazimafzal
    @kazimafzal5 жыл бұрын

    Loved the concise yet thorough explanation! More vids like this one please! Subbed!

  • @TheInertBoyz
    @TheInertBoyz6 жыл бұрын

    That's perfect explaination....

  • @chasingthestereotype6420
    @chasingthestereotype64204 жыл бұрын

    thank god you decided to record youtube videos. You just destroyed my fear of hashing in under 15 minutes, you have my eternal gratitude

  • @sandipanbera
    @sandipanbera5 жыл бұрын

    This is a video of a different level. Hats off to you Sir.

  • @rebeccataylor8188
    @rebeccataylor81884 жыл бұрын

    Never heard someone so hyped about hash tables, but I love it. Thanks for the great explanation!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    4 жыл бұрын

    It's a Sunday morning pastime.

  • @mushusax
    @mushusax6 жыл бұрын

    The examples he uses are real. Ex: Bea = Beatrice Tinsley; created galaxy models Ada Lovelace = Ada Lovelace; the first programmer

  • @ComputerScienceLessons

    @ComputerScienceLessons

    6 жыл бұрын

    Mostly... Beatrice Tinsley (Astronomer) Tim Berners Lee (Computer Scientist of WWW fame) Leo Adelman (Mathematician of RSA fame) Jan Łukasiewicz (Logician of reverse Polish notation fame) Lou Kauffman (Mathematician - of polynomial fame) Max Newman (Mathematician and code breaker) Ada Lovelace(Computer Scientist) Ted Nelson (Computer Scientist and Philosopher) Sam (Sam Malone - the guy in Cheers) Mia (the space station) Zoe (Zoe Saldana - Guardians of the Galaxy, Star Trek)

  • @Afdch

    @Afdch

    5 жыл бұрын

    @@ComputerScienceLessons Except the space station is MIR, not MIA. Just saying.

  • @ComputerScienceLessons

    @ComputerScienceLessons

    5 жыл бұрын

    мое орфографическое отстой

  • @SJ23982398

    @SJ23982398

    5 жыл бұрын

    Yeah and Tod is real too. Tod Einstein. Famous for drinking a relatively large amount of beer in a very short amount of time.

  • @charlesbaldo

    @charlesbaldo

    4 жыл бұрын

    M Detlef she died. A life of debauchery is often short.

  • @danijelvasov9999
    @danijelvasov99995 жыл бұрын

    Great explained! Simple and concise! Amazing!

  • @claire3z
    @claire3z4 жыл бұрын

    Super clear and well explained. Thank you so much!

  • @arlene5990
    @arlene59905 жыл бұрын

    omg i love your voice and your explanation it’s really clear, thank you!!!

  • @keeperkell13
    @keeperkell135 жыл бұрын

    I don't normally comment on videos but this was the most helpful explanation of what a hash table is and how to use one. I have been looking for good articles and videos for a couple of hours before I found this video! So thank you!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    5 жыл бұрын

    Thanks for talking the time to comment :)

  • @DJNecktron
    @DJNecktron4 жыл бұрын

    Thank you good sir for this splendid and easily understandable video! My hopes for the "Data structures and algorithms" exam are looking way brighter now!

  • @mariesv426
    @mariesv4264 жыл бұрын

    Thank you for such a clear and simple explanation of this topic!!

  • @AhmetHDonmez
    @AhmetHDonmez3 жыл бұрын

    Just incredible, thank you for your time and efforts for these incredible videos. Your teaching abilities are through the roof!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    3 жыл бұрын

    You are very kind :)KD

  • @MdMainuddinJU
    @MdMainuddinJU4 жыл бұрын

    This is one of the best lectures I have ever found to understand something clearly and precisely, yet in a reasonably short time.

  • @geybriyel2416
    @geybriyel2416 Жыл бұрын

    finally, a clear and great visualization of the hash table. Thank you so much, this has been really helpful for me to understand the principle.

  • @iAdam368
    @iAdam3685 жыл бұрын

    That was so bloody well explained, I actually get this topic now, thanks!!

  • @ahmedshalaby948
    @ahmedshalaby948 Жыл бұрын

    I just stumbled upon your video and I must say, you did an amazing job! Your clear and concise explanation helped me understand the concept better than any textbook or lecture ever could. Your use of examples and visual aids made the topic so much easier to grasp.

  • @ComputerScienceLessons

    @ComputerScienceLessons

    Жыл бұрын

    Thank you so much. I really appreciate comments like yours :)KD

  • @Democracyphobia
    @Democracyphobia2 жыл бұрын

    ok this was brilliant . we need more teachers like you . understanding whats going rather than just learning by heart .

  • @ComputerScienceLessons

    @ComputerScienceLessons

    2 жыл бұрын

    Thank you so much :)KD

  • @claytonzdroik9796
    @claytonzdroik97965 жыл бұрын

    Thank you! This is the best explanation out there!

  • @mazedesign9804
    @mazedesign98045 жыл бұрын

    I applaud you, honestly the best video on computer science anywhere period. GREAT WORK! didn't take a single note

  • @reca117
    @reca1177 жыл бұрын

    Your videos are amazing quality. Keep it up

  • @ComputerScienceLessons

    @ComputerScienceLessons

    7 жыл бұрын

    That's great to hear - Tnx

  • @user-jf4cb3nn6p
    @user-jf4cb3nn6p5 жыл бұрын

    Thank you so much!! i thought i'd never understand this!

  • @yenenehmulatu5707
    @yenenehmulatu57075 жыл бұрын

    One of the best explanation, thank you

  • @00arashad
    @00arashad6 жыл бұрын

    Great explanation. Clear and concise. Thank you!!

  • @GunelMammadova93
    @GunelMammadova935 жыл бұрын

    The best explanation of hash tables/functions! Thank you!

  • @ChrisBreemer
    @ChrisBreemer5 жыл бұрын

    Excellent, crystal clear, perfectly animated and optimally paced. Many thanks ! What I missed were some simple ideas to improve the hash function to reduce collisions. I could think of factoring in the position of a letter, so that 'Leo' doesn't collide with 'Loe'. Maybe also the length of the string though that's of no use in this particular example. Also it would be great to have some examples of how to choose between closed and open (and the different variants of open).

  • @yorgosathanasiadis5335
    @yorgosathanasiadis53354 жыл бұрын

    Great video. Thanks for explaining so clearly the concept of hashing

  • @Puffufuf
    @Puffufuf5 жыл бұрын

    Thanks this made hash tables make a lot of sense. Cheers from Papua New Guinea!

  • @sramaiah110784
    @sramaiah1107846 жыл бұрын

    Very neat explanation! Thanks for the detailed picturization of how things are stored internally.

  • @ComputerScienceLessons

    @ComputerScienceLessons

    6 жыл бұрын

    You're welcome. Thanks for the feedback.

  • @charlliemurphy8381
    @charlliemurphy83814 жыл бұрын

    this dude saving lives in 2020

  • @ed2023bc
    @ed2023bc2 ай бұрын

    The best explanation I've seen. Thank you!

  • @osamaa.h.altameemi5592
    @osamaa.h.altameemi55924 жыл бұрын

    Best explanation so far and the animations are so on point. thank you for making data structures enjoyable again :)

  • @ron0studios
    @ron0studios3 жыл бұрын

    this is the most beautiful explanation of hashing I've ever come across. Well done! All the other vids take a cryptic description and focus more on big ideas like blockchaining and encryption/security. Having a nice bit-sized chunk really helps out! Thanks!

  • @ComputerScienceLessons

    @ComputerScienceLessons

    3 жыл бұрын

    Lovely comment. Thanks for making me smile :)KD

  • @pranavnyavanandi9710

    @pranavnyavanandi9710

    Жыл бұрын

    I would like it if videos like this transitioned to such bigger concepts after giving a good foundational understanding like this. Would be real helpful, especially for beginners looking to advance.

  • @sushruttabakade6088
    @sushruttabakade60885 жыл бұрын

    Tens of books couldn't teach me what you just did in a couple of minutes. you are fantastic!!!

  • @ChuckHahm
    @ChuckHahm4 жыл бұрын

    Such clear explanations. Great work!

  • @punpompur
    @punpompur5 жыл бұрын

    this explanation is so simple and easy to understand. thank you. keep making such videos

  • @GoddamnAxl
    @GoddamnAxl5 жыл бұрын

    You sir deserves a medal;

  • @ComputerScienceLessons

    @ComputerScienceLessons

    5 жыл бұрын

    I'm still waiting for the queen to get in touch. :)

  • @intrepidsouls
    @intrepidsouls4 жыл бұрын

    That is what we call a man born to be a teacher.

  • @sunmonu-adedejiolawale4959
    @sunmonu-adedejiolawale49592 жыл бұрын

    Thank you so much for demystifying HashTables.

  • @gonejellyfishin
    @gonejellyfishin6 жыл бұрын

    I was super confused on hash tables and now I get them! Thank you so so much!