1 00:00:01,360 --> 00:00:05,340 - Hey, welcome to week 10 of CS124 2 00:00:05,340 --> 00:00:07,743 online data structures and algorithms. 3 00:00:08,650 --> 00:00:11,150 This week, we'll pick up where we left off 4 00:00:11,150 --> 00:00:13,710 with hash tables, and continue our studies 5 00:00:13,710 --> 00:00:18,060 with what's called linear probing, rehashing, 6 00:00:18,060 --> 00:00:20,603 quadratic probing, and double hashing. 7 00:00:21,730 --> 00:00:23,690 Now in contrast to separate chaining, 8 00:00:23,690 --> 00:00:25,400 which we saw last week, 9 00:00:25,400 --> 00:00:27,690 the so-called open addressing schemes 10 00:00:27,690 --> 00:00:30,590 take a different approach to resolving collisions 11 00:00:30,590 --> 00:00:31,963 and that is probing. 12 00:00:33,060 --> 00:00:36,640 So what happens with these collision resolution policies 13 00:00:36,640 --> 00:00:38,810 is that when a collision occurs, 14 00:00:38,810 --> 00:00:41,770 we probe our table to find an empty place 15 00:00:41,770 --> 00:00:43,763 to put the object we wish to insert. 16 00:00:45,390 --> 00:00:48,090 And if we do this in an orderly fashion, 17 00:00:48,090 --> 00:00:50,010 then we can find and remove objects 18 00:00:50,010 --> 00:00:53,113 in our hash table as well, using the same probing approach. 19 00:00:54,240 --> 00:00:58,000 Now, how we go about probing will vary, 20 00:00:58,000 --> 00:01:01,730 and we'll look at three policies that use probing. 21 00:01:01,730 --> 00:01:05,580 Linear probing, quadratic probing, and double hashing. 22 00:01:05,580 --> 00:01:08,780 They're all different, but they all use probing. 23 00:01:08,780 --> 00:01:10,640 Now, unlike separate chaining, 24 00:01:10,640 --> 00:01:13,500 where we handle hash collisions by extending the chains 25 00:01:13,500 --> 00:01:16,970 that is putting multiple objects in the same bucket, 26 00:01:16,970 --> 00:01:19,090 we don't do this with our open addressing 27 00:01:19,090 --> 00:01:20,900 or probing methods. 28 00:01:20,900 --> 00:01:21,900 In these cases, 29 00:01:21,900 --> 00:01:24,933 there can be only one object at a given location. 30 00:01:26,120 --> 00:01:29,250 And so that means we have capacity to deal with. 31 00:01:29,250 --> 00:01:31,490 So accordingly, we're going to have some method 32 00:01:31,490 --> 00:01:33,430 of growing our table in order to 33 00:01:33,430 --> 00:01:36,800 accommodate new objects when we exceed capacity 34 00:01:36,800 --> 00:01:39,573 or reach a certain threshold as the case may be. 35 00:01:41,010 --> 00:01:43,630 This is what rehashing is all about. 36 00:01:43,630 --> 00:01:46,260 We create a new larger table 37 00:01:46,260 --> 00:01:49,963 and then insert or rehash our objects into the new table. 38 00:01:52,200 --> 00:01:53,790 We'll implement linear probing 39 00:01:53,790 --> 00:01:55,890 and rehashing in C plus plus, 40 00:01:55,890 --> 00:01:57,780 but I'm going to leave the implementation 41 00:01:57,780 --> 00:02:01,460 of quadratic probing and double hashing up to you. 42 00:02:01,460 --> 00:02:02,940 This will be part of what you'll be doing 43 00:02:02,940 --> 00:02:04,393 in project number five. 44 00:02:05,600 --> 00:02:08,490 So let's get down to this week's business 45 00:02:08,490 --> 00:02:11,010 with the video lectures and the demonstrations. 46 00:02:11,010 --> 00:02:14,640 We'll begin with linear probing and as always, 47 00:02:14,640 --> 00:02:16,660 these videos and supplemental materials 48 00:02:16,660 --> 00:02:18,940 are posted here on Blackboard. 49 00:02:18,940 --> 00:02:22,250 And then there's some assigned reading in the textbook. 50 00:02:22,250 --> 00:02:25,380 But most of that reading you should have covered last week, 51 00:02:25,380 --> 00:02:27,033 the chapter on hash tables. 52 00:02:28,540 --> 00:02:30,800 At the end of the week, we'll have another quiz 53 00:02:30,800 --> 00:02:32,360 which will cover this week's material, 54 00:02:32,360 --> 00:02:34,940 and a little bit from last week. 55 00:02:34,940 --> 00:02:36,100 So that's all for now, 56 00:02:36,100 --> 00:02:38,630 and I'll see you on our yellow dig discussion board. 57 00:02:38,630 --> 00:02:39,823 Have fun, good luck.