1
00:00:01,140 --> 00:00:01,520
OK.

2
00:00:01,560 --> 00:00:03,630
Welcome back to another lecture.

3
00:00:03,900 --> 00:00:10,260
Today we are going to be going over a new type of data structure called a hash table.

4
00:00:10,950 --> 00:00:13,380
So let's go ahead and get started.

5
00:00:15,060 --> 00:00:16,350
So what is a hash table?

6
00:00:16,440 --> 00:00:21,990
Well, it is a data structure that's used with a technique called hashing.

7
00:00:22,710 --> 00:00:23,700
What is hashing?

8
00:00:23,700 --> 00:00:31,110
Well, hashing is a technique where you can take a collection of what we're calling keys like this over

9
00:00:31,110 --> 00:00:38,580
here and you put them through a special function like you can think of a C++ function that you've written

10
00:00:39,960 --> 00:00:44,010
and that's going to convert them into an index.

11
00:00:44,010 --> 00:00:52,080
So an index value will come out of this function and will tell us where to store the values that are

12
00:00:52,080 --> 00:00:53,460
associated with our keys.

13
00:00:55,190 --> 00:00:57,860
So let's look at this in a little bit more detail.

14
00:01:00,380 --> 00:01:01,760
So here's an example.

15
00:01:03,420 --> 00:01:06,210
We have these pictures right here.

16
00:01:07,630 --> 00:01:12,820
And I'm going to be referring to the thing on the left and no, as our key in the thing we want to store

17
00:01:13,090 --> 00:01:15,550
as the value in this specific example.

18
00:01:17,230 --> 00:01:19,360
So 12 would be a key.

19
00:01:19,570 --> 00:01:21,040
And this would be the value.

20
00:01:22,940 --> 00:01:24,500
Our hash function right here.

21
00:01:26,040 --> 00:01:28,620
Is going to be the key mod six.

22
00:01:28,920 --> 00:01:35,010
And I'm using six because it is the size of our table here.

23
00:01:35,850 --> 00:01:38,850
You can just think of this as an array for right now.

24
00:01:39,480 --> 00:01:41,640
So these are the values being stored at the array.

25
00:01:42,810 --> 00:01:45,490
And so these are color coded right now.

26
00:01:45,510 --> 00:01:50,940
Let's go ahead and follow where they are going from the beginning to the hash function to where it's

27
00:01:50,940 --> 00:01:51,330
stored.

28
00:01:52,510 --> 00:01:57,040
So I have 12, which is my key in the value that Jeff is the value I want to store.

29
00:01:57,910 --> 00:02:02,080
So 12 models, six is zero zero remainder.

30
00:02:03,070 --> 00:02:05,470
So I go to index zero and I store Jeff.

31
00:02:07,280 --> 00:02:14,450
Next, I look at how the key value 23, 23 months six is going to be five.

32
00:02:14,930 --> 00:02:17,600
So I store HAL right here at Index five.

33
00:02:18,470 --> 00:02:19,520
Same thing with Bob.

34
00:02:19,550 --> 00:02:21,950
Eight months, six or two.

35
00:02:22,890 --> 00:02:25,200
I store Bob here at index to.

36
00:02:27,740 --> 00:02:32,810
So this looks, you know, this is great and all, but these kind of nicely just ended up.

37
00:02:34,260 --> 00:02:41,910
In these spots, all kind of separated distance from each other, but you're you won't be wondering,

38
00:02:42,240 --> 00:02:45,150
well, what happens if we had something?

39
00:02:46,440 --> 00:02:48,090
That was, let's say.

40
00:02:50,150 --> 00:02:57,470
Maybe 18, like how was 18 had a key 18 instead of 23.

41
00:02:58,430 --> 00:03:00,140
So 18 mod six.

42
00:03:00,800 --> 00:03:01,700
Well, that's zero.

43
00:03:02,060 --> 00:03:04,010
We already inserted Jeff here zero.

