[Evans] We've seen the basic looking at just the first letter does not work very well.
It 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.
We want the same property we had before in the sense that it's 1 function
that takes 2 inputs, and the 2 inputs are the keyword, which is a string,
and the number of buckets, which is a number.
Those are the 2 inputs, and the output is the hash value,
and it's in the range from 0 to number of buckets - 1.
And our goal is for these numbers to be well distributed.
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.
In order to do better than we were doing before,
we're going to need to look at more than just 1 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 and 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 will decide the 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 would go through each element in p, assigning it to the variable e
and executing whatever is in the block for each element of p.
We can do something similar with strings.
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 1-letter string corresponding to each character in the string in order.
So first it will have the value a, then the value b, then the value c, then the value d.
This gives us a way to go through all the elements in the string.
If you remember how we turned single letter strings into numbers and modulo 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, hashstring, that behaves like this.
It takes a keyword, a number of buckets, and it gives a 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 produce as its output a single number
that represents the bucket where that keyword belongs.
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 different ways to do this,
so we're going to specify exactly what you should do.
What we want to do is make the output of hashstring a function of all the characters.
We can think of that with modulo 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 - 1,
what we want to do for each character, we're going to start at 0,
and for each character in the string we're going to go around ord of that character,
distance around the circle, and we're going to keep going.
So each character we're 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 modulo arithmetic for each letter.
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.
Let's say that's position 27. Who knows where it is?
That's the idea, and I'll give you a couple 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.
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 8 times
because 97 is 12 8.
And 1 more because 97 is 12 8 + 1.
You don't actually have to go around the circle.
If you use the modulo, that's what it will give you.
So the hash value for 'a' should end up in bucket 1.
As another example, if we tried hashstring where the string is the single letter 'b'
also with 12 buckets, that's going to also go around the circle 8 times
because the ord of 'b' is 98, but it's going to end up in bucket 2
since that's 96 + 2, which will end up in bucket 2.
If we change the number of buckets, the results will be different.
Let's say instead of having 12 buckets we have 13
and we tried hashstring on the single letter string 'a' with 13 buckets.
The result there should end up being 6.
The reason it's 6 is because 97 is equal to 13 7 + 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're 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.
Where we can see the difference between what you're going to define as hashstring
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 2, we get 214.
And modulo the number of buckets, which is 12 here, we should get 10.
So that string with 2 symbols doesn't end up in position 1 where the 'a' would end up.
It ends up in bucket 10.
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 bucket--
Sorry. I forgot the input size. This is very important.
We need 2 inputs to hashstring. 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.
See if you can define a function, hashstring, that does this.
We want it to take these 2 inputs and produce a number
that tells us what bucket that keyword should be in.