A hash table is a combination of an
array and linked lists inside of it.
So I'm going to go ahead and just
for convenience draw my array,
this time vertically
instead of horizontally.
But it's the same thing.
And it's just an artist's
rendition anyway.
And suppose the goal at hand is to keep
track efficiently of like a name tags.
So maybe we're holding a big event.
We've made some name tags in
advance, which we indeed have.
And we want people to be able to pick
up these name tags super efficiently.
It would be really
annoying and pretty dumb
if we just made a big
stack and name tags,
even if it's alphabetical, A to Z,
then had everyone in the room line up
and look through all of the darn
name tags looking for their name.
That's not a very inefficient system.
Fortunately, we've come prepared with
some buckets, all of which are labeled,
because wouldn't it be nice if
you're looking for your name tag,
you don't look through the whole
darn list of name tags or stack?
You actually just go to your bucket.
And you jump instantly to your
name, where hopefully you're
the only person with a name
that starts with some letter.
And then you can just
reach in and get it.
Well, how do we implement
this conceptually?
Well, it's very common with
a hash table if the inputs
are things like words or names to
look at the characters in those words
to decide where to put those names
or those name tags, if you will.
So here's an array of
size 26, from 0 to 25.
But, you know what, It's
convenient to think of this array
as maybe being indexed from A
through Z. So still 26 buckets,
but this array is really just of
size 26, 0 through 25 ultimately.
And suppose the goal at hand now
is to go ahead and store these name
tags in advance.
So this is what the staff
and I would do in advance.
And, Brian, if you wouldn't
mind helping out with this.
The goal at hand is quite simply to
get the name tags ready for students
to pick up.
And so where do I want to go
ahead and put the first one?
So Albus is the first one
whose name tag we made.
I'm going to go ahead and
jump immediately to bucket 0
and put Albus's name
right there in one step.
Meanwhile I've got
Zacharias, and so even
though it's taking me a bunch of steps
to go over here, if this is an array,
I have random access, as a
human, and so I can immediately,
instantly put Zacharias over there.
It's a little laborious for my
feet, but a computer could just
jump to 0 or 25 or anything in between.
All right, so Hermione--
maybe you're noticing the pattern--
so Hermione is going to be H,
or which is 7, which is
going to be over here.
Ginny is 6, which is over here.
Ron is 17, which is over here.
So think of each of my multiple
steps taking actually one step.
Fred is going to go over here.
As an aside, the staff and
I discussed this morning
how we probably should've put
the buckets closer together.
But that's OK.
Severus is going to go over here.
Petunia is going to go over here.
Draco is way over here, but doesn't
matter, constant time, bracket 3.
James is bracket 9.
Cedric is bracket 2.
Perhaps play this part in 2x speed.
Luna is bucket 11.
Neville bucket 13.
Kingsley bucket 10.
Kingsley, there we go.
Minerva bucket 12.
Vernon-- ironically, we don't
actually need this many names
to make the point we're trying to make.
But Vernon-- we got a little carried
away with the names we recognized.
And now, the list is pretty full.
All right, so that's a
whole bunch of names.
I filled up most of the
buckets with a name tag.
But-- why am I out of breath?
But what's really convenient now is
that if Cedric or Albus or Draco or Fred
or Ginny come into the room,
they can index instantly,
randomly, to their pocket,
get their name tag, and go.
Nothing linear.
They don't have to flip through
the whole stack of name tags
with which I actually began the story.
But there's a problem ahead.
We very deliberately ordered the
name tags thus far in such a way
that we don't create a
problem for ourselves.
But among the more famous characters
we've not heard from yet is Harry.
So Harry's name tag is still here.
Where does this go?
Well, Harry is going to go in bucket 7.
But wait a minute, there's
already someone there.
So what do I do?
If I were only using an array,
Harry's kind of out of luck.
Like Hermione is already in
that location in the array.
And we would have to decide, either
Hermione goes there or Harry,
but we can't just put them both.
But if we implement this new data
structure called a hash table using
an array that's conceptually vertical,
but that horizontally is a linked list,
you know what, that's fine.
We're just going to go ahead and
link Hermione's and Harry's together.
So, yes, it's going to take both of
them or one of them at least two steps
to find their name tag.
But it's not going to take big O
of n steps to find their name tag,
at least if there's
only two in this bucket.
All right, Hagrid, dammit,
so he came in the door too.
So now that linked list is
getting a little longer.
We now have a chain, if you
will, a linked list of size 3.
Sirius is going to go
over here in bucket 18.
But Severus is already there too.
Awkward.
Remus is 17.
Remus is going to go and
link together with Ron there.
George is going to go into
bucket 6, which is over here.
Lily is also going to collide,
so to speak with Luna.
And this is a collision
in computer science.
Anytime you have a value that
you're trying to put in one place
but there's something there, you need
to resolve the collision somehow.
So I'm proposing that we actually
just link these together.
Or as we're doing here, to bucketize
values in computer science conceptually
means to throw the value into a bucket,
or physically as we've done here.
Lucius finally is going
to go in bucket 11 too.
And lastly, Lavender
goes in that same bucket.
Phew.