44
00:03:04,370 --> 00:03:06,650
So now we want to insert how at zero.

45
00:03:08,200 --> 00:03:12,460
This is something that we're going to call a collision and we need to resolve it.

46
00:03:13,000 --> 00:03:13,480
So.

47
00:03:16,640 --> 00:03:21,590
This is what we're talking about, two different values, something that's already here in two different

48
00:03:21,590 --> 00:03:23,990
values, one to hash to the same spot.

49
00:03:24,090 --> 00:03:28,760
The second one, we need to figure out what to do with that second value or.

50
00:03:29,980 --> 00:03:35,170
X and value, whatever it is, there's there's something already here, we're going to refer to it as

51
00:03:35,170 --> 00:03:37,330
a collision or something else is trying to be stored there.

52
00:03:40,590 --> 00:03:46,290
So the technique that we are going to be talking about in this lecture is changing.

53
00:03:47,350 --> 00:03:54,690
This is kind of one of the most rudimentary techniques, but it's great for explaining and gives us

54
00:03:54,690 --> 00:03:58,410
a chance to implement some things we've already learned.

55
00:03:58,420 --> 00:04:09,930
So this specific strategy uses appending to a linked list as a coalition resolution solution.

56
00:04:11,310 --> 00:04:13,700
So you can look at this diagram right here.

57
00:04:14,640 --> 00:04:18,380
Let's say that Jeff ended up right here.

58
00:04:19,910 --> 00:04:32,150
And so it has to this first value, I think Jeff was index zero, and then we had HAL with our hypothetical

59
00:04:32,180 --> 00:04:35,540
18 key instead of 23.

60
00:04:35,990 --> 00:04:37,880
And he attached to the same thing here.

61
00:04:37,910 --> 00:04:43,010
Well, what I'm going to have to do is I'm going to have to append a HAL to a linked list.

62
00:04:43,010 --> 00:04:44,570
So pretend this part's not here yet.

63
00:04:45,780 --> 00:04:50,190
We haven't added that yet, but I did add a note right here, and I put Hal right here.

64
00:04:51,630 --> 00:04:53,610
Jeff, here and now how to put how here.

65
00:04:54,480 --> 00:04:59,910
So that is changing, we're creating mailing lists to deal with collisions, and so as we get more and

66
00:04:59,910 --> 00:05:03,360
more collisions, we keep building our linked lists down like this.

67
00:05:04,040 --> 00:05:09,750
And these were just hypothetical other spots in which I had to insert something in right here.

68
00:05:09,750 --> 00:05:12,230
I left a pointer on here.

69
00:05:12,270 --> 00:05:16,860
You notice I don't have any pointers sticking off of these boxes.

70
00:05:18,420 --> 00:05:23,850
You can think of the link list as maybe I should have deleted this pointer, but it is now pointing

71
00:05:23,850 --> 00:05:24,340
to no.

72
00:05:24,360 --> 00:05:26,700
So hopefully you aren't confused by that.

73
00:05:26,710 --> 00:05:28,830
Just wanted to point that out because I just noticed it.

74
00:05:30,350 --> 00:05:33,170
So this is the essential idea of chaining.

75
00:05:34,700 --> 00:05:39,110
Let's go through an example just to really hammer that theory in there.

76
00:05:39,380 --> 00:05:46,610
So I'm going to have a hash function that's going to be in our input mod for and this is going to be

77
00:05:46,610 --> 00:05:48,320
a list of our input here.

78
00:05:48,330 --> 00:05:49,640
So a start left to right.

79
00:05:51,150 --> 00:05:56,430
So to start out with seven, so we're going to seven mod for.

80
00:05:58,550 --> 00:06:00,410
We see that that ends up here.

81
00:06:01,440 --> 00:06:02,190
At three.

82
00:06:04,060 --> 00:06:05,470
I'm going to do 10 more for.

