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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Toshita
記事: 23
登録日時: 9年前

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

#1

投稿記事 by Toshita » 9年前

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

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

アバター
amehirune
記事: 181
登録日時: 11年前
住所: どっか
連絡を取る:

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

#2

投稿記事 by amehirune » 9年前

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

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

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

間違っていたらごめんなさい。
ほら、来いよ!! 誤字や矛盾を指摘したい奴から、前に出てこいよぉおおおおおおおッ!!!
※都合により、不定期でしか現れません。即返などはできませんのでご了承ください※

いわん

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

#3

投稿記事 by いわん » 9年前

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

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

閉鎖

“C言語何でも質問掲示板” へ戻る