1
00:00:00,960 --> 00:00:02,060
- [Instructor] Okay, so now that we have

2
00:00:02,060 --> 00:00:05,420
a working basic Hash Table,

3
00:00:05,420 --> 00:00:08,850
we're going to modify
that Hash table class

4
00:00:08,850 --> 00:00:12,990
to handle objects that have a key field.

5
00:00:12,990 --> 00:00:15,020
So in the first iteration

6
00:00:15,020 --> 00:00:16,820
that I showed in the previous video,

7
00:00:16,820 --> 00:00:18,930
we were just passing in strings

8
00:00:18,930 --> 00:00:21,240
and putting strings into a Hash table.

9
00:00:21,240 --> 00:00:25,500
But for your projects, and
for a more realistic example,

10
00:00:25,500 --> 00:00:28,090
we want to be able to pass in an object

11
00:00:28,090 --> 00:00:30,550
that we want to insert
into our Hash table.

12
00:00:30,550 --> 00:00:34,020
And so in order to do that,
our Hash table needs to be able

13
00:00:34,020 --> 00:00:36,880
to find the appropriate key.

14
00:00:36,880 --> 00:00:40,700
And so just like we
passed in a Hash function,

15
00:00:40,700 --> 00:00:43,320
so that the Hash table
could use that function,

16
00:00:43,320 --> 00:00:48,130
we're going to allow for passing
in of a get key function.

17
00:00:48,130 --> 00:00:50,350
That's going to be used by the Hash table

18
00:00:50,350 --> 00:00:52,432
to retrieve the key from objects

19
00:00:52,432 --> 00:00:55,350
of the type that I defined here.

20
00:00:55,350 --> 00:00:57,913
And when it comes time to be your turn,

21
00:00:58,800 --> 00:01:02,290
you'll use objects of your custom class.

22
00:01:02,290 --> 00:01:05,490
So, first what I did,'

23
00:01:05,490 --> 00:01:09,550
was I created a very
simple dictionary class.

24
00:01:09,550 --> 00:01:11,110
It has two private members.

25
00:01:11,110 --> 00:01:15,140
Your objects obviously
will have five or more

26
00:01:15,140 --> 00:01:18,160
but this has two, a word and a definition,

27
00:01:18,160 --> 00:01:19,700
those are the private members.

28
00:01:19,700 --> 00:01:21,363
This is called dictionary item.

29
00:01:22,560 --> 00:01:25,300
There's a constructor that takes
the word and the definition

30
00:01:25,300 --> 00:01:30,000
and assigns the appropriate
values to the private members.

31
00:01:30,000 --> 00:01:34,590
There are getters and setters,
get word, get definition.

32
00:01:34,590 --> 00:01:38,000
There are setters, set
word and set definition.

33
00:01:38,000 --> 00:01:39,620
And then these should look familiar

34
00:01:39,620 --> 00:01:41,430
because you've done these in your classes.

35
00:01:41,430 --> 00:01:45,610
This is a function that overrides

36
00:01:45,610 --> 00:01:49,450
the stream insertion operator
for pretty printing objects,

37
00:01:49,450 --> 00:01:51,450
just prints the word and the definition.

38
00:01:52,770 --> 00:01:55,753
And then we also have this function.

39
00:01:56,590 --> 00:02:00,170
Which is used to compare
two dictionary items.

40
00:02:00,170 --> 00:02:01,130
Are they the same?

41
00:02:01,130 --> 00:02:04,361
And the method that it uses is,

42
00:02:04,361 --> 00:02:08,740
it checks this key value
word and if they're the same,

43
00:02:08,740 --> 00:02:10,070
then the objects are equal.

44
00:02:10,070 --> 00:02:12,210
And again, you've done
something very similar to this

45
00:02:12,210 --> 00:02:14,363
in your own custom class.

46
00:02:15,610 --> 00:02:18,943
And so now we'll modify
our Hash table accordingly.

47
00:02:19,900 --> 00:02:21,880
So what do we need to do?

48
00:02:21,880 --> 00:02:25,937
Well, we're going to
need a new private member

49
00:02:25,937 --> 00:02:27,533
that's gonna be a function.

50
00:02:30,910 --> 00:02:35,323
And that function is
going to return a string,

51
00:02:37,750 --> 00:02:40,263
when provided with a Hashable.

52
00:02:43,810 --> 00:02:45,260
And we'll call that, get key.