83
00:06:07,160 --> 00:06:11,180
Ten more for is, too, so we put it into four month for.

84
00:06:12,380 --> 00:06:13,460
That's going to be zero.

85
00:06:14,630 --> 00:06:15,860
13 mod for.

86
00:06:17,130 --> 00:06:21,750
It's going to be at once, you see that it just naturally kind of filled this up, that's not always

87
00:06:21,750 --> 00:06:22,560
going to be the case.

88
00:06:22,560 --> 00:06:27,000
We might have encountered a collision by now, but it just so happens that they all went to an empty

89
00:06:27,000 --> 00:06:27,390
spot.

90
00:06:27,390 --> 00:06:32,580
And this original refer to this as an array right now.

91
00:06:32,580 --> 00:06:37,620
And then these are linked lists stored here at all these points and they're coming off this direction.

92
00:06:37,650 --> 00:06:39,180
So think of it like that.

93
00:06:40,170 --> 00:06:41,280
So let's go to our next value.

94
00:06:41,280 --> 00:06:42,060
48.

95
00:06:42,120 --> 00:06:47,940
We know we're going to have a collision because our air is filled up with values already at the first

96
00:06:47,940 --> 00:06:48,270
spot.

97
00:06:50,420 --> 00:06:55,790
So that gets hashed to zero, and since we have a collision, we have to store it here in our link listens

98
00:06:55,790 --> 00:06:58,460
first node, go to the next one three.

99
00:06:59,910 --> 00:07:01,350
Three, get stored over here.

100
00:07:02,160 --> 00:07:05,040
Next one nine gets stored here.

101
00:07:05,880 --> 00:07:08,700
Next one will get stored here.

102
00:07:08,700 --> 00:07:14,340
And then of course, 11 one four is going to be three and it just goes in the last spot here.

103
00:07:15,780 --> 00:07:25,350
OK, so what if we think about the efficiency of these operations, we've just been looking at inserts

104
00:07:25,350 --> 00:07:25,950
so far.

105
00:07:26,200 --> 00:07:32,610
But let's look at insertion and search, so insertion.

106
00:07:32,760 --> 00:07:41,940
If we consider an as the size of our input for this insertion insertion search, we're going to be considering

107
00:07:41,940 --> 00:07:43,590
in as input size.

108
00:07:44,520 --> 00:07:49,530
The insertion would be cost and time for the best and worst case.

109
00:07:50,250 --> 00:07:50,910
Why is that?

110
00:07:50,940 --> 00:07:51,930
Well, let's take a look.

111
00:07:52,380 --> 00:08:02,220
The best case is the case in which we have an open spot, and it just so happens that our item, our

112
00:08:02,220 --> 00:08:02,760
key.

113
00:08:03,860 --> 00:08:05,720
It's hashed straight to that spot.

114
00:08:06,950 --> 00:08:10,700
So let's think of like our previous example here, we're just going to say that.

115
00:08:12,100 --> 00:08:21,850
Our numbers here, we didn't have a pair like 18 and how like that we're just storing the numbers like

116
00:08:21,850 --> 00:08:23,230
we did in this example here.

117
00:08:23,240 --> 00:08:25,510
So the keys are the values as well.

118
00:08:25,510 --> 00:08:27,280
So let's just roll with that for now.

119
00:08:28,830 --> 00:08:30,400
Think about it that way to simplify it.

120
00:08:30,720 --> 00:08:39,120
And so if there's an open spot here, let's say, for seven or whatever.

121
00:08:39,930 --> 00:08:44,280
I'm just going to put it in this arbitrary location, but it has a hash up to here and it's open.

122
00:08:45,090 --> 00:08:52,290
We know that indexing our array is going to be a cost and time operation.

123
00:08:53,160 --> 00:09:01,530
And we're also just going to say that computing the hash value is going to be cost and time operation.

124
00:09:01,530 --> 00:09:06,030
Like, let's say it's just an integer mod, some other integer like that simple example we've already

