OK.
Welcome back to another lecture.
Today we are going to be going over a new type of data structure called a hash table.
So let's go ahead and get started.
So what is a hash table?
Well, it is a data structure that's used with a technique called hashing.
What is hashing?
Well, hashing is a technique where you can take a collection of what we're calling keys like this over
here and you put them through a special function like you can think of a C++ function that you've written
and that's going to convert them into an index.
So an index value will come out of this function and will tell us where to store the values that are
associated with our keys.
So let's look at this in a little bit more detail.
So here's an example.
We have these pictures right here.
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
as the value in this specific example.
So 12 would be a key.
And this would be the value.
Our hash function right here.
Is going to be the key mod six.
And I'm using six because it is the size of our table here.
You can just think of this as an array for right now.
So these are the values being stored at the array.
And so these are color coded right now.
Let's go ahead and follow where they are going from the beginning to the hash function to where it's
stored.
So I have 12, which is my key in the value that Jeff is the value I want to store.
So 12 models, six is zero zero remainder.
So I go to index zero and I store Jeff.
Next, I look at how the key value 23, 23 months six is going to be five.
So I store HAL right here at Index five.
Same thing with Bob.
Eight months, six or two.
I store Bob here at index to.
So this looks, you know, this is great and all, but these kind of nicely just ended up.
In these spots, all kind of separated distance from each other, but you're you won't be wondering,
well, what happens if we had something?
That was, let's say.
Maybe 18, like how was 18 had a key 18 instead of 23.
So 18 mod six.
Well, that's zero.
We already inserted Jeff here zero.
So now we want to insert how at zero.
This is something that we're going to call a collision and we need to resolve it.
So.
This is what we're talking about, two different values, something that's already here in two different
values, one to hash to the same spot.
The second one, we need to figure out what to do with that second value or.
X and value, whatever it is, there's there's something already here, we're going to refer to it as
a collision or something else is trying to be stored there.
So the technique that we are going to be talking about in this lecture is changing.
This is kind of one of the most rudimentary techniques, but it's great for explaining and gives us
a chance to implement some things we've already learned.
So this specific strategy uses appending to a linked list as a coalition resolution solution.
So you can look at this diagram right here.
Let's say that Jeff ended up right here.
And so it has to this first value, I think Jeff was index zero, and then we had HAL with our hypothetical
18 key instead of 23.
And he attached to the same thing here.
Well, what I'm going to have to do is I'm going to have to append a HAL to a linked list.
So pretend this part's not here yet.
We haven't added that yet, but I did add a note right here, and I put Hal right here.
Jeff, here and now how to put how here.
So that is changing, we're creating mailing lists to deal with collisions, and so as we get more and
more collisions, we keep building our linked lists down like this.
And these were just hypothetical other spots in which I had to insert something in right here.
I left a pointer on here.
You notice I don't have any pointers sticking off of these boxes.
You can think of the link list as maybe I should have deleted this pointer, but it is now pointing
to no.
So hopefully you aren't confused by that.
Just wanted to point that out because I just noticed it.
So this is the essential idea of chaining.
Let's go through an example just to really hammer that theory in there.
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
a list of our input here.
So a start left to right.
So to start out with seven, so we're going to seven mod for.
We see that that ends up here.
At three.
I'm going to do 10 more for.
Ten more for is, too, so we put it into four month for.
That's going to be zero.
13 mod for.
It's going to be at once, you see that it just naturally kind of filled this up, that's not always
going to be the case.
We might have encountered a collision by now, but it just so happens that they all went to an empty
spot.
And this original refer to this as an array right now.
And then these are linked lists stored here at all these points and they're coming off this direction.
So think of it like that.
So let's go to our next value.
48.
We know we're going to have a collision because our air is filled up with values already at the first
spot.
So that gets hashed to zero, and since we have a collision, we have to store it here in our link listens
first node, go to the next one three.
Three, get stored over here.
Next one nine gets stored here.
Next one will get stored here.
And then of course, 11 one four is going to be three and it just goes in the last spot here.
OK, so what if we think about the efficiency of these operations, we've just been looking at inserts
so far.
But let's look at insertion and search, so insertion.
If we consider an as the size of our input for this insertion insertion search, we're going to be considering
in as input size.
The insertion would be cost and time for the best and worst case.
Why is that?
Well, let's take a look.
The best case is the case in which we have an open spot, and it just so happens that our item, our
key.
It's hashed straight to that spot.
So let's think of like our previous example here, we're just going to say that.
Our numbers here, we didn't have a pair like 18 and how like that we're just storing the numbers like
we did in this example here.
So the keys are the values as well.
So let's just roll with that for now.
Think about it that way to simplify it.
And so if there's an open spot here, let's say, for seven or whatever.
I'm just going to put it in this arbitrary location, but it has a hash up to here and it's open.
We know that indexing our array is going to be a cost and time operation.
And we're also just going to say that computing the hash value is going to be cost and time operation.
Like, let's say it's just an integer mod, some other integer like that simple example we've already
been looking at now, that is Constantine.
So you have constant time plus cost and time that's just going to be cost in time because we know that
we're simplifying it down to the term of the average magnitude, and they're just two of 1s.
So a one plus of one is over one.
So we're considering that for the best case, what would the worst case be?
Well, the worst case, we're going to actually say that for some reason, our array is just one.
It just the size one.
So array of size one, and then we're just storing a big link list there.
So every single time our.
Input comes in, it's a collision.
And so in that case, if you think about it, we're basically going to end up with a linked list equivalent
to the the size of our linked list is going to be equivalent to the size of our input because it's just
going to collide every single time.
So we're going to have a link list starting with the first item here and then going all the way down,
up to end.
But the thing is, and we know this from doing linguists and talking about the complexity of insertion
into linguists specifically right now in this example and the things I've been referring to is unordered.
So we're not hearing about the order and we know that insertion into an unaudited linked list is caused
in time so we can just append it to the end.
So now we can say that we add that cost, which is of one for computing the hash and then inserting
into a linked list.
We also can say we'll go ahead and say that it's all one to index to this value and then another old
one to add it to our linked list to insert it into our own link list.
So those are all of one.
So it's still going to be of one.
And that's why I said insertions of one for best and worst case.
So if it's all won for best and worst case, you see, have an average case down here, turn about to
get to, it's going to be over one for the average case as well.
And so you're kind of thinking, OK, well, we didn't talk about much of our best and worst case before.
Why are we talking about this now?
Well, later on, as I said before, we're going to get more into the details of going deeper into algorithm
analysis.
And although we're kind of simplifying things now, I want to start introducing a little bit more just
so we can look at this hash table in more detail as far as its efficiency.
So there are three different cases that we need to consider when we look deeper into algorithm analysis
and in the industry, we kind of just use that big oh, like I was saying, and that is actually referring
to the average case most of the time they've simplified it.
You know, I said that we're not going to go over these other things you might have heard of, like
Big Omega and Theta Theta being the average case.
We're just going to still call it big.
And most of the time, we're concerned and wanting to know about the average case.
Because it's not going to give me the best case all the time and worst case, let's just simplify it
to the average case, that's why people care about that.
And the big oh, most of the time they're referring to the average case.
So just repeating that again, just so we're all clear.
And now I'm introducing these cases.
So let's think about where we have a more complex average case and start with the search.
So let's start out.
Actually, let's go first over the worst and best searching for something in our house table.
Have these kind of out of order, but yeah, let's actually let's start at this like we did over here
with the best case, the best case to search for something is going to be a cost and time operation.
And why is that?
Well, when we search, I've only talked about insertion now, but it's similar when we search for something
in our hash table.
We're going to use that hash function on our input.
So I'm going to use this example.
Like I said, I would use of just this simple array of numbers like this where we don't have a different
value.
We are hashing on this and storing this.
So if I am now looking it up and I want to look up seven, for example, remember I said it kind of
just as a random location.
Let's say it has two here because, you know, we have some arbitrary random hash function and the operation
of hashing that to get it, you know, is going to be overrun like we talked about.
And now we can use that hash value just like we did to insert to search it.
So we're going to use that value if we want to find seven and we get the hash value of that, we're
going to look at that index to find what we stored there.
So the hash version computes the same value as it did when we inserted.
And that's how we can look it up at that index.
So it's kind of like a dictionary looking something up like that.
And we know that looking it up and which is the operation of indexing it is also constant time.
So we have that constant time, Wisconsin time.
It's going to be constant time of one for the best case where it's stored right here in an open spot.
OK, so now let's look at the worst case, the worst case.
So let's go back to that example where it was just sighs one.
And we don't really need a sample, let's just do that, though, anyways, so we have this huge link
list coming up here that size and well, we do our constant time hash to.
And then a cost and time index with that has to get to this index.
But let's say that our thing we're looking for is stored at the very end of the linked list.
Well, we don't really know where it is because it's not, you know, we're not able to hash the link
list values.
So we actually just have to.
So I don't mean hash mean to index the link list values.
We have to sequentially search through the link to list all the way until we find our item, which I
said is at the end.
So we're going to have to search the whole list of in items to the end.
So that's why we're going to call worst case Bago of any.
So what about this average case that I just mentioned?
Well, for searching, it gets a little bit more complicated and we're not going to get super deep into
it, but I don't want to just throw a big show out there for you to look at without explaining anything.
So let's take a look at this.
So the average case analysis of chaining.
We are going to still say that n equals the size of the input, but I'm going to use another variable
here called M, and that's going to be the size of the hash table array.
So like this right here and I'm not necessarily going to be using this example specifically.
So don't try and count things quite yet in here, like numbers of squares or anything or make assumptions.
I just wanted it.
Here is a visual reference.
So M is going to be the size of the array and in is, however, many values we have coming in like,
for example, here.
One two three four five six seven eight nine We had nine values, so in could be, you know, the size
of our input like that.
A new term that I want to introduce is something called the load factor, which I'm going to let the
load factor be represented by Alpha, and that is going to equal the size of the input over the size
of our hash table array.
And so we can think about our input having to be distributed over these M slots.
And there, of course, being some collisions, you know, if we have all our input coming in gets distributed
over time slots is going to have some length lists and I'm going to be thinking about the size of those
link lists as being represented by this load factor.
OK.
So, Alpha, the load factor.
So when we look at the average case of searching, we're going to think about competing or hash function
like we were talking about before, which is going to be that old one.
And then we are going to have to add the time it takes and total to search for our values.
So we're going to index to the value in the array, the index value, and then we're going to have to
potentially look through a certain size of link list, which I'm thinking of about this distribution
of the link lists being similar in size and thinking about, you know, in this average case of this
length of the link list, I'm going to let Alfa be representative of that, which is our load factor
we're talking about here.
So that's why I have this alfa there, because we're going to have to search through a given size of
link list based on our load factor.
And then you're probably wondering, OK, well, I could you know, why I need really simplify this?
Wouldn't this just be, you know, oh, of alpha, because we have this like cost and time operation
and then we care about the largest terms.
So why wouldn't this answer here be big go of alpha, which is the load factor?
And if you did think that that's good thinking.
But the reason why is because we're not really sure what this load factor is in relation to one, it
could be greater than one, you know, or it could be equal to one or it could be less than one.
So think about this in over in.
You're curious about the size of our input related to the size of the array.
So our input could be one size one in our input could be size a thousand and we could have an array
that was this size or we could have array that was like a million size a million.
Because of that, we have variable values that can be stored in this A.
So that's a what I should say instead, is this a can represent different values that are less than
equal to or greater than one.
And so if it is less than one, we don't want to just completely forget about this one because it becomes
significant.
Now, the largest thing of magnitude is is potentially bigger here than here.
And so we don't want to get rid of it.
So that's why we're leaving this one.
Plus a big show of one plus sorry, not a alpha.
So hopefully that explains it a little bit to you.
We are going to get deeper into this, as I said, and I will continue to say with our algorithm analysis
later on, but I didn't want to completely just leave this out when we're thinking about how efficient
this type of hashing method is.
So hopefully that explain it OK for you.
We are going to be implementing this in an interesting project coming up right after this.
So that's why I wanted to.
I wanted to use chaining as the initial hashing thing we talk about and hash table topic because we
can use our linked lists and get some practice implementing implementing them in association with another
data structure, this hash table.
OK, so hopefully you enjoyed that lecture and I will see you in the next video.