- [Instructor] Okay, now we're gonna look
at our first collision resolution policy,
which is called separate chaining,
or in the book, just chaining.
And you recall from an earlier video,
our introduction to hash tables left something out,
and we made a note of that fact.
And that is what do we do when two different keys
yield the same index into our hash table?
This is called hash collision,
and it's something that we need to handle.
We saw in our coding demonstration of a naive hash table,
that when a collision occurred,
our hash table overwrote an existing entry.
Remember our dictionary
and the objects for dentist and fish?
Both keys yielded the same index,
and the entry for dentist was overwritten
with the entry of fish.
Obviously, we don't want that to happen.
So, what do we do?
We have to implement some collision resolution policy.
Now, we've shown that collisions are inevitable.
So, we're going to take the example of pigeonholes to heart
in our first collision resolution policy, separate chaining.
The idea behind separate chaining
is the same as having two or more pigeons
in the same pigeonhole.
That is, instead of holding just one object,
we allow our elements in our hash table
to hold more than one object.
We saw how to do this, in fact,
when we implemented bucket sort and and rated sort.
And you recall both of those algorithms
used a data structure that was a vector of buckets,
that is a vector of vectors.
And we'll use exactly the same structure
for separate chaining.
For an example, let's choose a small problem instance.
Here, we have a hash table of size seven
with indices from zero to six.
And again, for purposes of this demonstration,
let's choose the simplest possible hash function,
f(x) equals X mod 7, where our inputs are integers.
So, we're gonna take integers and we're going to insert them
into this hash table using separate chain,
and we'll see how that works.
So, I used a random number generator
to pick random numbers between zero and 200.
We start with 13.
13 mod 7 is 6.
So, 13 goes in bucket six.
Now, 179.
179 mod 7 is 4.
And so, 179 goes in bucket four.
114, 114 mod 7 is 2.
So, 114 goes in bucket two.
5 mod 7 is 5.
So, that goes a bucket five.
20 mod 7 is 6.
Now, this is our first collision.
Now, what happens?
We're just going to add it to the bucket.
13's already there.
That's okay.
We're not gonna overwrite 13,
like we did in our naive implementation of hash table.
We're just gonna add it to the bucket.
73 mod 7 is 3.
So, that goes in bucket three.
180 mod 7 equals 5.
So, now we have another collision.
We're just gonna add it to the bucket.
So, now we have 5 and 180 in bucket five.
48 mod 7 is 6,
so we're gonna add another value to that bucket six.
And there's 48.
46 mod 7 is 4, so we're gonna add that to the bucket
that already has 179.
There's 46 now.
88 mod 7 is 4, so we're gonna add that again
to the same bucket, 88.
196 mod 7 is 0.
There's 196.
And that's how separate chaining works.
So, insertion takes constant time,
or it could take constant time
because calculating the hash takes constant time,
and inserting into a vector takes constant time.
But, what about duplicate values?
Our hash table becomes a little less useful
if we allow duplicate values.
And it makes matters messy,
especially if we want to remove values.
Now, we have to remove duplicate values.
So, we don't want duplicate values in our table.
So, what happens when we have duplicate values?
Well, we have to search through the bucket,
and that kills the constant time.
It no longer takes constant time to insert an object
into a hash table with separate chaining.
We have to search through the bucket first
in order to confirm that that value doesn't already exist
in the bucket.
What about find and remove?
For find and remove,
we have to search through the bucket regardless, okay?
So, that's a given.
Now, if we have a table of size b,
where b is the number of buckets,
and we have n objects we wish to store,
then on average, a bucket will store n divided by b objects.
Simple arithmetic.
And if we use linear search to check to see
if an object is already in our bucket,
because our buckets aren't sorted,
then that takes big O(n/b) time.
And we also have to search through a bucket
when finding or removing.
Now, note that the book uses a linked list for buckets
and here we're using vectors,
but this doesn't change the fact that in either case
we still need to search.
So, in summary, separate chaining uses a vector of vectors,
or a vector of linked lists, if you will,
to handle collisions.
Objects with the same index
calculated from the hash function
wind up in the same bucket.
Again, whether it's a vector or a linked list.
And this requires us to search on each insertion,
find, or remove operation, okay?
We have to search on insertion
to verify that an element doesn't already exist
in our bucket.
We always have to search on a find,
and we always have to search on a remove.
But, separate chaining has the benefit
that it's very easy to implement.
And we'll see that in a subsequent video.
Now, before we go,
I'm gonna leave you with a couple of questions.
First, if we sorted our buckets,
we could improve the search time to big O(log (n/b))
using binary search.
Or if our data were suitable, big O(log log(n/b))
using interpolation search.
Does it make sense to do this?
Why or why not?
Give that some thought.
Also, we're gonna look
at a number of other collision resolution policies.
So, can you think of other ways
that we might handle collisions
that don't require the use of buckets?
I'll leave you with those two questions for now.
More later.