4. Hashing

แชร์
ฝัง
  • เผยแพร่เมื่อ 24 ธ.ค. 2024

ความคิดเห็น • 157

  • @ParthPatel-vj2zv
    @ParthPatel-vj2zv 3 ปีที่แล้ว +182

    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

  • @luizfernandobuenorosa2529
    @luizfernandobuenorosa2529 3 ปีที่แล้ว +46

    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

    • @faaizsiddiqui7906
      @faaizsiddiqui7906 2 ปีที่แล้ว +7

      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.

    • @linyerin
      @linyerin 2 ปีที่แล้ว +8

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

  • @ameenh4122
    @ameenh4122 3 ปีที่แล้ว +309

    Yeah,I went to MIT.

    • @hrishikeshjadhav7010
      @hrishikeshjadhav7010 3 ปีที่แล้ว +7

      So how was the experience?? Are u rich now?

    • @ameenh4122
      @ameenh4122 3 ปีที่แล้ว +4

      @@hrishikeshjadhav7010 pardon?

    • @mattizzle81
      @mattizzle81 2 ปีที่แล้ว +2

      Same here my brother, same here.

    • @AlexNH56
      @AlexNH56 2 ปีที่แล้ว +3

      Do you make the money you should be making with a degree from MIT? Is the degree really worth it’s worth?

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว +18

      @@AlexNH56 WHOOOSH!!!!

  • @linyerin
    @linyerin 2 ปีที่แล้ว +67

    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.

    • @JP-fv1id
      @JP-fv1id ปีที่แล้ว

      ha

    • @statikriki
      @statikriki 6 หลายเดือนก่อน

      @@JP-fv1idindeed very ha

  • @jacktrainer4387
    @jacktrainer4387 3 ปีที่แล้ว +28

    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.

  • @offYears
    @offYears 3 วันที่ผ่านมา

    the argument at 10:00 that the decision tree for the comparison model requires n+1 leaves did not click. to clarify (using 'element' to mean a member of the data structure, i.e. each element is associated with a key):
    1. the comparison model _cannot_ operate on a data structure, other than fetching and comparing element keys.
    2. thus the only part of the Set interface we are concerned with investigating using the comparison model is _find(k)_ . we should view the decision tree discussed from 5:00-16:30 as _specifically_ representing the algorithm for _search_ - nothing else (not insert, delete, etc.).
    3. given remark 2, the only meaningful input to the decision tree is a specific _key_ k ( *not* an element!). the desired output is the *element* _corresponding_ to that key. (it is important to appreciate the 'black block'-iness of the tree here. we know _nothing_ about the actual operations required to find a match, other than the fact that all the operations are themselves comparisons.)
    4. given our desired output is an element, this explains why there are n+1 outputs (corresponding to an answer for each element of the data structure + 'none').
    this explains the student's (very reasonable) question at 10:48.

  • @sungjuyea4627
    @sungjuyea4627 2 ปีที่แล้ว +12

    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.

  • @offYears
    @offYears 3 วันที่ผ่านมา

    at 1:46, he claims 2 of the sort methods (permutation, selection) we learned in the last lecture are n^2. however, we actually showed permutation sort to be n!n. i suppose he meant Omega(n^2), as in both are _minimum_ n^2.

  • @macicoinc9363
    @macicoinc9363 3 ปีที่แล้ว +42

    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.

    • @franciscogutierrezramirez5497
      @franciscogutierrezramirez5497 3 ปีที่แล้ว +8

      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.

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว +14

      Only private colleges can post their lecture recordings. UC Berkeley had a ton of lectures on TH-cam 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.

    • @macicoinc9363
      @macicoinc9363 2 ปีที่แล้ว +7

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

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว

      @@macicoinc9363 Remind me which fed agency was it?

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว +1

      @@macicoinc9363 "We're from the government and we're going to help you."

  • @thepolyglotprogrammer
    @thepolyglotprogrammer 5 หลายเดือนก่อน

    Watching this class for the second time, different recordings this time. Feels like it gets better every time.

  • @fwang3695
    @fwang3695 หลายเดือนก่อน +1

    give a lecture: 50 minutes
    step count: 10000

  • @hung-tienhuang3640
    @hung-tienhuang3640 3 ปีที่แล้ว +7

    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?

  • @austinoquinn815
    @austinoquinn815 2 ปีที่แล้ว +2

    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.

    • @MufaddalHakim
      @MufaddalHakim 2 ปีที่แล้ว +1

      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.

  • @lydxlx
    @lydxlx 3 ปีที่แล้ว +17

    I think Linearity of Expectation holds regardless of whether the involved random variables are independent or not.

  • @plushiie_
    @plushiie_ 2 ปีที่แล้ว +2

    Feel like I have wasted so much time in school with terrible lectures.
    Wish they could've been like this.

  • @JohnSmith-yv5bn
    @JohnSmith-yv5bn 2 หลายเดือนก่อน

    12:17 I thought the whole tree would be made from the datastructure items - leaves and not leaves. So it could have less than n+1 leaves.

  • @yahrdme
    @yahrdme 3 ปีที่แล้ว +5

    I didn't see one single head nod at any point after any time that he asked 'does that make sense?'

  • @BRYDN_NATHAN
    @BRYDN_NATHAN 2 ปีที่แล้ว

    .
    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.
    .

  • @franciscogutierrezramirez5497
    @franciscogutierrezramirez5497 3 ปีที่แล้ว +26

    The last 10 minutes were kinda brutal. I got so lost lol

    • @koushikvss7638
      @koushikvss7638 3 ปีที่แล้ว +12

      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.

  • @ElMehdi-61
    @ElMehdi-61 3 หลายเดือนก่อน

    That's so complicated, and yet it's perfectly explained. Thumbs UPP

  • @weignerg
    @weignerg 2 ปีที่แล้ว +1

    31:32
    The person already said earlier that you could use a linked list... 28:32
    Why did you ignore them earlier?

    • @RonaldABG
      @RonaldABG 2 ปีที่แล้ว +1

      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.

  • @jobosan4855
    @jobosan4855 2 ปีที่แล้ว

    12:20 - Begging the question.

  • @bigchadryans230
    @bigchadryans230 2 ปีที่แล้ว +3

    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.

    • @DanilTomenko
      @DanilTomenko ปีที่แล้ว

      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.

  • @karthikKarthik-by6ws
    @karthikKarthik-by6ws 2 ปีที่แล้ว

    it takes 3hrs to catch the idea.Neat way of teaching

  • @Mickey_McD
    @Mickey_McD 3 ปีที่แล้ว +13

    The universal hash function proof is a little scary.

  • @VoxHwa
    @VoxHwa 2 ปีที่แล้ว +3

    GREAT LESSION! GREAT STUDENTS!

  • @shashankbajpai5659
    @shashankbajpai5659 3 ปีที่แล้ว +5

    Thank you so much for uploading these new lectures

  • @marcvanleeuwen5986
    @marcvanleeuwen5986 3 ปีที่แล้ว +9

    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.

    • @dominikwiegner7142
      @dominikwiegner7142 3 ปีที่แล้ว

      I like this comment very much.

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว

      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?

    • @marcvanleeuwen5986
      @marcvanleeuwen5986 2 ปีที่แล้ว

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

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว

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

  • @cesarbarrera9207
    @cesarbarrera9207 ปีที่แล้ว

    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 )

  • @pranki2254
    @pranki2254 3 ปีที่แล้ว +1

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

    • @leogama3422
      @leogama3422 2 ปีที่แล้ว

      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.

  • @roros2512
    @roros2512 3 ปีที่แล้ว

    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!

    • @roros2512
      @roros2512 3 ปีที่แล้ว +2

      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

  • @davidjames1684
    @davidjames1684 3 ปีที่แล้ว +5

    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.

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว +2

      "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.

  • @gastonsanda8784
    @gastonsanda8784 2 ปีที่แล้ว

    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.

  • @Davidicus000
    @Davidicus000 3 ปีที่แล้ว

    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

    • @erwinmulder1338
      @erwinmulder1338 3 ปีที่แล้ว +4

      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.

    • @offYears
      @offYears 3 วันที่ผ่านมา

      see the 'Word-RAM model' from L01

  • @pariveshplayson
    @pariveshplayson 3 ปีที่แล้ว +1

    Linearity doesn't need independence.

  • @tanveer867
    @tanveer867 2 ปีที่แล้ว

    How to handle badly skewed inputs for hashing ?

  • @peterjamali772
    @peterjamali772 3 ปีที่แล้ว +2

    Is this the same course as of 6.006 taught years back ??

  • @duosable
    @duosable 3 ปีที่แล้ว +18

    nvm, I thought it was a video about how to make Hashish

  • @__rahul005
    @__rahul005 2 ปีที่แล้ว

    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?

    • @TimothyRourke
      @TimothyRourke 2 ปีที่แล้ว +5

      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."

    • @leogama3422
      @leogama3422 2 ปีที่แล้ว +1

      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.

  • @tinytinoog
    @tinytinoog 3 ปีที่แล้ว +1

    does that make sense?
    it does

  • @colin398
    @colin398 2 ปีที่แล้ว

    28:30 the professor tosses out the idea of storing linked lists then 5 minutes later suggests that idea

    • @leogama3422
      @leogama3422 2 ปีที่แล้ว +2

      He tossed the idea of using a linked list for the hash table itself, not for the "buckets" of items in the table

    • @malikaremu2344
      @malikaremu2344 10 หลายเดือนก่อน

      why is linked list not suitable for hash table@@leogama3422

  • @OshNatour
    @OshNatour ปีที่แล้ว +1

    Can I see your bonker certificate please?

  • @lucifyer4486
    @lucifyer4486 3 ปีที่แล้ว +1

    Thank you for uploading this lecture!

  • @여늘-p6s
    @여늘-p6s 2 ปีที่แล้ว

    21:51

  • @edwin355160
    @edwin355160 3 ปีที่แล้ว

    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?

    • @RonaldABG
      @RonaldABG 2 ปีที่แล้ว

      Exactly, n is the number of keys

  • @johnw6021
    @johnw6021 3 ปีที่แล้ว

    man the explanation is so good, even makes a dumb like me understand

  • @somedude9057
    @somedude9057 2 ปีที่แล้ว

    So glad I found this

  • @sam_s3344
    @sam_s3344 3 ปีที่แล้ว +2

    Great video! Thank you MIT OCW :)
    18:37...how is it 10^9? Can someone please explain?

    • @JoeyFknD
      @JoeyFknD 3 ปีที่แล้ว +7

      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.

    • @cahakgeorge6208
      @cahakgeorge6208 2 ปีที่แล้ว +2

      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.

  • @sarthakkhandelwal9969
    @sarthakkhandelwal9969 3 ปีที่แล้ว +1

    Quite complicated to understand

  • @davidjames1684
    @davidjames1684 3 ปีที่แล้ว +5

    Usually when I think of hashing, I think of Waffle House, IHOP, McDonalds, Perkins... oh, maybe that is hash browning.

  • @farruhhabibullaev5316
    @farruhhabibullaev5316 3 ปีที่แล้ว

    Thanks, it makes sense. Finally!

  • @FitWithShamas
    @FitWithShamas 2 ปีที่แล้ว

    pretty good session !

  • @nteasushz
    @nteasushz 3 ปีที่แล้ว +3

    Best lectures ever

  • @lukea3836
    @lukea3836 2 ปีที่แล้ว

    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.

  • @kaipingli-mh3mw
    @kaipingli-mh3mw 3 ปีที่แล้ว

    thank you!

  • @TurboWindex
    @TurboWindex 3 ปีที่แล้ว +6

    When he wrote ≠ instead of != I was

    • @roros2512
      @roros2512 3 ปีที่แล้ว +2

      I thought you were !

  • @DanielBrownsan
    @DanielBrownsan 3 ปีที่แล้ว +2

    They need to teach camera operation at MIT.

  • @rishabhdwivedi2516
    @rishabhdwivedi2516 3 หลายเดือนก่อน

    15:30 screaming INDEX

  • @hyunkwak6569
    @hyunkwak6569 2 ปีที่แล้ว +1

    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?

    • @leogama3422
      @leogama3422 2 ปีที่แล้ว

      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.

    • @offYears
      @offYears 3 วันที่ผ่านมา

      Confused about this as well. I guess the universal condition (44:00) is that the hash function has a uniform probability distribution?

  • @beaver_stealer
    @beaver_stealer 3 ปีที่แล้ว

    Thanks man

  • @MrHorse16
    @MrHorse16 2 ปีที่แล้ว

    If U is large, then you is in charge

  • @moonbrush5
    @moonbrush5 2 ปีที่แล้ว

    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!

    • @malikaremu2344
      @malikaremu2344 10 หลายเดือนก่อน

      you dull then, what he said clearly makes sense

  • @davidjames1684
    @davidjames1684 3 ปีที่แล้ว +1

    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.

    • @erwinmulder1338
      @erwinmulder1338 3 ปีที่แล้ว +2

      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.

    • @davidjames1684
      @davidjames1684 3 ปีที่แล้ว

      @@erwinmulder1338 I was just making a point that this guy is misleading students.

    • @davidjames1684
      @davidjames1684 3 ปีที่แล้ว

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

    • @TimothyRourke
      @TimothyRourke 2 ปีที่แล้ว

      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.

    • @davidjames1684
      @davidjames1684 2 ปีที่แล้ว

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

  • @nanunsaram
    @nanunsaram 2 ปีที่แล้ว

    Great!!

  • @Bambledamble
    @Bambledamble 3 ปีที่แล้ว

    Very simple and easy to understand thank you

  • @kajetankasprzyk3019
    @kajetankasprzyk3019 10 หลายเดือนก่อน

    YEES, it makes sense!! :D you asked for it like 20 times xd

  • @rwfrench66GenX
    @rwfrench66GenX 2 ปีที่แล้ว +2

    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.

  • @willk7184
    @willk7184 3 ปีที่แล้ว +6

    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.

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว +7

      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.

    • @mickeymacke1780
      @mickeymacke1780 2 ปีที่แล้ว +1

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

    • @TimothyRourke
      @TimothyRourke 2 ปีที่แล้ว

      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.

  • @Array_of_objects
    @Array_of_objects ปีที่แล้ว

    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

  • @savetheoceancoin8700
    @savetheoceancoin8700 3 ปีที่แล้ว +5

    If U is large then U is in charge baby hahaha stay cool baby ; )

  • @paulkim1521
    @paulkim1521 2 ปีที่แล้ว

    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?

  • @sanjeen2503
    @sanjeen2503 2 ปีที่แล้ว +1

    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...

  • @hussienalsafi1149
    @hussienalsafi1149 2 ปีที่แล้ว

    🇺🇸🇺🇸🇺🇸🇺🇸🇺🇸😊😊😊😊😊😊

  • @shankar570
    @shankar570 2 ปีที่แล้ว +1

    sounds inexperienced for MIT standards

  • @99cya
    @99cya 3 ปีที่แล้ว +3

    someone asked what n means. seriously? are these guys from MIT? fuck me ...

    • @mytech6779
      @mytech6779 2 ปีที่แล้ว +3

      I think you missed some part of the context.

    • @anonymous.youtuber
      @anonymous.youtuber 2 ปีที่แล้ว +2

      As a good teacher you indulge the freshmen. He’s a great teacher.

    • @leogama3422
      @leogama3422 2 ปีที่แล้ว

      People can get distracted for a moment...

  • @mikekallas6329
    @mikekallas6329 2 ปีที่แล้ว +1

    Gibberish, right?

  • @PEACEKEEPER-mm3js
    @PEACEKEEPER-mm3js ปีที่แล้ว

    Low tech black board 🤣

  • @Ben-bg2lp
    @Ben-bg2lp 2 ปีที่แล้ว +1

    I was really surprise to realize MIT also have bad teachers.

  • @AsenAtanasoff1
    @AsenAtanasoff1 2 ปีที่แล้ว +4

    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?"

    • @lukea3836
      @lukea3836 2 ปีที่แล้ว +1

      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.

    • @AsenAtanasoff1
      @AsenAtanasoff1 2 ปีที่แล้ว

      ​@@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! :)

    • @lukea3836
      @lukea3836 2 ปีที่แล้ว

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

    • @moonbrush5
      @moonbrush5 2 ปีที่แล้ว

      Absolutely, he may be too smart but he is not a good teacher.

  • @kavourakos
    @kavourakos 3 ปีที่แล้ว

    "what is n?" gg