53
00:02:48,640 --> 00:02:52,363
And then we need to add this
exact same thing to our,

54
00:02:53,890 --> 00:02:57,443
function signature for our
constructor, we'll do that here.

55
00:02:58,500 --> 00:03:03,500
And so now, when we want to
instantiate a Hash table object

56
00:03:03,560 --> 00:03:05,720
we pass it the table size,

57
00:03:05,720 --> 00:03:08,180
we pass it that get key function,

58
00:03:08,180 --> 00:03:10,083
and we pass it the Hash function.

59
00:03:11,010 --> 00:03:12,890
And we also need to assign

60
00:03:14,220 --> 00:03:18,810
the get key function that we
passed in to the constructor.

61
00:03:18,810 --> 00:03:22,403
Get key, to the get key member.

62
00:03:25,900 --> 00:03:29,450
Alright, so that's our
modified constructor.

63
00:03:29,450 --> 00:03:34,320
Now we have to modify,
insert, find and remove.

64
00:03:34,320 --> 00:03:36,680
And the modifications are very simple.

65
00:03:36,680 --> 00:03:40,270
So in our earlier example,
we were passing in a string

66
00:03:40,270 --> 00:03:44,120
as a Hashable, and it was just
that value, just the string.

67
00:03:44,120 --> 00:03:47,100
We were inserting strings
into a Hash table.

68
00:03:47,100 --> 00:03:49,740
So, now the only thing that's
really gonna be a Hashable

69
00:03:49,740 --> 00:03:51,440
is what we're passing into insert.

70
00:03:52,600 --> 00:03:53,863
And we'll call that item.

71
00:03:54,880 --> 00:03:59,330
And then insert needs to
know how to find the key.

72
00:03:59,330 --> 00:04:01,870
So we just get that key.

73
00:04:01,870 --> 00:04:06,063
So standard string key,

74
00:04:07,050 --> 00:04:12,050
equals get key item.

75
00:04:14,560 --> 00:04:16,853
So now we passed in an object,

76
00:04:18,160 --> 00:04:23,030
we call get key to get
the key from that object,

77
00:04:23,030 --> 00:04:26,220
and then we passed that
key to the Hash function

78
00:04:26,220 --> 00:04:29,170
along with the table
size to get the index.

79
00:04:29,170 --> 00:04:33,813
And then we insert the item, okay?

80
00:04:36,670 --> 00:04:37,563
So far so good.

81
00:04:38,510 --> 00:04:40,643
Now let's modify, find and remove.

82
00:04:41,490 --> 00:04:44,380
Now, as you recall, before we
were just passing in a string

83
00:04:44,380 --> 00:04:46,970
we were adding strings to our Hash table.

84
00:04:46,970 --> 00:04:50,850
Now we're passing in objects,
but when we find and remove

85
00:04:50,850 --> 00:04:53,100
we don't know if that object exists.

86
00:04:53,100 --> 00:04:55,783
So we're going to pass a string,

87
00:04:57,200 --> 00:04:58,173
to find,

88
00:05:00,590 --> 00:05:02,023
that will serve as the key.

89
00:05:02,930 --> 00:05:05,800
We don't need to use get key here

90
00:05:05,800 --> 00:05:07,370
because we're just looking to see

91
00:05:07,370 --> 00:05:09,260
does this key exist in the table?

92
00:05:09,260 --> 00:05:11,560
We don't know if there's
an object there yet.

93
00:05:11,560 --> 00:05:14,267
But if we do find an object,

94
00:05:14,267 --> 00:05:18,060
if there is something here at table index,

95
00:05:18,060 --> 00:05:21,123
whatever that index is that
calculated index from the key,

96
00:05:22,006 --> 00:05:24,903
then we need to perform
a comparison, get key,

97
00:05:26,255 --> 00:05:28,263
to see if we found a match.

98
00:05:31,270 --> 00:05:35,830
And if we do we return
the D referenced pointer

99
00:05:35,830 --> 00:05:38,670
to the object and if we don't find it

100
00:05:38,670 --> 00:05:41,740
then we return all up,
that's all the same.

101
00:05:41,740 --> 00:05:44,180
But we need to make the same
modification for remove,

102
00:05:44,180 --> 00:05:46,463
so this becomes standard string.

103
00:05:48,880 --> 00:05:50,830
And then if we find an object

104
00:05:50,830 --> 00:05:54,826
we wanna perform the comparison
on the keys so we get key

