So we've seen the basic looking at just the first
letter does not work very well, doesn't use enough buckets.
And it doesn't distribute the keys well. So now we're
going to think about how to make a better hash
function. So we want the same property we had before
in the sense that it's one function that takes two
inputs and that two inputs are the keyword which is
a string and the number of buckets, which is a number.
Those are the two inputs and the output is the
hash value and it's in the range from zero to
number of buckets minus one. And our goal is for
these numbers to well distributed, so we can have any
number of buckets we want. The keywords will be spread
evenly among the buckets, and every time we hash the
same keyword we'll get the same bucket. So, we'll know
quickly where to find it. So in order to do better
than we were doing before, we're going to need to look at more
than just one letter of the keyword. If we look at just the
first letter, we're not going to do better than having a limited number
of buckets in a bad distribution. So, what we want to do is
something that's going to look at all the letters of the keyword, not
just the first letter. And based on all the letters, we'll decide their
appropriate bucket. We saw that with lists, if we had a list of
items, we could use the for loop construct to go through the elements
in the list, like this. And this will go through each
element in p, assigning it to the variable e and executing
is whatever is in the block for each element of p.
We can do something similar with strings, so if we have
a string s, we can use the same construct to go
through the characters in s. So each time we go through
the loop, the value assigned to variable c will be a
one letter string corresponding to each character in the string in order.
So first it will have the value a, and then
value b, and then value c, and then value d.
So this gives us a way to go through all
the elements in the string. And if you remember how we
turned single letter strings into numbers and modular arithmetic, then
I think you know enough to define a much better hash
function. So for this quiz, your goal is to define
a function hash_string that behaves like this. It takes a keyword,
a number of buckets, and it gives it number, identifying the bucket
where that keyword will belong. But instead of just using the first
letter in the keyword, it's going to use all the letters. And produces
as output, a single number that
represents the bucket where that keyword belongs.
And your goal is to do this in a way that depends
on all the characters in the string, not just the first character.
There are lots of ways to do this, so we're going to
specify exactly what you should do. So what we want to do is make
the output of hash string a function of all the characters.
And we can think of that with modular arithmetic, that if we
have a circle which is the size of the number of
buckets, so this is going to go from 0 to the buckets minus
1. But what we want to do for each character, we are
going to start at 0 and for each character in the string, we
are going to go around ord of that character, distance around the circle,
and we are going to keep going. So each character we are going to
go some distance around the circle, the circle can
be any size depending on the number of buckets and
we're going to keep going around the circle using modular arithmetic
for each letter. And as we keep going, we can
go lots and lots of times if it's a big
word. Wherever we end up is going to be the
bucket that we use. And let's say that's position 27,
who knows where it is. So that's the idea and
I'll give you a couple of examples so
you know if you're implementing it the right way.
Let's suppose we have as our string the single
letter a, and we have 12 buckets. Well in
that case we're going to have 12 buckets, so
we wouldn't have 27 here. This is going to be,
11 is the last bucket, the ord value of a is 97. So for a, what we would
do is go around the circle eight times,
because 97 is 12 times 8, and one more,
because 97 is 12 times 8 plus 1. You don't actually have to
go around the circle if you use the modulo that's what it will give you.
And so the hash value for a should end up in bucket one. As another
example, if we tried hash string where the string
is the single letter b, also with 12 buckets, well
that's going to also go around the circle eight
times because the ord of b is 98. But it's
going to end up in bucket two, since that's 96
plus 2, which will end up in bucket two. If
we change the number of buckets, the results will be
different, so let's say, instead of having 12 buckets we
have 13, and we tried hash_string on the
single letter string a, with 13 buckets. The result there should end
up being 6, and the reason it's 6 is because 97
is equal to 13 times 7 plus
6, so the size of the hash table matters, as well as the string. We don't want
it to just work on single letter strings. With single
letter strings, we are really getting the same thing we defined
before, where it gets interesting is where we have multi letter
strings. So let's look at a few examples like that. So
where we can see the difference between what you are going to
find at hash_string and the bad_hash_string we had
before is once we have longer strings. So suppose we tried
the string au, the ord of a was 97, and that,
when we went around the circle, ended up at location 1. The ord of u, I
can tell you, is 117. When we add those two, we get 214.
And modulo the number of buckets, which is 12 here, we should get 10.
So that string with two symbols doesn't end up in position one where the a would
end up. It ends up in bucket ten, and
as another example, we won't work through the details on
this one, but you'll be able to test if
your result is correct. If you try the string udacity,
it should end up in the bucket sorry I
forgot the input size, this is very important. We need
two inputs to hash string, both the string and
the number of buckets matter. So here, we're also assuming
12 buckets, here we'll use 12 buckets again, the result should be
11. So see if you can define a function hash_string that does
this. And we want it to take these two inputs and produce
a number that tells us what bucket that keyword should be in.