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?
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.
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.
@@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)
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.)
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?
