So I'm gonna go ahead and just for convenience, draw my greatest time vertically instead of horizontally.

But it's the same thing, and this is just an artist's rendition anyway.

And suppose the goal at hand is to keep track efficiently of like 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 of name tags, even if it's alphabetical, a dizzy, then had everyone in the room lineup and look through all of the Dar name tags looking for their name right?

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.

We're Hopefully you're the only person with a name that starts with some letter and you could just reach in and get it.

Well, how do we implement this conceptually?

Well, it's very common with 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 is maybe being indexed from a through Z so still 26 buckets.

But this array is really just a 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, 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, um, where do I want to go ahead and put the 1st 1?

So Alvis is the 1st 1 who's name tag we made.

I'm gonna go ahead and jump immediately to bucket zero and put Albert's name right there in one step.

Meanwhile, I've got Zachariah is.

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.

I just don't have a human.

And so I can immediately instantly put Zacharias over their rights.

Little laborious for my feet.

But a computer could just jump to zero or 25 or anything in between.

All right, So her Miami, maybe you're noticing the pattern.

So her mind is gonna be a tch or which is seven.

Which is gonna be over here.

Ginny s six.

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 gonna go over here.

As an aside, the staff and I discussed this morning how we probably should have put the buckets closer together, but that's okay.

Uh, severest is gonna go over here.

Petunia is gonna go over here.

Draco's way over here, but doesn't matter.

Constant time Bracket three.

James's bracket nine.

Cedric is bracket, too.

I have to play this part into X speed.

Luna is Buckets.

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 who 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 I'm out of breath.

But what's really convenient now is that if Cedric or Elvis or Drake Oh, or Fred or Ginny come into the room, they can index instantly, randomly to their bucket, 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, right?

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 gonna go in bucket 77 But wait a minute.

There's already someone there, right?

So what do I do if I were only using an array?

Harry is kind of out of luck like her.

Miami is already in that location in the array, and we would have to decide either her Miami 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 length list, you know what, That's fine.

We're just gonna go ahead and link her Miami and Harry's together.

So, yes, it's gonna take both of them or one of them at least two steps to find their name tag.

But it's not gonna take big O of end steps to find their name tag.

At least if there's only two in this bucket are Hagrid dammit.

So he came in the door to.

So now that link list is getting a little longer.

We now have a chain, if you will.

A link list of size three serious is going to go over here in Bucket 18 but Severus is already there, too.

Awkward, remiss is 17 Remiss is going to go and link together with Ron There.

George is gonna go into buckets six, 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, two bucket ties, values and computer science conceptually means to throw the value into a bucket or physically.

As we've done here, Lucious finally is gonna go in bucket 11 2 And lastly, lavender goes in that same bucket who?