The answer is, all choices are true except for the
first one. The reason the first one's not true, is
this really doesn't take long to compute. We only need
to look at one letter and do a simple modular computation,
that's very efficient. But the other three reasons are true
and we'll go through each of these showing what happens
looking at how things evaluate in the Python Interpreter. So
the first correct reason is that it produces an error for
one input keyword. When we write code we should think
about whether it works for all possible inputs. And the one
that's usually the trickiest to think about is the boundary case.
For a string, that's often the empty string. So, if we
pass in a string with no characters in it, which
is a perfectly valid string, we'll then, when we try to
index element zero, that would be an error. So let's see
what happens when we try that in the Python Shell. So
we'll try to evaluate bad_hash_string, passing in the keyword the
empty string, which is a perfectly valid string. And let's see
there are 100 buckets. And we do get an error,
we get the error that the string index is out of
range because we tried to access the character at position
zero, but there is no character at position zero in the
empty string. So to understand the other two reasons, I have
defined a procedure called test hash function. It takes three inputs.
The first input is a function, so we can pass functions around,
just like any other value, so what we're going to pass in for this,
is the bad_hash_string function that we've defined, but we can also use
it to test other hash functions, which we'll see later. We're going to pass
in a list of keys, those are the keywords for the hash
table, and we're going to pass in the size, this is the number of
buckets. What we do in test hash function, is we're going to keep
results as a list of the number of times each bucket is used.
So initially, they're all zeroes. And we initialize it with zero
times the size. We're going to use keys_used as a list
of the keys that have already been used. We don't want to
count a duplicate key more than once. So now we're going to
loop through the keys. We're going to check if a key
was used already, and if the key was not used, then
we're going to figure out by calling the hash function where
that key would hash to. So, if we passed in
bad_hash_string, that would be the function here.
And we're calling that passing in the keyword, and
the number of buckets. We're storing the result in
the variable hv. And then we're increasing the value
of the element at results position hv by one.
And this is a shorthand syntax, means the
same thing as doing a new assignment where we're
assigning to results[hv], the value currently end results[hv]
plus one, and then we're adding the word that
we just used to the list of keys_used, so
we don't use it again. This is similar to what
we did in the web crawler, to avoid crawling the
same page more than once. And if end will return
the results. So what we'll have as the result of
test_hash_function, is a list where the values in that list
are numbers, giving the number of times a key hashes
to that bucket. So let's try this with
an example using the bad_hash_string function. So to test
our hash function, we need some content. We
need content that represents the kind of words that
we think we're going to be using the hash
table on. I've picked this one, which, perhaps is
represented, perhaps not. And what's there at that link,
is Gutenberg's text of The Adventures of Sherlock Holmes.
And you can see from the scroll bar, it's quite long. So this is all the text
there is. And so on. So, we're going to get all the words on this page using
getpage. We're going to split them into words like
we were doing in the crawler, and we'll
store that in the variable words. And the
length of that is over 100,000 words. Now they're
not all unique, so the number of entries in our
hash table will be smaller then that. But let's see
how the distribution is for those words. So we'll use
the test_hash_function that we defined,
passing in bad_hash_string, the words that
we got from Sherlock Holmes, and we'll pick, for now
we'll use size 12, definitely too small, but that'll give
us a good sense of how the distribution goes for
a small number of buckets. So now we have the result.
Let's look at what the counts are. And
you can see, we've got 12 entries, which corresponds
to the number of buckets. And they vary quite
a bit. The smallest one has only 754 elements.
The largest one has over 2000. So the gap
between the smallest and largest is nearly a factor
of three. If our hash function was good, we
will want these to be about the same size.
Here's what that looks like graphically. We have our twelve buckets.
The ones that are red, are too full. The ones that are
blue, are not full enough. We would like this to be a
fairly flat graph, distributing all of the words evenly between the buckets.