125
00:09:06,030 --> 00:09:08,520
been looking at now, that is Constantine.

126
00:09:09,030 --> 00:09:15,210
So you have constant time plus cost and time that's just going to be cost in time because we know that

127
00:09:15,210 --> 00:09:21,690
we're simplifying it down to the term of the average magnitude, and they're just two of 1s.

128
00:09:21,690 --> 00:09:24,900
So a one plus of one is over one.

129
00:09:25,230 --> 00:09:29,370
So we're considering that for the best case, what would the worst case be?

130
00:09:29,400 --> 00:09:37,470
Well, the worst case, we're going to actually say that for some reason, our array is just one.

131
00:09:39,700 --> 00:09:41,020
It just the size one.

132
00:09:41,470 --> 00:09:45,760
So array of size one, and then we're just storing a big link list there.

133
00:09:45,760 --> 00:09:48,700
So every single time our.

134
00:09:51,250 --> 00:09:53,680
Input comes in, it's a collision.

135
00:09:54,580 --> 00:10:01,690
And so in that case, if you think about it, we're basically going to end up with a linked list equivalent

136
00:10:01,690 --> 00:10:06,940
to the the size of our linked list is going to be equivalent to the size of our input because it's just

137
00:10:06,940 --> 00:10:08,620
going to collide every single time.

138
00:10:08,620 --> 00:10:13,030
So we're going to have a link list starting with the first item here and then going all the way down,

139
00:10:13,030 --> 00:10:13,900
up to end.

140
00:10:16,340 --> 00:10:23,690
But the thing is, and we know this from doing linguists and talking about the complexity of insertion

141
00:10:24,230 --> 00:10:31,460
into linguists specifically right now in this example and the things I've been referring to is unordered.

142
00:10:31,460 --> 00:10:38,930
So we're not hearing about the order and we know that insertion into an unaudited linked list is caused

143
00:10:38,930 --> 00:10:41,480
in time so we can just append it to the end.

144
00:10:42,980 --> 00:10:52,310
So now we can say that we add that cost, which is of one for computing the hash and then inserting

145
00:10:52,310 --> 00:10:53,780
into a linked list.

146
00:10:54,350 --> 00:11:01,520
We also can say we'll go ahead and say that it's all one to index to this value and then another old

147
00:11:01,520 --> 00:11:08,080
one to add it to our linked list to insert it into our own link list.

148
00:11:08,090 --> 00:11:09,460
So those are all of one.

149
00:11:09,470 --> 00:11:11,030
So it's still going to be of one.

150
00:11:11,030 --> 00:11:14,630
And that's why I said insertions of one for best and worst case.

151
00:11:17,350 --> 00:11:23,170
So if it's all won for best and worst case, you see, have an average case down here, turn about to

152
00:11:23,170 --> 00:11:26,140
get to, it's going to be over one for the average case as well.

153
00:11:28,680 --> 00:11:33,270
And so you're kind of thinking, OK, well, we didn't talk about much of our best and worst case before.

154
00:11:33,780 --> 00:11:35,070
Why are we talking about this now?

155
00:11:35,100 --> 00:11:43,290
Well, later on, as I said before, we're going to get more into the details of going deeper into algorithm

156
00:11:43,290 --> 00:11:44,040
analysis.

157
00:11:44,820 --> 00:11:51,780
And although we're kind of simplifying things now, I want to start introducing a little bit more just

158
00:11:51,780 --> 00:11:55,530
so we can look at this hash table in more detail as far as its efficiency.

159
00:11:56,460 --> 00:12:02,400
So there are three different cases that we need to consider when we look deeper into algorithm analysis

160
00:12:02,400 --> 00:12:09,390
and in the industry, we kind of just use that big oh, like I was saying, and that is actually referring

161
00:12:09,390 --> 00:12:13,020
to the average case most of the time they've simplified it.

