4. Hashing
Vložit
- čas přidán 7. 06. 2024
- MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Jason Ku
View the complete course: ocw.mit.edu/6-006S20
CZcams Playlist: • MIT 6.006 Introduction...
Hashing allows for faster search and dynamic operations on data structures, arrays, and sorted arrays. This lecture discusses comparison models, decision trees, and hash functions.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Support OCW at ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s CZcams and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/comments.
Yeah,I went to MIT.
So how was the experience?? Are u rich now?
@@hrishikeshjadhav7010 pardon?
Same here my brother, same here.
Do you make the money you should be making with a degree from MIT? Is the degree really worth it’s worth?
@@AlexNH56 WHOOOSH!!!!
0:00 intro
4:15 comparision model - proof of lower bound for find(k) op
13:34 direct access array
23:10 hashing
34:40 division hash function
39:26 universal hash function
Appreciate it
You are saving my life thank you so much. Finally I can find a professor that is speaking in a human way instead of assuming students know a lot and just skipping the important parts.
ha
All of their lecturers are so damn good. They break the material down such that anyone who's interested can understand it, and many are good natured, humble Nobel Laureates. Just amazing.
What the hell is this, this guy asks questions, this guy engages, this guys doesn't rely on slides, this guy actually isn't affraid to talk about the math and he even makes it simple, where were you when I needed you Mr. Ku? You're perfect, I needed to figure all of this shit on my own and wow what i wouldn't give to have an education of this quality
I agree, his teaching style is excellent. I'm surprised because sometimes I think people who are really smart can't properly communicate their understanding. But just listening for 10 minutes I would love to take his class. His style is engaging, encouraging, supportive, elaborate, thoughtful, and effective.
@@faaizsiddiqui7906 It must take much time, patience and efforts for a genius to figure out a way to explain concepts such that most people can understand. Respect.
Thank you so much for uploading these new lectures
I think Linearity of Expectation holds regardless of whether the involved random variables are independent or not.
Thank you for uploading this lecture!
GREAT LESSION! GREAT STUDENTS!
Honestly, all public Universities should have to make their lecture recordings public domain. Nearly all of them already record and store every lecture, the only reason they don't is to prop up the perceived value of their education. Essentially: You can't get this information arranged and presented like this unless you pay into our program. It honestly would open up so many avenues for the general populace.
MIT is in a position where they can do this, just like Harvard and Stanford. It's the same reason why they say if you get into our school and you can't afford it, it's free. Money isn't a problem to them.
Only private colleges can post their lecture recordings. UC Berkeley had a ton of lectures on CZcams about 5 years ago and was sued by some branch of the federal government for non-compliance with the ADA and forced to take down all the content. The issue was a lack of subtitles and they didn't want to pay somebody to add subtitles to all of the videos.(I guess they need to be correct edited subtitles not the YT auto generated stuff) And of course who is going to pay major legal fees to appeal and fight for giving away free stuff.
I understand the ADA requirements for accommodating students that were actually enrolled in the original classes. But to extend this to surplus content released to non-students long after the course is a perversion of the law and a minor power grab by bureaucracy X to extend beyond its legal juristication.
@@mytech6779 That is ridiculous, "Since some people can't consume this content, no one will be able to." I had to validate what you said because I couldn't honestly believe that would be allowed. Sounds like something out of a comedy sketch.
@@macicoinc9363 Remind me which fed agency was it?
@@macicoinc9363 "We're from the government and we're going to help you."
At 50:51, shouldn't that be less than or equal to as probability 1/m is an upper bound to the probability of two keys having the same hash value?
48:53 I would like to mention that switching the summation sigma here does not need to have independent random variables. Expectation is by definition an integral, and thus innately a linear operation over random variables, which are merely measurable functions.
.
thank you MIT.
18:09 well so my rolls royce is parked out front on the lawn by the fountain so this is the best knowledge i ever has.
.
it takes 3hrs to catch the idea.Neat way of teaching
Thanks, it makes sense. Finally!
Feel like I have wasted so much time in school with terrible lectures.
Wish they could've been like this.
Best lectures ever
So glad I found this
pretty good session !
How to handle badly skewed inputs for hashing ?
The last 10 minutes were kinda brutal. I got so lost lol
Erik Demaine's lecture on Hashing in 6.006 Fall 2011 is so much better. If you aren't understanding this, I'd suggest watching that.
The universal hash function proof is a little scary.
thank you!
Very simple and easy to understand thank you
man the explanation is so good, even makes a dumb like me understand
I didn't see one single head nod at any point after any time that he asked 'does that make sense?'
12:20 - Begging the question.
13:24 wouldn't the min height be log 1???? because the best case scenario we would find what we want in the first node/leaf
Question:
At 51:00 Jason says that chain length is constant if m is at least order n. Will 1+((n-1)/m) not be between 1 and 2 which is not constant.
If m is massive and n is massive then 1+((n-1)/m) would be about 2.
If massive and n is small, say m=10000000 and n=1, then 1+((n-1)/m) is about 1.
I am not great at probability, which is probably why I don't understand.
Thanks for any clarification.
He means constant in the sense that it would not be linear or logarithmic or something like that. It can be greater than 2 and still be constant.
Thanks man
why is memory access constant time? are we assuming the bus is this wide to support the full memory address? Seems like a big assumption since we do not know how large the data set is
If the data set is larger than your computer memory, you're screwed because you need to somehow chop up your data first and none of the algorithms so far will actually work as described. This is why they keep referring to 2^w, which is the maximum amount of RAM supported by a computer given a word size of w-bits.
Just use a large array for your hash table so it is loaded no more than about 10%. This will reduce collisions drastically which is good. Memory is cheap and abundant in many computer systems. Also, if using linear resolution method for collisions, just keep track of the maximum offset used for a given set of data, that way you never have to scan more than that. For example, if Bob, Jim, and Steve all hash to bucket 8 in a size 128 hash table, with Bob getting inserted into bucket 8, Jim gets put in bucket 9 and Steve gets put in bucket 10, at this point, our max offset is 2 (for example, Steve wants to hash to bucket 8 but got put in bucket 10 which is offset by 2). So now if we want to look up if Mary is in our hash table and Mary also hashes to bucket 8, but there are also directly hashed items in buckets 11, 12, 13 and 14 (meaning their positions were not altered), we only have to compare Mary against whatever is in buckets 8, 9, and 10, then we can stop if Mary is not found. We do NOT have to check buckets 11, 12, 13, and 14. In general (for lookups), we only have to check buckets hash value to (hash value + offset), stopping immediately if found. For example, if offset is 2 and we look up Jim, we may have to check buckets 8, 9, and 10, but upon seeing it is in bucket 9, we stop, not even checking bucket 10. My 2 cents.
"Memory[/CPU cycles] is cheap and abundant in many computer systems.", ah the rhythmic mating call of code-camp hacks that think all computers are high end desktops with direct fiber internet connections and doing little more than processing instant messages.
48:50 As I learned in 6.042j 2010 from Prof. Leighton, Linearity of Expectation holds regardless of mutual independence property.
Correct me if I misunderstood.
No, Linearity of Expectation does not hold regardless of mutual independence property. Linearity of Expectation is a property of expected values in probability theory, which states that the expected value of the sum of random variables is equal to the sum of their expected values, even if the random variables are dependent. However, this property holds only when the random variables are mutually independent.
Mutual independence refers to a property of multiple random variables, where the occurrence or value of one variable does not affect the occurrence or value of another variable. When random variables are mutually independent, their joint probability distribution can be factorized into the product of their marginal probability distributions. In this case, Linearity of Expectation holds, and the expected value of the sum of the random variables is equal to the sum of their expected values.
However, if the random variables are not mutually independent, Linearity of Expectation may not hold. In other words, if the variables are dependent, their joint probability distribution cannot be factorized into the product of their marginal probability distributions, and the expected value of the sum of the variables may not be equal to the sum of their expected values.
Therefore, Linearity of Expectation holds only when the random variables are mutually independent, and it may not hold when the variables are dependent. It is important to consider the mutual independence property when applying Linearity of Expectation in probability calculations.
Great!!
51:20 shouldn't be n-2? instead n-1, the result of the sum, bc one of the n-1 elements is not counted and that's when j=i, can anyone explain? thanks!
answering my own question, the sum goes from 0 to n-1, so there is n elements (n times 1) except the element when j=i, so the result is n-1
does that make sense?
it does
31:32
The person already said earlier that you could use a linked list... 28:32
Why did you ignore them earlier?
That person was thinking (or at least the professor interpreted she implied that) the entire hash table as a linked list structure. Instead, what the professor is proposing is an array (the hash table) whose elements are pointers to linked lists.
nvm, I thought it was a video about how to make Hashish
A little confuse that if you need to choose m lager than n to keep conflict probability of hash table small than 1/m. Why do we need the hash table? Unless n means the number of keys rather than largest key in origin array?
Exactly, n is the number of keys
They need to teach camera operation at MIT.
You should’t feel guilty never, Watever happens and Could happen, is not your fault 🥺. Don’t feel Bad. But look, you will always have the chance to ignore this problem. I will tell you what. Take care of all the other problems you might have, and then i Will be here when you come back. There isssss time. No need to rush.
@12:14 he asked a question saying why we need to think of the minimum height of a binary tree with at least n+1 leaves. I wonder why that minimum height is significant for the hashTable that was discussed later. Please explain. A student asked a doubt at that time and the Professor forgot to reiterate his statement.
The number of operations (comparisons) in the binary decision tree is logarithmic, while the number of operations to find/insert an item in the hash table is constant given an adequate table size m. It's the difference, for a set of items of reasonable size, of executing tens of operations or just a couple to find a key.
Is this the same course as of 6.006 taught years back ??
Not exactly, but yes.
@@krishnachaitanya8353 are you taking this course ?
@@peterjamali772 No, but occasionally will refer to the material.
The content is similar but a way better.
Universal hash function
hash(k) = (((ak + b) mod p) mod m) at 41:31
How do we know the key value (k)?
Can anyone explain?
K represents the input we're passing into the hash function. It's the parameter to the hash function, ie. "the thing you are hashing."
Can be any value between 0 and u-1. It's the universe of possible keys. The conclusions are for a random set of keys, in the average case.
Seeing how the quality of teaching is so much better than what i got makes me realize the American education system and American society id doomed to collapse , because it is revolved around money and it system (or structure) can not keep up with its demand ( skilled works equals better products , better products equals more money ,but poor education institutions does not equal big amounts of skilled workers so you will have shortage of skilled workers and surplus of unskilled workers )
Can I see your bonker certificate please?
Great video! Thank you MIT OCW :)
18:37...how is it 10^9? Can someone please explain?
That's how many 9-digit numbers there are. So in order to be ready for any possible 9-digit ID number, you would have to have 10^9 spaces available in memory.
Using a small number set. Say 3 digits. The max space we need for 3 digit numbers is 000 - 999, which is bounded by 10 ^^ 3. So, to handle a 3 digit number we'll need an array which has a size of at most 1000.
Same applies to 9 digits numbers.
Quite complicated to understand
Thanks for uploading this lecture and all the other MIT lectures. I am somewhat shocked by the questions some of the students were asking considering they're MIT students, but half are wearing hats indoors so I'm not really surprised.
YEES, it makes sense!! :D you asked for it like 20 times xd
Usually when I think of hashing, I think of Waffle House, IHOP, McDonalds, Perkins... oh, maybe that is hash browning.
Can someone explain how it's possible for the universal hashing function to make the probability of two keys hashing to the same value be less than or equal to 1/m, for ALL keys? Wouldn't the perfect case be that after hashing, the keys are uniformly distributed, in which case the probability should be equal to 1/m?
I think I'm missing something here but for the probability of a pair, to be hashed to the same value, to be less than 1/m, wouldn't that imply another pair is necessarily greater than 1/m?
I think you're right. It must be equal to 1/m, given that a and b are chosen randomly, and not less or equal to 1/m.
Linearity doesn't need independence.
Thanks for the lecture, these are great resource. Some constructive feedback for Jason, I found your mannerism of saying "right" at the end of your sentence very distracting. In my opinion, the already high value of your lectures would improve. Thank you again.
21:51
I find the universal hash function stuff somewhat of a cheat, or at the very least a misnomer. That a universal hash function is not unique is a non-problem (universal things are hardly ever unique) whose mention masks a more important defect: it is not a hash function with some universal property, in the way that a universal Turing machine is a Turing machine with some universal property. Indeed it is not a hash function at all, but a family of hash functions. And the way it achieves "universality" (which I guess means being efficient on all inputs) does not ring true: all functions in the family have bad worst-case complexity and good average complexity, and we are made to believe that by choosing a random member the worst-case magically dissolves. Which of course it does not; it is just harder to pinpoint. It is like claiming in a chess position you have a winning strategy by not telling what your first move is; if only you opponent would be so kind as to tell their first move is (the set to represent with a hash table) the you will demonstrate that many first moves will defeat it. But that is not how the game is played: a program must be provided before its input is known. And if the program uses true randomisation, then the random data is part of its input, not of the program: a user really doesn't care if they could hit a bad case due to unfortunate input or due to unfortunate randomisation. If one is really only interested in average rather that worst-case complexity, then one should just say so. And in that case randomisation buys you exactly nothing.
I like this comment very much.
But average complexity is dependent on both worst case complexity and probability of worst case complexity, if you reduce the probability of the worse case then the mean improves. (Though the median may not improve much, I suppose this is very much linked to each specific case.) I haven't done a proper analysis, am I way off?
@@mytech6779 Yes, I'd say way off. Average and worst case complexities are independent quantities; you cannot determine one from the other even given some additional statistics. Like one cannot determine the average height of a person in a given population from the height of the tallest person, or vice versa.
@@marcvanleeuwen5986 I agree with that but it isn't what I was getting at.
You don't need to determine the mean of a population to know that changing the height of the tallest person effects the mean and does not effect the median.
When he wrote ≠ instead of != I was
I thought you were !
If U is large, then you is in charge
28:30 the professor tosses out the idea of storing linked lists then 5 minutes later suggests that idea
He tossed the idea of using a linked list for the hash table itself, not for the "buckets" of items in the table
why is linked list not suitable for hash table@@leogama3422
Link list lookups are not necessarily linear time. You wouldn't say binary search is linear time right? Well what if I had a linked list and instead of just a pointer from one element to the next, I instead had many pointers that approximated a binary search? For example, imagine I insert items into a linked list so that I maintain them in some sorted order. Let's assume 1000 entries. In the simplest example, I can add 1 extra pointer which is to the middle of the linked list, allowing me to skip over half of the items. So if I want to find a name in the sorted linked list such as Roger, I can check the first element and see that it is Adam, then immediately check the middle (500th) element and see it is Ralph, and then know I need to check only the 2nd half of the list of names. I can "split" the data with pointers many times too, for example, have pointers to elements 250, 500, and 750. The more I split, the more I can narrow down the lookup to make it quicker. So I have to disagree that a linked list is linear time. If I had (and maintained) enough links, I could approximate the speed of a binary search because I could have pointers to the middle of each main section (of size 500 each), then pointers to the middle of those subsections (of size 250 each).... Yes I realize it is a lot of work to maintain this, but I just wanted to prove my point that linked lists can be made NOT linear (for lookups). Of course if the elements are not sorted, then there isn't much advantage to having these "extra" pointers.
Except you don't use a linked list, but a different structure called a binary tree. Also: In any practical situation the lists of a chain are less than 10 items. It is complete and utter overkill to use such a complicated and memory intensive structure, which needs constant rebalancing on updates as well.
@@erwinmulder1338 I was just making a point that this guy is misleading students.
@@erwinmulder1338 Practical? Why should a linked list length be limited to only 10 nodes? That seems ridiculous to me. Computers can process lists with thousands of links in a reasonable amount of time. We are not talking a 4.7 Mhz computer from the 1980s. They are several orders of magnitude quicker than that now. 4.7 Ghz for example.
Linked lists definitionally cannot be made more efficient than linear for random lookups because the only way to find the "middle" is to start from the head and walk to the tail. Even if sorted. This lecture is not misleading.
@@TimothyRourke I totally disagree with you. It is obvious that a linked list can have multiple pointers, so it would be easy to add a pointer to the middle of a long sorted linked list for example, thus cutting out about half of the links to be searched. The definition of a linked list states each node must point to the next node in the list, but doesn't state that it must ONLY point to that next node. Therefore we are free to introduce additional pointers at will. The link implies that the node are connected that way, rather than being positionally connected (such as in an array). However, I can add pointers to other things such as other nodes that are not neighbors. I don't see any restriction preventing that, as long as each node at least points to the next one in the list, creating a linear sequence. Whatever other pointers I add after that is my business... it doesn't then make it not a linked list. I would have to break one of the required links to "unmake" it a linked list.
If U is large then U is in charge baby hahaha stay cool baby ; )
🇺🇸🇺🇸🇺🇸🇺🇸🇺🇸😊😊😊😊😊😊
There are theories Does have connections to so called Blockchain technology in today's economic society But also a probability link to codes to decipher A.I. basic alogrythm. Stuff that were born to dream of?
YOU SHOULD HAVE AN ACTUAL TREE LIKE AN OAK TREE WHEN EXPLAINING THIS. Make the connection of data structures to nature. That will make it stick
Videos have been great till now. My only qualm is, I don't think that the minds there can appreciate the importance of the subject unless they have really worked in the field and had had to deal with the downside of design decisions they had made in their projects. I, for one, can resonate with the content yet I am unable to interact with the professor. MIT lectures in person may remain a dream...
How do you do a hashing function? Easy, just choose whatever is the standard hashing function in whatever language you're writing your code in. Actually this is like 95% of modern programming and why these kinds of lectures and indeed entire computer science programs, although interesting, are mostly time-wasters.
This is a computer science class, not a code-camp bloatware class.
ie the people who actually create and implement efficient hashing functions for your language library. People that understand that the right function for an embedded 8bit microcontroller may not be the same as the right function for a safety/mission-critical system, which is not right for a distributed webservice and how to select which to use where.
@@mytech6779 but the overwhelming majority of these kids will go on to work at jobs and do similar task to those who come out of "code-camp bloatware class"; just for bigger companies, i.e. Google, Facebook etc.
This lecture is not about how to "do a hashing function"; it's about what a hash map is, why it's useful and efficient, and how to understand performance characteristics of a given solution to a programming problem using this strategy. By the way, this lecture goes a long way in pointing out that picking any old hashing function is not a good idea because each one has different tradeoffs.
I don’t understand why some people thinks he is great professors. What he is teaching nothing makes sense. I am so lost when he said its N+1 nodes. MIT can do better!
you dull then, what he said clearly makes sense
Low tech black board 🤣
someone asked what n means. seriously? are these guys from MIT? fuck me ...
I think you missed some part of the context.
As a good teacher you indulge the freshmen. He’s a great teacher.
People can get distracted for a moment...
Gibberish, right?
sounds inexperienced for MIT standards
I was really surprise to realize MIT also have bad teachers.
A torture! Stuttering lecturer, unstructured and unmotivated lecture (chain of thought not clear) . "Right?" Looks like they roll out only the trash. "That make sense?" The overall impression is that the professor doesn't understand the subject very well. "Any questions? No?"
If this was the case, why is every student paying attention and focused on the lecturer? While I will agree the mannerisms were at times distracting and is one area Jason can improve his lecture style, the lecture was of a high quality moreover the students were comfortable with asking questions because his lecture style was welcoming and positive. I also found the lecture to be of high energy and very motivating. As for the chain of thought, I suggest you re-watch the lecture again it is very structured, and covers a very complex subject matter the requires the lecture to describe the events of a number of systems that occur at the same time. Lastly, I am assuming Jason is a jnr lecture, it takes a lot for a person to stand infrount of a group of students, and present such a complex subject matter matter, rather then being judgemental and negative, how about be constructive, and encouraging, then we would have more people wanting to help others, instead your bs comments, result in people avoiding such jobs because of comments from those who need to put others down in order to feel better about themselves, I suggest you find a better outlet for your own issues, and stop hiding behind a keyboard.
@@lukea3836 This is MIT. And it looks it has it's reputation not due to the brilliant educational service they provide, but due to the quality of it's students. Watched a few other lectures - a female professor in poverty stood out... Universities are dead (outdated). By the way I'm pretty sure the stuttering lecturer will be really cocky once it's time for the exam... bet he won't be "jnr" then :D
Anyways - I am retarded and bitter.
I am a coward and hide behind the keyboard.
I have issues and a tiny you know what.
Best regards & thank you for your response. I really hope we could make a few more rounds! :)
@@AsenAtanasoff1 And what makes you pretty sure? Do you know the lecture personally? No - you are just being judgemental. Dont you have better things to do then make up stories about someone you dont know? Go deal with what ever issue you have, that causes your need to make up stories about people you dont know.
stuttering now? I didnt here any stuttering?
What evidence do you have to support your position that Universities are dead? The Internet being free, does not mean free of facts, or free of references when you publish a statement that you claim is factual, and certainly not free of people who have 0 consideration for other peoples feelings.
and by the way, just want to remind you, Jason the lecture, he is a human, what has he done to deserve your nasty comments? You are evidence that humanity does not exist online. Just remember you type on a keyboard, and sit behind a screen, but on the other end, there is a human, with real feelings, and you are just as much as an a hole when you post unsolicited hateful comments, as you are if you do it in public with words.
Absolutely, he may be too smart but he is not a good teacher.
"what is n?" gg