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.