105
00:05:54,826 --> 00:05:56,453
on this object,

106
00:05:58,900 --> 00:06:01,000
that we get from the D referenced pointer,

107
00:06:02,390 --> 00:06:04,250
and everything else is the same.

108
00:06:04,250 --> 00:06:07,700
So now we've completed our modifications

109
00:06:07,700 --> 00:06:12,700
of our Hash table class so
that it can handle objects.

110
00:06:13,920 --> 00:06:17,030
Print table doesn't change
that's all the same.

111
00:06:17,030 --> 00:06:19,660
Everything else is the same, all right.

112
00:06:19,660 --> 00:06:24,450
So I prepared a little
demo here to test this

113
00:06:24,450 --> 00:06:27,653
and to show you how we
implement the get key function.

114
00:06:28,500 --> 00:06:31,283
So here's the get key function.

115
00:06:32,210 --> 00:06:33,700
And you'll recall that we're working

116
00:06:33,700 --> 00:06:37,620
with this class of dictionary items.

117
00:06:37,620 --> 00:06:41,560
And recall also that each dictionary item

118
00:06:41,560 --> 00:06:45,760
had a word and a definition,
and the word is the key value.

119
00:06:45,760 --> 00:06:47,780
Okay, that's our unique field

120
00:06:47,780 --> 00:06:50,120
in our collection of dictionary items.

121
00:06:50,120 --> 00:06:53,700
So we write this function
that returns a standard string

122
00:06:53,700 --> 00:06:55,570
we call it get key.

123
00:06:55,570 --> 00:06:59,140
It takes a dictionary item
D, and then calls the getter

124
00:06:59,140 --> 00:07:04,140
get word on that dictionary
item and returns that word.

125
00:07:04,150 --> 00:07:06,730
So that's how we get key.

126
00:07:06,730 --> 00:07:09,900
And that's what we pass
in to our Hash table.

127
00:07:09,900 --> 00:07:13,010
So we have here a constant

128
00:07:13,010 --> 00:07:16,213
that's our table size 17, 17 is prime.

129
00:07:17,150 --> 00:07:20,482
And then when we
instantiate our Hash table,

130
00:07:20,482 --> 00:07:23,770
our Hashable is a dictionary item.

131
00:07:23,770 --> 00:07:27,540
We'll call this Hash table,
we're passing in the table size.

132
00:07:27,540 --> 00:07:31,000
Now we're also passing
in the get key function.

133
00:07:31,000 --> 00:07:34,490
That's this function here
and our Hashing function.

134
00:07:34,490 --> 00:07:37,173
So we're passing in two
functions as required.

135
00:07:38,270 --> 00:07:39,930
And then what we're doing,

136
00:07:39,930 --> 00:07:43,670
is we're creating eight
different dictionary items.

137
00:07:43,670 --> 00:07:47,090
And again, the dictionary
entry is just a word

138
00:07:47,090 --> 00:07:49,470
that's our key and the definitions.

139
00:07:49,470 --> 00:07:52,990
A dentist is a person
who takes care of teeth.

140
00:07:52,990 --> 00:07:57,250
Then we insert that object
into our Hash table.

141
00:07:57,250 --> 00:07:59,880
Giggle is a high pitched laugh,

142
00:07:59,880 --> 00:08:02,413
and we insert that item
into our Hash table.

143
00:08:02,413 --> 00:08:05,170
Then we do the same thing for potato,

144
00:08:05,170 --> 00:08:09,143
shoe, yak, axle, cone, and fish.

145
00:08:10,090 --> 00:08:11,490
And then we print our table.

146
00:08:12,520 --> 00:08:15,610
Now there's something
funny going on in here.

147
00:08:15,610 --> 00:08:18,930
And you'll see when we print
the table, what that is.

148
00:08:18,930 --> 00:08:23,680
And by way of explanation,
I've also printed out here

149
00:08:24,550 --> 00:08:28,980
the key value, the word, and the output

150
00:08:28,980 --> 00:08:32,230
of our Horner Hash for
each one of those words.

151
00:08:32,230 --> 00:08:34,373
So we can see what the result is there.

152
00:08:35,810 --> 00:08:39,400
Then, finally, we do a find on giggle

153
00:08:39,400 --> 00:08:42,320
to make sure that that
works and we do a remove

154
00:08:42,320 --> 00:08:44,400
on giggle to make sure that works.

155
00:08:44,400 --> 00:08:46,600
And then we print our
table again to verify.