162
00:12:14,280 --> 00:12:19,230
You know, I said that we're not going to go over these other things you might have heard of, like

163
00:12:19,230 --> 00:12:25,110
Big Omega and Theta Theta being the average case.

164
00:12:25,470 --> 00:12:27,300
We're just going to still call it big.

165
00:12:27,540 --> 00:12:31,530
And most of the time, we're concerned and wanting to know about the average case.

166
00:12:32,630 --> 00:12:36,710
Because it's not going to give me the best case all the time and worst case, let's just simplify it

167
00:12:36,710 --> 00:12:38,930
to the average case, that's why people care about that.

168
00:12:39,500 --> 00:12:42,230
And the big oh, most of the time they're referring to the average case.

169
00:12:42,950 --> 00:12:45,590
So just repeating that again, just so we're all clear.

170
00:12:46,520 --> 00:12:49,050
And now I'm introducing these cases.

171
00:12:49,070 --> 00:12:57,620
So let's think about where we have a more complex average case and start with the search.

172
00:12:58,010 --> 00:12:58,730
So let's start out.

173
00:12:58,730 --> 00:13:04,280
Actually, let's go first over the worst and best searching for something in our house table.

174
00:13:06,250 --> 00:13:10,080
Have these kind of out of order, but yeah, let's actually let's start at this like we did over here

175
00:13:10,080 --> 00:13:16,050
with the best case, the best case to search for something is going to be a cost and time operation.

176
00:13:16,650 --> 00:13:17,610
And why is that?

177
00:13:18,060 --> 00:13:24,450
Well, when we search, I've only talked about insertion now, but it's similar when we search for something

178
00:13:24,450 --> 00:13:25,290
in our hash table.

179
00:13:25,680 --> 00:13:30,210
We're going to use that hash function on our input.

180
00:13:30,210 --> 00:13:32,060
So I'm going to use this example.

181
00:13:32,070 --> 00:13:40,260
Like I said, I would use of just this simple array of numbers like this where we don't have a different

182
00:13:40,260 --> 00:13:40,960
value.

183
00:13:40,980 --> 00:13:43,920
We are hashing on this and storing this.

184
00:13:44,970 --> 00:13:55,050
So if I am now looking it up and I want to look up seven, for example, remember I said it kind of

185
00:13:55,050 --> 00:13:56,550
just as a random location.

186
00:13:56,550 --> 00:14:08,220
Let's say it has two here because, you know, we have some arbitrary random hash function and the operation

187
00:14:08,220 --> 00:14:13,620
of hashing that to get it, you know, is going to be overrun like we talked about.

188
00:14:13,950 --> 00:14:18,930
And now we can use that hash value just like we did to insert to search it.

189
00:14:19,470 --> 00:14:24,870
So we're going to use that value if we want to find seven and we get the hash value of that, we're

190
00:14:24,870 --> 00:14:28,800
going to look at that index to find what we stored there.

191
00:14:29,400 --> 00:14:35,010
So the hash version computes the same value as it did when we inserted.

192
00:14:35,190 --> 00:14:37,110
And that's how we can look it up at that index.

193
00:14:37,110 --> 00:14:40,800
So it's kind of like a dictionary looking something up like that.

194
00:14:41,190 --> 00:14:47,370
And we know that looking it up and which is the operation of indexing it is also constant time.

195
00:14:47,700 --> 00:14:50,160
So we have that constant time, Wisconsin time.

196
00:14:50,700 --> 00:14:57,660
It's going to be constant time of one for the best case where it's stored right here in an open spot.

197
00:14:59,630 --> 00:15:07,610
OK, so now let's look at the worst case, the worst case.

198
00:15:08,390 --> 00:15:14,370
So let's go back to that example where it was just sighs one.

199
00:15:16,140 --> 00:15:21,480
And we don't really need a sample, let's just do that, though, anyways, so we have this huge link

