キャッシュ関数の限界

**age** · 2006/10/10(火) 11:32:35

今データベースで使われるようなハッシュ関数の限界
というものを調べています。

ハッシュ関数に関して初心者です。

もちろんデータの偏りに対してどういったハッシュ関数
を選択するかによってハッシュ関数の検索能力が変わる
と思い、一概には言えないと分かってますが、ハッシュ関数
の限界というものをある程度定量的に述べることが出来ないか？
と考えています。例えば具体的には，データの定義域が2の32乗
あって，データの数が2のN乗としたときに，Nが３２に近いと
ハッシュの検索回数が急激に増加するとか，そういう感じの
特性を知りたいと思っています．
もし知ってたら（ポインタ（論文等）でもいいので）
教えてください。

またデータの偏りが変わった場合に、その偏りに
応じて適当な関数を作り出すとか出来るのでしょうか？

質問ばかりで申し訳ありませんが、ご教授のほど
よろしくお願いいたします。

**名無しさん＠お腹いっぱい。** · 2006/10/10(火) 16:34:21

俺もデータベースについては疎いけれど，
ハッシュの検索回数ってどういう意味？

2^32というのはハッシュされたデータの長さだとして
その定義域が2^32でそれが満杯になろうとも
ハッシュする回数は一回なはず．
ハッシュが衝突した場合はハッシュされたデータの値で
インデックスされた場所にリンクリストを
作るものだと理解しているのだけど．

ハッシュが衝突する頻度を知りたいという意味ならば
最近使われている十分いいハッシュ関数ならば
単純な統計の計算ですむし
性質の悪いハッシュ関数の話をしているなら
そのハッシュ関数の名前を言ってくれないと答えようがない．

データが偏っていても極めて特殊なというか悪意をもって
データの偏りをうまく設計するぐらいしないと，
最近使われているハッシュ関数ならば問題が起きることはない

**age** · 2006/10/13(金) 11:39:18

>ハッシュの検索回数ってどういう意味？

言葉が不適切で申し訳ありません。

>ハッシュが衝突する頻度を知りたいという意味ならば
その通りです。

>最近使われている十分いいハッシュ関数ならば
>単純な統計の計算ですむし

統計の計算ですむんですか。どういう計算をすれば衝突頻度が
分かるのでしょうか？
またすぐに使える十分にいいハッシュ関数（Linux標準搭載とか、
プログラムが公開されているとか）ハッシュ関数の名前を教えて
いただけないでしょうか？

くれくれ君で申し訳ありません。再度ご教授いただけると幸いです。

**名無しさん＠お腹いっぱい。** · 2006/10/14(土) 12:38:50

で、キャッシュ関数って何ですか?

**名無しさん＠お腹いっぱい。** · 2006/10/14(土) 16:40:54

k番目に使われたエントリのハッシュが
既に使われている確率をPkとして
ハッシュ関数の値域の大きさをNとすると、
P2=1/N
P(k+1)=Pk+(1-Pk)(1/N)
この漸化式を解くと
Pk=1-(1-1/N)^(k-1)
でいい?

ハッシュ関数の例としてはMD5とかでいいんでない?
データベースに向いてるかは知らないけど。

**名無しさん＠お腹いっぱい。** · 2006/10/14(土) 20:39:20

MD5とSHA1とCRC32が同時に衝突することは現実的にありうるだろうか。

**名無しさん＠お腹いっぱい。** · 2006/10/14(土) 21:06:12

同時に衝突ってどういうことだよ。MD5は16バイトだしSHA1は20バイトだろ。

**age** · 2006/10/15(日) 17:55:39

>k番目に使われたエントリのハッシュが
>既に使われている確率をPkとして

大変申し訳ありませんがもう少し詳しく説明して
頂けないでしょうか？

>ハッシュ関数の値域の大きさをN
Nはデータ数だと考えればよいでしょうか？

「ハッシュ関数の検索はO(1)で出来る」と言われたのですが
これは本当なのでしょうか？データ数がNであれば、最悪N回
ハッシュ関数で計算をしなければならないので、O(N/2)くらい
だと思っているのですが間違いでしょうか？

**age** · 2006/10/15(日) 22:52:55

>ハッシュ関数の検索はO(1)で出来る」と言われたのですが・・・

完全に勘違いしてましたすみません。