@@davidjmalan Thank you! I just learned about the genesis of this catchphrase in your freecodecamp interview, haha... For everybody interested, listen to it here: freecodecamp.libsyn.com/ep-71-harvard-cs50s-david-malan-and-colton-ogden-on-computer-science (The part about "THIS is CS50" starts at 01:59:50)
Thank you, Professor Lloyd, for your amazing explanation of the material in CS50x. I have taken many online courses in the past, but this is the only one that has been so comprehensive and well-explained. I never have to waste time searching for additional information because everything I need is covered in the lectures, sections, and shorts.
I love harvard university, For some reason almost no one knows how to explaing hash tables in a simple way but this video just clear everything up for me. Thank you Doug!
After implementing linear probing on Doug's hash table example now i understand why its not a good example (different char strings can have the same sum so they are given the same hash code)
Why did they switch from "don't write your own hash functions, just find some on the internet" to "you better write your own hash function or else" for pset5 lol
Curious why the hash function Doug wrote isn’t good? It generates different hash codes for similar data and allows you to increase the number of buckets to the extent of memory Is it because the number of buckets is not related to the number of elements in the hash structure? If so, how would you know the optimal number of buckets?
I think it is bad because it can easily output the same hash code over and over again AB and BA would result in the same hashcode, and also since it is adding up ASCII numbers AAAAA might be equal to ZZZ (the example is symbolic) and then it would result the same hash code as well.
@@ahmetselimerdogan6187but if You ask or compare your string to what is actually in the buckets You can diferentiate both, and maybe add some label to like bucket 1.1 and and then if there have the dame ascci value but diferent string You may solv. The things is that You have to iterate and compare all the link list of one bucket.
7:30 "Generally you're probably not going to want to write your own hash functions. It is actually a bit of an art, not a science. And there's a lot that goes into them. The internet, like I said, is full of really good hash functions, and you should use the internet to find hash functions because it's really just kind of an unnecessary waste of time to create your own." Why did you lie to us Doug?
I'm having some trouble trying to understand how to use the hash tables I can find online. Can someone help me with that? Did any of you had problems with this pset5 and have some good hints for someone who is lost?
there would have to be something unique about the values, some piece of accompanying information that makes them unique, for example a sort of unique ID. otherwise there is no point to it, unless you're trying to write a program to find out how many times Joey occurs. but if that was the case, you wouldn't be need to use such a hash table, but would rather use one where the KEY is the name and VALUE is a counter that's incremented with every occurrence of Joey.
I was thinking about Doug's hash function. He said his hash function is not the best for some reason he was going to get into right now. Is anyone curious about the reasons. looking at the function it add the ascii representation of all the letter in the in the so call string. it then takes the sum of the ascii value of each letter and devide it by size of the array. who could tell me what could go wrong ?? Well suppose when hash jhon and we had a return hash code of 4, suppose we now hash jhon in reverse (nohj) or any sequence of the same characters arrange differently to form another name of the same length , we are going to get the same hash code for these names in other word some collisions. so I guess that's bad but what are the chances right ?? OH by the way thanks for the great lecture Doug. I finally got hash tables
to me it seems like you'd want to use another way of dealing with collisions not because his way would be technically wrong but because as the array grows, you'll eventually run into inefficiencies that negates any performance you gained by using hash tables. for example, what if your array needs to get larger? you'd have to rehash all the values because your "mod" changes. and unless you implement some kind of mechanism to deal with collisions, the max number of elements you can store in your array will be limited to the size of your array (plus one if your default base index is 0.)
Hash tables are used everywhere. There are entire database system designed around hash tables (Redis). The language python is entirely built around dictionaries, which are essentially hash tables.
A real life example could be if you are looking for duplicates in an array. You could loop through each element of the array and create a key value for that element. If the key already exists, then you know you've found a duplicate. The benefit of hash tables is as follows: if you use an ordinary hash object you would have to search each key of the hash object to see if the key already exists, potentially searching through the entire hash object. The benefit of the hash table is the hash function will give you a specific "address" for the key so you can check to see if the key for that specific element exists in one look, instead of having to look at each key in the hash object. In terms of computational complexity, to search a hash object it takes O(n) time but for hash tables it takes O(1).
Many popular language interpreters (Python for example) use them to store your variable names and their respective values. That's how your interprerer knows which variables refers to what. They're also used in JS. Every single JavaScript object is actually a hashtable under the hood.
Collisions are always possible. The hash value is inherently smaller than the value being hashed, so considering all possibilities, there have to be some values that result in the same hash.
I just love the pride with which they say "THIS is CS50" at the end of each video. That's really contagious, makes me proud to be a part of it, too!
Welcome aboard!
@@davidjmalan Thank you! I just learned about the genesis of this catchphrase in your freecodecamp interview, haha...
For everybody interested, listen to it here:
freecodecamp.libsyn.com/ep-71-harvard-cs50s-david-malan-and-colton-ogden-on-computer-science
(The part about "THIS is CS50" starts at 01:59:50)
0:33 vsauce music starts playing in the background
underrated comment
accurate.
Best comment i've seen all week!
lol
I've started watching these videos in 0.75 speed, and I love drunk Doug explaining complex concepts to me! xD
XD 0.5 speed even better!!
I watch them at 1.25 speed to save time XD
@@Dall1n 0.5 speed is gold! hahah Drunk Doug!
I usually watch the lectures at 1.5x. It makes David seem even more energetic than usual lol
LOL
This guy explains stuff stupidely well and simple. Thanks a lot Doug!
Thank you, Professor Lloyd, for your amazing explanation of the material in CS50x. I have taken many online courses in the past, but this is the only one that has been so comprehensive and well-explained. I never have to waste time searching for additional information because everything I need is covered in the lectures, sections, and shorts.
you are the best! keep it up! can't believe such professional lectures are free. Big up Harvard!
Agreed 100% 👏
O0io0o0ii0o0⁰⁸kĺ
@@aprameyaaithal9071 gggĺlllllķ
If these lectures are free just imagine the actual lectures in harvard. Man I wished I was a student there😭😭😭
Loved the Beatles, Simpsons, and Friends references!!
I love harvard university, For some reason almost no one knows how to explaing hash tables in a simple way but this video just clear everything up for me. Thank you Doug!
I love love love Doug's attitude in these videos
This is amazing! The best video explainer of hash tables hands down 🏆
John, Paul, Ringo... and that's why I love CS50
As David likes to say .
The complexity escalated quickly .
Thanks for an awesome explanation!!!
best teacher ever thank you Doug Lloyd
Oh, he linked Phoebe and Joey, so sweeet!😍
This is particularly an exceptional video. If only I could follow Doug into more courses.
Thank you for explaining it in such a clear and detailed manner. Cheers :)
Thanks CS50, Sending you guys a big hug❤💚
Saved my academic life, thanks!
Thank you so much for the illustrative explanation. You just saved my day.
Thank you, Professor Lloyd!😀
What is the standard way to cite the source of my code? Are there rules for this like there are for writing essays in MLA or APA?
Great explanation and that FRIENDS reference though. xD
lol
Dude! What a masterclass of a video!!!!
I love this channel
Excellent explanation: you made it clear for me! Thank you.
you really described in a fantastic way....
After implementing linear probing on Doug's hash table example now i understand why its not a good example (different char strings can have the same sum so they are given the same hash code)
Why did they switch from "don't write your own hash functions, just find some on the internet" to "you better write your own hash function or else" for pset5 lol
"We've chained "Phoebe" in"
I like how he says it's a waste of time to make your own hash function but then this weeks problem set tells you to make your own
Doug you are a legend, thank you.
Doug = Legend
Thank you so much for this.
Thank you so much for the clear explanation
Curious why the hash function Doug wrote isn’t good? It generates different hash codes for similar data and allows you to increase the number of buckets to the extent of memory
Is it because the number of buckets is not related to the number of elements in the hash structure? If so, how would you know the optimal number of buckets?
I think it is bad because it can easily output the same hash code over and over again AB and BA would result in the same hashcode, and also since it is adding up ASCII numbers AAAAA might be equal to ZZZ (the example is symbolic) and then it would result the same hash code as well.
@@ahmetselimerdogan6187but if You ask or compare your string to what is actually in the buckets You can diferentiate both, and maybe add some label to like bucket 1.1 and and then if there have the dame ascci value but diferent string You may solv. The things is that You have to iterate and compare all the link list of one bucket.
7:30 "Generally you're probably not going to want to write your own hash functions. It is actually a bit of an art, not a science. And there's a lot that goes into them. The internet, like I said, is full of really good hash functions, and you should use the internet to find hash functions because it's really just kind of an unnecessary waste of time to create your own."
Why did you lie to us Doug?
finally a big confusion was solved. thanks.
Awesome! Very easy to understand! Thank you!
Now, I can start solving leet codes haha!
Captions aren't not synced with voice. Please fix it
Hi Ilya, thanks for pointing this out! We've updated the subtitles!
Awesome. Thanks Doug!
Legend, Thank you
Quicker and faster, like it. *Thumbs up*
Solid video! Thank you
Well explained!
I hope they had the source code for this lesson
thank you daddy loyd
Thank you very much!!!
I'm having some trouble trying to understand how to use the hash tables I can find online. Can someone help me with that? Did any of you had problems with this pset5 and have some good hints for someone who is lost?
What about in the case that you're trying to add an identical value, e.g. Joey once more? Are duplicates allowed or no?
there would have to be something unique about the values, some piece of accompanying information that makes them unique, for example a sort of unique ID. otherwise there is no point to it, unless you're trying to write a program to find out how many times Joey occurs. but if that was the case, you wouldn't be need to use such a hash table, but would rather use one where the KEY is the name and VALUE is a counter that's incremented with every occurrence of Joey.
oh what a relief bro, thanks!
15:05 Shouldn't that be node hashtable[10], since it arrays are already pointers??
Nah because the data type is node*
I was thinking about Doug's hash function. He said his hash function is not the best for some reason he was going to get into right now. Is anyone curious about the reasons. looking at the function it add the ascii representation of all the letter in the in the so call string. it then takes the sum of the ascii value of each letter and devide it by size of the array. who could tell me what could go wrong ?? Well suppose when hash jhon and we had a return hash code of 4, suppose we now hash jhon in reverse (nohj) or any sequence of the same characters arrange differently to form another name of the same length , we are going to get the same hash code for these names in other word some collisions. so I guess that's bad but what are the chances right ?? OH by the way thanks for the great lecture Doug. I finally got hash tables
to me it seems like you'd want to use another way of dealing with collisions not because his way would be technically wrong but because as the array grows, you'll eventually run into inefficiencies that negates any performance you gained by using hash tables. for example, what if your array needs to get larger? you'd have to rehash all the values because your "mod" changes. and unless you implement some kind of mechanism to deal with collisions, the max number of elements you can store in your array will be limited to the size of your array (plus one if your default base index is 0.)
FINALLY A GOOD VIDEO .
Can't thank you enough!
is shazem using hashing when searching for music ??
great explanation
Hash the citizens of Springfield.
Milhash
Super Dude underrated comment
3:00 for future reference!
Not really sure that is lookup speed is O(1)
How should we distinguish two different objects with the same hash without additional logic?
why is x = 4,(and y =6)? what is stopping x from being 0 or 7?
n o w w e h a s h h o m e r
Rachel and Ross not together in the same list?! How dare you
Thanks for teaching.... You are good.. I give you the credit for the work you did ... Plegiarism you said remember!
Hey but what about cache misses in linked list ?? I thought of using a dynamic array
But if hashtable don't have linked list for handle collisions, is hashtable still it?
thank you!!!
You forgot Chandler Bing!!!!
Monica too !!
thank you!
Hey Dug! you forgot Monica and Chandler lol
Awesome
interesting topic. Thanks, teacher. Advanced topic. Could you suggest some real-life applications?
Hash tables are used everywhere. There are entire database system designed around hash tables (Redis). The language python is entirely built around dictionaries, which are essentially hash tables.
In Javascript for example all objects are hash tables, you can find Hash Tables under the name of Associative Array
A real life example could be if you are looking for duplicates in an array. You could loop through each element of the array and create a key value for that element. If the key already exists, then you know you've found a duplicate. The benefit of hash tables is as follows: if you use an ordinary hash object you would have to search each key of the hash object to see if the key already exists, potentially searching through the entire hash object. The benefit of the hash table is the hash function will give you a specific "address" for the key so you can check to see if the key for that specific element exists in one look, instead of having to look at each key in the hash object. In terms of computational complexity, to search a hash object it takes O(n) time but for hash tables it takes O(1).
Many popular language interpreters (Python for example) use them to store your variable names and their respective values. That's how your interprerer knows which variables refers to what.
They're also used in JS. Every single JavaScript object is actually a hashtable under the hood.
Can somebody recommend a great hash function for javascript?
Wat r buckets in hash tables?
6:23 "you see what's going on here?"
er... sorry, no
Very Good!
Aha! Friends 😁 Chandler and Monica are missing😅
you r great
Captions are not sync :/
Hi Fabian, thanks for pointing this out! We've now updated the subtitles!
@@ArturoJReal perfect!!
I feel like such an idiot... No matter how many times I try to understand the Week 5 content, I just can't follow it...
the beatles ha
where can i find hash functions already created?
Google should yield some results. They aren't uncommon at all.
unreal.
Why are we getting collisions? Shouldn't a good hash function barely have any?
It's not something that can be completely avoided, so there needs to be protocol.
depends on what you are trying to achieve
Collisions are always possible. The hash value is inherently smaller than the value being hashed, so considering all possibilities, there have to be some values that result in the same hash.
Geez this speller is killing me
(y)
1000 Likes
I don't think you'd be allowed to look up hash functions online during interviews sir
Use this in industry.
or we can just use HashTable classes and leverage OOP... without even worrying about it :D
Awesome