YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 18-31 Testing Hash Functions

18-31 Testing Hash Functions

Get Embed Code
2 Languages

Showing Revision 1 created 07/21/2014 by osawakjvta.

  1. 新しいハッシュ関数をテストします
  2. 以前定義したbad_string_hash関数より
    優れているか確認します
  3. 以前定義したものと同じtest_hash関数を使用します
  4. 入力として関数を使用します
  5. 元のbad_string_hash関数
    または新しいhash_string関数を渡します
  6. 新しい方はうまく機能することを願います
  7. キーのリストとサイズ
    各キーのハッシュサイズ値を計算します
  8. そして各ポジションで終了する数を記録します
    やってみましょう
  9. 以前と同じくシャーロック・ホームズを
    例に使用します
  10. まず単語の設定です
  11. Webの「The Adventure of Sherlock Holmes」の
    ページのすべての単語に設定します
  12. それではまず古いハッシュ関数
    つまりbad_string_hashでもう一度試してみます
  13. そしてカウントを入手し表示させます
  14. どのようなものか覚えておいてください
  15. 以前確認したようにこれは悪い分配です
    1つのバケットで725から2,000以上まであります
  16. これをbad_hash_stringではなく
    新しいハッシュ関数で試してみましょう
  17. ただのhash_stringを渡します
    同じ単語とバケット数を使用します
  18. 現在の分配を確認します とてもよくなりました
  19. 1,000以下の値がありません
  20. 一番大きい値は1,363です
  21. それではこれをグラフで見てみましょう
  22. これが以前のものです bad_hash_string関数では
  23. バケットのサイズが大きく違うことが分かります
  24. 赤色と青色の棒は
  25. 集中し過ぎのものとしていないものが
    あることを示しています
  26. 新しいハッシュ関数では
    バラツキがずっと少なくなりました
  27. まだ完璧ではありません
    すべての棒を可能な限り同じに近づけたいです
  28. でもかなり均等です
    これはとてもうまく機能しています
  29. 他に試すことはバケットをさらに増やすことです
  30. 同じことを行いますが
    12バケットではなく今回は100バケットです
  31. 表示させると100バケットの結果が確認できます
  32. とてもいいのですが完璧ではありません
    小さいものは104です
  33. 大きいものは197です
  34. 最小バケットサイズの約2倍あります
  35. 優れたハッシュ関数を作成するのは
    とても難しい問題です
  36. そのために多くの人が努力しています
  37. 表が大きくなるほど
    ハッシュ関数の効率性がとても重要になります
  38. 私たちのhash_string関数はそれほど優れていません
  39. 文字列が長いとそれぞれの文字のループを行うので
    実行に長時間要するからです
  40. もっと優れたハッシュ関数があります
  41. 関数にはこれ以上詳しく触れませんが
  42. もっと面白いハッシュ関数のドキュメントへのリンクが
    Webサイトに載っています
  43. この関数も私たちには十分です
  44. それでは実際にハッシュテーブルに実装する前に
  45. 元のインデックスよりずっと優れている理由を
    理解できているか確認する小テストを行います