- [Instructor] Hash tables.
Hashing is a big subject.
What we're gonna study here is how do you use hashing
to construct and use hash tables.
A hash table is a data structure that provides for access
to elements in big O one time that's constant time.
We won't be studying cryptographic hashing
which is a subject in its own right,
and in a very interesting subject I might add.
That's where hashing is used for data security,
authentication, blockchain, proof of work,
and other applications.
If you are interested in this see CS 166, 167 and 266
those are the courses that deal with cybersecurity
and they touch on cryptographic hashing.
Anyhow, we've looked at many ways
to find an element in various data structure.
We've seen binary search trees, b-trees, binary search
and the linear structure, interpolation search
and a linear structure and more.
And these approaches are all based
on finding an object within a data structure.
But what if there were a way for us to know exactly
where to find the given object?
How might that work?
In your projects, you've been working with a set
of objects that have at least one unique value
for each object.
And let's say you wanted to store a collection
of your objects in some data structure, say a vector.
I mean, we've been doing that.
So, how would you store your objects
in the vector and how would you retrieve them?
You could, as we've already done,
add all your objects to the vector, sort the vector and then
do binary search or an interpolation search if your object's
unique values have some uniform distribution.
But there's a faster way, and I've already alluded to this.
A hash table stores items in a way
that lets you calculate the items index directly.
How does that work?
Well, it requires what's called a hash function.
A hash function is a map, now what do I mean by that?
It means that ideally a hash function takes some key value,
say the unique field in your object,
and turns it into an address or an index
that can be used to insert or look up
the corresponding object and the vector
which we call a hash table.
So, if we have a vector as shown here,
with certain properties and we have a hash function
which we'll explain what that is in a minute
then we have what's called a hash table.
And, the way the hash table works is it takes a key passes
it to the hash function that returns an address.
And that tells you where to insert
or to find the object in question.
So, let's say we have a collection of objects,
say books and we want to store book objects in a vector
the hash table, how would we decide where to put them?
So here, we're gonna do an insert using the title
as a key, The Blind Watchmaker.
We pass this title, this string to the hash function
the hash function returns a value too and now we're pointing
at element two in the hash table
and we make our insertion.
We insert our object
which includes our author and publisher and year.
And, that goes here at index two.
Now, if we wanna access our object again
we pass the title to our hash function.
Again, the hash function will return two
and we can access this element in the vector index two.
And that's the idea behind hashing.
Now, as you might've guessed,
it's not quite as simple as this.
And to be honest, we've glossed over many details
in this simplified example but we'll spend
this in the next few lectures
going over some of those details.
A couple of the details that we'll look
at in this lecture are these.
First, what does a hash function look like?
That is how do we take a string, for example
as an input and return an index to our table.
And second, how big should we make our table?
And we'll see that these are related.
So first the question of how big our vector
or hash table should be.
For starters, if we have an object,
our hash table should be at least of size n,
it's gotta hold all our objects that's obvious,
but we also want to have our objects distributed
within the table as uniformly as possible.
We don't want them forming clusters or groups.
Complete uniformity is a goal
that's seldom met and practice.
But the idea is that we want them spread
throughout the table and not have them in clusters.
That's an ideal.
We'd also like to have some capacity
to add new objects if need be.
And we call the ratio of the number of objects to the size
of our hash table, the fill percentage or load factor.
And, we don't want our load factor to be too high.
Finally, the size of our hash table should be prime,
and we'll see why a little later.
We also need to choose a hash function.
Now for a hash function, we wanna function that takes a key
whatever that key is, a string and integer
or even a combination of multiple values.
And this function should return a value
that we can use as an index into our hash table.
Now, it's important that this function
should be easy to compute.
If it's too expensive, then we lose time
and our implementation isn't efficient.
This function should produce outputs that are as close
to uniformly distributed as possible.
And, that's how we distribute elements
throughout our hash table, as uniformly as possible.
It's important that the range of our function
should be valid indices into our table.
So, they should range from zero
to the size of our hash table minus one.
And we want to the greatest extent possible
to avoid different keys from resulting in the same index.
Let's consider the last two items which are closely related.
Let's say we have a table size of 17.
The range of outputs for our hash function
should be zero through 16.
Those are the valid indices of our hash table,
and how do we accomplish this?
We calculate a number and then we return
that number modulo 17 that is modulo the size of our table.
Remember modulo arithmetic from the first week in class?
That's what we're using here.
So how do we implement hash function?
Here's a not so good hash function.
We take an input string.
We start with hash equals zero
and then we break the string apart into characters
and in C++, characters have an underlying representation
as an integer so we can add them.
So we take this starting hash
which is zero for the first iteration.
And we add the value of the character and we keep
doing this, looping through this until we've consumed
all the characters in the string.
And, then we return that result modulo this maxindex
whatever that value is that we passed in.
And if we do this, we get these values for these input keys.
Dog gets 10, catamount returns five,
squirrel returns five, rabbit returns one,
toad returns one, monkey returns 15, chipmunk returns 15
and you can see right away that we have a problem here.
We have multiple inputs that mapped to the same value
and that would mean mapping to the same index
in our hash table, and that's not good.
So we've got these three duplicated values.
And to improve on this, we need to calculate something
that distributes the values more evenly.
And since we're taking the modulates,
it makes sense to start with a calculation
that distributes the values more widely to begin with
and then we'll have less chance of duplicated values.
So here's a better function.
Here what we're doing, is we start as before
with the input string, the maximum index,
we initialize this variable hash
which is now an unsigned long to be zero.
And, then for each character in our input string
we take the previous hash
we multiply it by 37, 37 is a prime number,
and then we add the value of that character.
Then we take the hash modulo,
the max index and return that value.
And with this hash function, we see dog gets 11,
catamount gets nine, squirrel gets 12, rabbit gets three,
toad gets three, monkey gets 14 and chipmunk gets seven.
So it's still not perfect, we still have a duplicated value
and we'll get to those in a later video,
but it's an improvement.
And this particular hash function
is called a Horner hash function.
It gets its name after Horner's method
of evaluating polynomials.
Horner was a 19th century mathematician.
But wait, you say
what does this have to do with polynomials?
Well, let's look at this part of the code here.
If we were to pass in the string DCBA
at the first iteration,
hash would be zero, hash times 37 is zero,
and we add the value of D which I'll represent here
just as the variable D.
Then at the next iteration, we take that value,
we multiply by 37 and we add the value of C.
At the next iteration we multiply that by 37.
So, this is what we had before C in the braces here
is what we have above multiply that by 37 and add B.
And then we do it again for the letter A,
multiply this whole thing by 37 and add A.
Now with X equals 37,
this is just a plus BX plus CX squared plus DX cubed.
So, we've constructed a polynomial function
in a very simple and elegant way.
That's Horner's method.
Now, it bears his name, but you might be interested
to know that numerous mathematicians had discovered
and rediscovered similar methods over the centuries.
In fact, the oldest example that we have of this method
dates back over 2000 years in ancient China.
So, Horner hash function has demonstrated,
meets the requirements we outlined earlier.
It takes an input and returns a value we can use
as an index, it's easy to compute,
it comes close to producing uniformly distributed values
and its output values are within the appropriate range.
So, that's all good.
Let's walk through some examples.
Here, again, we're inserting a book into our hash table.
We take The Blind Watchmaker,
we use the Horner hash that yields five
that points to index five in our hash table
and we insert the object.
Next, we have clever algorithms,
that's a great title, that yields index nine.
We insert that into our hash table.
The Human Condition with a Horner hash gives us index 11
given that our table is of size 17 here,
we insert Human Condition into our hash table.
Here we have an object representing the book modern algebra
that key modern algebra yields an index
of two when we Horner hash it, so insert that into two.
Symbiotic Planet, you're getting the idea,
you're not a gadget, gets us index 16,
we insert that into our hash table.
What's the complexity of inserting?
Well, we have to calculate the hash value
and that takes place in constant time.
And we have to perform the insert into the vector
and that takes constant time.
So, our complexity is big O of one.
It takes place in constant time, that's pretty cool.
When we find we simply pass a string
we wanna know is Blind Watchmaker in our table
and if so, where is it?
We pass that to the Horner hash,
we get the index five and it looks it up.
It finds the record for us.
We do it with clever algorithms.
It looks up nine and finds it, and so on.
So it works just the way that insertion works.
Now, what happens if we search for a string
for which there is no corresponding entry like Moby Dick?
We apply Horner hash to Moby Dick,
we get an address of three but in our hash table,
there's nothing at index three, there's no entry.
So, we know that that doesn't exist in our hash table
but even so it was a quick operation.
So, for finding what's the complexity,
well, we have to calculate the hash value
that takes place in constant time.
We have to fetch the items stored at that index
and the vector or refined that there's nothing there,
that takes constant time.
So, again, our complexity is big O of one.
If we wanna delete a record in our hash table,
same thing, we have to calculate the hash value,
we go to that index,
we delete the value takes place in constant time.
So, now what have we left out?
There are quite a few implementation details
that we've left out, but the most important thing
we've left out of our discussion so far is this,
what do we do when hashing two different keys
yields the same value?
And this is a challenge for hash tables
called hash collisions or just collisions.
And we'll learn more about collisions
and what to do when they occur in future lectures.
It turns out that there are many different strategies
called collision resolution policies.
And we'll look at some of the most common ones.
So in summary, the hash table allows
for big O of one insertion access and deletion of objects.
A hash table requires a hash function
that turns keys into indices.
Choosing a good hash function is important.
We've already seen this, we want values in its range
to be as close to uniformly distributed as possible,
and it should be easy to compute.
And we have yet to address collisions
and collision resolution policies.
So before we end, I'll leave you with a few questions.
You'll recall that we said it's best
if the size of a hash table is the prime number.
Can you think of any reason why this might be so?
Another question, random numbers
can be more or less uniformly distributed.
Why don't we use random numbers for hashing?
And finally, think about how we might handle
collisions when they occur.
There are many different methods as we'll see.
That's all for now.