再ハッシュ法を設計時に気をつけること

[Toshita]

再ハッシュ法を設計する場合、具体的に何を気をつけて設計すべきかと
教授に訪ねたところ
「格納する最大のデータ数より、ハッシュ法の大きさを大きくし、ハッシュ値が一様なハッシュ関数を構築する」
と解答してくれたのですが、意味が理解できませんでした。
「ハッシュ値が一様なハッシュ関数」とは
「ハッシュ値がすべてバラバラになるようにするハッシュ関数」
という意味だと思うのですが、
「格納する最大のデータ数より、ハッシュ法の大きさを大きく」
という部分がどういう意味かわからないです。
どういう説明をすればいいのでしょうか。

「格納するデータよりハッシュ表を大きくし、ハッシュ値が衝突しないようなハッシュ関数を構築する」
でいいのでしょうか？

[amehirune]

うーん、多分そういうことでいいのでしょう。

例えば、いくらハッシュ値が一様になるようなハッシュ関数が設定されてたとして、
そのハッシュ値の取りうる範囲が０～１００だったとしたときに、扱うデータ数が１５０とか１０００とか、
まあハッシュ値の最大数１００を超えるような量だった場合にはコリジョンは避けられませんからね。

一方でハッシュ値の取りうる範囲よりも大きいデータ格納範囲を用意してあった場合、コリジョンは避けられるはずです。
そういうことを言いたいのではないでしょうか。

間違っていたらごめんなさい。

[いわん]

一様なハッシュ関数について、再ハッシュ法ということであれば、意味合いは少し違ってくるかもしれません。

ハッシュ値が衝突したとき、別の場所を探す手順を再ハッシュといいます。
最も簡単な方法として、ハッシュ値の位置から一つずつ後ろに検索していく方法があります。
このとき、ハッシュ値が特定の位置に偏っていると衝突が発生する可能性が高くなり、再ハッシュの手間が大きくなってしまいます。
ハッシュ関数の出力が、全体に一様に拡散ようなもの考えよということではないでしょうか。