200
00:15:21,480 --> 00:15:30,380
list coming up here that size and well, we do our constant time hash to.

201
00:15:31,140 --> 00:15:35,070
And then a cost and time index with that has to get to this index.

202
00:15:36,330 --> 00:15:41,820
But let's say that our thing we're looking for is stored at the very end of the linked list.

203
00:15:42,810 --> 00:15:47,970
Well, we don't really know where it is because it's not, you know, we're not able to hash the link

204
00:15:47,970 --> 00:15:48,870
list values.

205
00:15:49,200 --> 00:15:51,150
So we actually just have to.

206
00:15:51,330 --> 00:15:54,150
So I don't mean hash mean to index the link list values.

207
00:15:55,140 --> 00:16:02,160
We have to sequentially search through the link to list all the way until we find our item, which I

208
00:16:02,160 --> 00:16:03,030
said is at the end.

209
00:16:03,030 --> 00:16:07,770
So we're going to have to search the whole list of in items to the end.

210
00:16:07,770 --> 00:16:12,360
So that's why we're going to call worst case Bago of any.

211
00:16:14,640 --> 00:16:17,280
So what about this average case that I just mentioned?

212
00:16:17,790 --> 00:16:24,930
Well, for searching, it gets a little bit more complicated and we're not going to get super deep into

213
00:16:24,930 --> 00:16:33,780
it, but I don't want to just throw a big show out there for you to look at without explaining anything.

214
00:16:33,790 --> 00:16:35,370
So let's take a look at this.

215
00:16:36,900 --> 00:16:39,180
So the average case analysis of chaining.

216
00:16:40,430 --> 00:16:47,270
We are going to still say that n equals the size of the input, but I'm going to use another variable

217
00:16:47,270 --> 00:16:50,960
here called M, and that's going to be the size of the hash table array.

218
00:16:50,960 --> 00:16:58,700
So like this right here and I'm not necessarily going to be using this example specifically.

219
00:16:58,700 --> 00:17:03,770
So don't try and count things quite yet in here, like numbers of squares or anything or make assumptions.

220
00:17:03,770 --> 00:17:04,520
I just wanted it.

221
00:17:04,520 --> 00:17:05,810
Here is a visual reference.

222
00:17:06,740 --> 00:17:14,110
So M is going to be the size of the array and in is, however, many values we have coming in like,

223
00:17:14,120 --> 00:17:15,350
for example, here.

224
00:17:15,620 --> 00:17:22,850
One two three four five six seven eight nine We had nine values, so in could be, you know, the size

225
00:17:22,850 --> 00:17:23,780
of our input like that.

226
00:17:25,500 --> 00:17:31,110
A new term that I want to introduce is something called the load factor, which I'm going to let the

227
00:17:31,110 --> 00:17:40,080
load factor be represented by Alpha, and that is going to equal the size of the input over the size

228
00:17:40,080 --> 00:17:41,310
of our hash table array.

229
00:17:43,730 --> 00:17:50,400
And so we can think about our input having to be distributed over these M slots.

230
00:17:50,420 --> 00:17:56,060
And there, of course, being some collisions, you know, if we have all our input coming in gets distributed

231
00:17:56,060 --> 00:18:05,270
over time slots is going to have some length lists and I'm going to be thinking about the size of those

232
00:18:05,270 --> 00:18:10,040
link lists as being represented by this load factor.

233
00:18:11,520 --> 00:18:11,920
OK.

234
00:18:12,090 --> 00:18:13,770
So, Alpha, the load factor.

235
00:18:16,500 --> 00:18:22,110
So when we look at the average case of searching, we're going to think about competing or hash function

236
00:18:22,110 --> 00:18:25,980
like we were talking about before, which is going to be that old one.

237
00:18:27,150 --> 00:18:35,070
And then we are going to have to add the time it takes and total to search for our values.

238
00:18:35,070 --> 00:18:44,430
So we're going to index to the value in the array, the index value, and then we're going to have to

