So let's test our new hash function. See if it does
better than the bad string hash function we defined earlier. We're going
to use the same test hash function we defined before, that
takes the function as input. So we can pass in either the
original bad string hash function, or the new hash string function
that we hope will work better. A list of keys, and the
size, computing the hash size value for each key. And, records
how many end up in each position. So let's try that again,
we'll use the same example we had before using
the words from Sherlock Holmes. And so we'll initialize
words, as all with words in the page that
is the Adventures of Sherlock Holmes, that we load
from the Web. So, first we'll try this again
with the old hash function, bad string hash, and
obtain the counts, and let's print those out, remember
what those look like. So it's a pretty bad distribution,
as we saw before, ranging from 725 all the way up to over 2,000, in one
bucket. Now, let's try it with the new
hash function, instead of bad_hash_string. We'll pass in
plain hash string. We're using the same words,
the same number of buckets. And we'll see
the distribution now. It looks a lot better,
right. There's no values under a thousand now,
there's now values over the highest one would be 1,363
in the first bucket. So, lets look at that graphically.
Here's what we had before. With a bad hash string
function we can see the size of the buckets varies a
great deal. And we have the red and blue bars
showing some that are too popular, some that are not popular
enough. With the new hash function we have much less
variance. Still not perfect. We'd like to have all the bars
really be as close to the same as possible, but it's really
close. So this is working pretty well. The other thing we can
try is having more buckets. So lets try this one, we are
doing the same thing but this time with a 100 buckets instead of
12 buckets. And we can print that out, and so we see
the results when we have 100 buckets, are pretty good, but certainly
not perfect. We have buckets as small as this one, that has
a 104, and as larger, this one that has a 197. So almost
twice the size of the smallest bucket. It's certainly a hard
problem to build a better hash function. People put a lot of
effort into building good hash functions. As your tables get larger,
it's very important to both have the hash function be efficient. Our
hash string function is not that great, because it does take
a long time to execute. If the string gets longer we have
to go through that loop once for each character. And so there
are better hash functions available. We're not going to look at those
in more detail now. But there'll be some links on the website to documents about
more interesting hash functions. This is going to
work well enough for us though. So before
we go on to actually implementing in a hash table. We're going to have one quiz
to make sure that you understand, why this
is so much better than the original index.
新しいハッシュ関数をテストします
以前定義したbad_string_hash関数より
優れているか確認します
以前定義したものと同じtest_hash関数を使用します
入力として関数を使用します
元のbad_string_hash関数
または新しいhash_string関数を渡します
新しい方はうまく機能することを願います
キーのリストとサイズ
各キーのハッシュサイズ値を計算します
そして各ポジションで終了する数を記録します
やってみましょう
以前と同じくシャーロック・ホームズを
例に使用します
まず単語の設定です
Webの「The Adventure of Sherlock Holmes」の
ページのすべての単語に設定します
それではまず古いハッシュ関数
つまりbad_string_hashでもう一度試してみます
そしてカウントを入手し表示させます
どのようなものか覚えておいてください
以前確認したようにこれは悪い分配です
1つのバケットで725から2,000以上まであります
これをbad_hash_stringではなく
新しいハッシュ関数で試してみましょう
ただのhash_stringを渡します
同じ単語とバケット数を使用します
現在の分配を確認します とてもよくなりました
1,000以下の値がありません
一番大きい値は1,363です
それではこれをグラフで見てみましょう
これが以前のものです bad_hash_string関数では
バケットのサイズが大きく違うことが分かります
赤色と青色の棒は
集中し過ぎのものとしていないものが
あることを示しています
新しいハッシュ関数では
バラツキがずっと少なくなりました
まだ完璧ではありません
すべての棒を可能な限り同じに近づけたいです
でもかなり均等です
これはとてもうまく機能しています
他に試すことはバケットをさらに増やすことです
同じことを行いますが
12バケットではなく今回は100バケットです
表示させると100バケットの結果が確認できます
とてもいいのですが完璧ではありません
小さいものは104です
大きいものは197です
最小バケットサイズの約2倍あります
優れたハッシュ関数を作成するのは
とても難しい問題です
そのために多くの人が努力しています
表が大きくなるほど
ハッシュ関数の効率性がとても重要になります
私たちのhash_string関数はそれほど優れていません
文字列が長いとそれぞれの文字のループを行うので
実行に長時間要するからです
もっと優れたハッシュ関数があります
関数にはこれ以上詳しく触れませんが
もっと面白いハッシュ関数のドキュメントへのリンクが
Webサイトに載っています
この関数も私たちには十分です
それでは実際にハッシュテーブルに実装する前に
元のインデックスよりずっと優れている理由を
理解できているか確認する小テストを行います