156
00:08:48,010 --> 00:08:50,573
So let's run that and see what happens.

157
00:08:53,220 --> 00:08:57,343
Okay, so here's our
output, just expand this.

158
00:09:00,370 --> 00:09:03,090
Okay, so,

159
00:09:03,090 --> 00:09:06,490
here's our Hash table, we have 17 entries,

160
00:09:06,490 --> 00:09:09,060
with entries C0-16.

161
00:09:09,060 --> 00:09:13,270
Fish, shoe, cone, potato,
yak, axle, giggle.

162
00:09:13,270 --> 00:09:16,290
Now wait a minute, what
happened to dentist?

163
00:09:16,290 --> 00:09:21,290
We had eight objects that we inserted,

164
00:09:21,630 --> 00:09:24,640
one, two, three, four,
five, six, seven, eight,

165
00:09:24,640 --> 00:09:25,760
but there's only seven here.

166
00:09:25,760 --> 00:09:27,850
One, two, three, four, five, six, seven.

167
00:09:27,850 --> 00:09:30,760
What happened to dentist, did it not work?

168
00:09:30,760 --> 00:09:32,910
Well, here's what happened.

169
00:09:32,910 --> 00:09:36,850
Take a look at the values
that Horner Hash returns

170
00:09:36,850 --> 00:09:38,370
for each of these strings.

171
00:09:38,370 --> 00:09:41,550
Dentist gives us a zero,
giggle gives us 12,

172
00:09:41,550 --> 00:09:44,872
potato seven, shoe four,
yak eight, axle 10,

173
00:09:44,872 --> 00:09:47,600
cone six, fish zero.

174
00:09:47,600 --> 00:09:51,270
So we have, what's
called a Hash collision.

175
00:09:51,270 --> 00:09:54,060
We have two values here,

176
00:09:54,060 --> 00:09:57,100
two keys that give us the same Hash.

177
00:09:57,100 --> 00:10:00,410
So when we inserted fish,

178
00:10:00,410 --> 00:10:04,630
it overwrote the value for
dentist and that's why dentist

179
00:10:04,630 --> 00:10:09,180
does not appear in our Hash
table, and that's not good.

180
00:10:09,180 --> 00:10:11,790
And we'll get to that in a minute.

181
00:10:11,790 --> 00:10:15,990
And then we wanted to verify that deletion

182
00:10:15,990 --> 00:10:18,890
does actually work,
removal actually works so,

183
00:10:18,890 --> 00:10:23,150
we remove giggle and we
see giggle is no longer

184
00:10:23,150 --> 00:10:27,320
in our Hash table, it was at index 12,

185
00:10:27,320 --> 00:10:29,270
and now when we look at index 12

186
00:10:29,270 --> 00:10:32,323
we see there's nothing there,
so that works as expected.

187
00:10:33,310 --> 00:10:35,800
So what happened here?

188
00:10:35,800 --> 00:10:37,113
We had a collision.

189
00:10:38,770 --> 00:10:43,600
We had dentist and fish
gave us the same index

190
00:10:43,600 --> 00:10:46,270
when we ran it through
our Horner Hash function.

191
00:10:46,270 --> 00:10:49,030
And if we go back to our Hash table here,

192
00:10:49,030 --> 00:10:53,190
we'll see here on the
insert there's nothing

193
00:10:53,190 --> 00:10:56,973
that checks to see if there's
already a value there.

194
00:10:58,150 --> 00:11:00,460
So it just overrode the value.

195
00:11:00,460 --> 00:11:03,663
We had dentist and we
overrode it with a fish.

196
00:11:04,890 --> 00:11:08,010
So that's not good, we
don't want that to happen.

197
00:11:08,010 --> 00:11:09,280
We'll lose data.

198
00:11:09,280 --> 00:11:12,450
So what we're going to need
to do in subsequent videos

199
00:11:12,450 --> 00:11:14,910
we're going to need to demonstrate

200
00:11:14,910 --> 00:11:19,730
what are called collision
resolution policies.

201
00:11:19,730 --> 00:11:22,100
There are some that are
presented in the book,

202
00:11:22,100 --> 00:11:24,720
and we're going to go over some of these

203
00:11:24,720 --> 00:11:28,110
and build a more sophisticated Hash table

204
00:11:28,110 --> 00:11:30,040
that can handle collisions.

205
00:11:30,040 --> 00:11:32,803
That'll be in future lectures,
but that's all for now.