239
00:18:44,430 --> 00:18:51,270
potentially look through a certain size of link list, which I'm thinking of about this distribution

240
00:18:51,270 --> 00:18:58,620
of the link lists being similar in size and thinking about, you know, in this average case of this

241
00:18:59,040 --> 00:19:05,370
length of the link list, I'm going to let Alfa be representative of that, which is our load factor

242
00:19:05,370 --> 00:19:06,540
we're talking about here.

243
00:19:08,040 --> 00:19:14,490
So that's why I have this alfa there, because we're going to have to search through a given size of

244
00:19:14,790 --> 00:19:17,220
link list based on our load factor.

245
00:19:19,040 --> 00:19:24,230
And then you're probably wondering, OK, well, I could you know, why I need really simplify this?

246
00:19:24,500 --> 00:19:31,160
Wouldn't this just be, you know, oh, of alpha, because we have this like cost and time operation

247
00:19:31,160 --> 00:19:34,010
and then we care about the largest terms.

248
00:19:34,010 --> 00:19:40,280
So why wouldn't this answer here be big go of alpha, which is the load factor?

249
00:19:41,440 --> 00:19:44,680
And if you did think that that's good thinking.

250
00:19:45,430 --> 00:19:53,560
But the reason why is because we're not really sure what this load factor is in relation to one, it

251
00:19:53,560 --> 00:20:00,250
could be greater than one, you know, or it could be equal to one or it could be less than one.

252
00:20:01,420 --> 00:20:03,820
So think about this in over in.

253
00:20:05,670 --> 00:20:13,020
You're curious about the size of our input related to the size of the array.

254
00:20:13,800 --> 00:20:21,690
So our input could be one size one in our input could be size a thousand and we could have an array

255
00:20:21,690 --> 00:20:26,610
that was this size or we could have array that was like a million size a million.

256
00:20:27,480 --> 00:20:34,650
Because of that, we have variable values that can be stored in this A.

257
00:20:35,620 --> 00:20:41,050
So that's a what I should say instead, is this a can represent different values that are less than

258
00:20:41,050 --> 00:20:42,430
equal to or greater than one.

259
00:20:42,470 --> 00:20:48,070
And so if it is less than one, we don't want to just completely forget about this one because it becomes

260
00:20:48,070 --> 00:20:48,910
significant.

261
00:20:49,780 --> 00:20:55,870
Now, the largest thing of magnitude is is potentially bigger here than here.

262
00:20:56,200 --> 00:20:57,700
And so we don't want to get rid of it.

263
00:20:58,300 --> 00:21:00,360
So that's why we're leaving this one.

264
00:21:00,370 --> 00:21:04,540
Plus a big show of one plus sorry, not a alpha.

265
00:21:06,010 --> 00:21:08,650
So hopefully that explains it a little bit to you.

266
00:21:09,070 --> 00:21:15,790
We are going to get deeper into this, as I said, and I will continue to say with our algorithm analysis

267
00:21:15,790 --> 00:21:23,050
later on, but I didn't want to completely just leave this out when we're thinking about how efficient

268
00:21:23,050 --> 00:21:26,470
this type of hashing method is.

269
00:21:27,460 --> 00:21:29,650
So hopefully that explain it OK for you.

270
00:21:29,950 --> 00:21:38,770
We are going to be implementing this in an interesting project coming up right after this.

271
00:21:38,770 --> 00:21:40,870
So that's why I wanted to.

272
00:21:41,230 --> 00:21:50,350
I wanted to use chaining as the initial hashing thing we talk about and hash table topic because we

273
00:21:50,350 --> 00:21:57,250
can use our linked lists and get some practice implementing implementing them in association with another

274
00:21:57,250 --> 00:21:58,930
data structure, this hash table.

275
00:22:00,100 --> 00:22:04,000
OK, so hopefully you enjoyed that lecture and I will see you in the next video.