キャッシュ関数の限界

**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)で出来る」と言われたのですが・・・

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

**名無しさん＠お腹いっぱい。** · 2006/10/19(木) 01:01:07

>>8
つまり、順次データを入れていくとしてk番目に入れられたデータの
ハッシュが衝突する確率がPk

**名無しさん＠お腹いっぱい。** · 2006/10/22(日) 11:02:46

スレタイですべて台無し

**名無しさん＠お腹いっぱい。** · 2006/11/11(土) 22:34:28

>>11　禿げ堂
年寄りです。
昔、RAIDというディスクがなかったころ、データベースにデータを書き込んだら
ディスクのどこに書いたか、ほぼわかる時代がありました。２０年ほど前ですが。
そのころは、キーからハッシュ関数をとおして、データを格納する場所をきめて
いました。
当然、キーは満遍なく存在しないことは多いです。（例えば、郵便番号をキーの
一部として住民に番号をふっていくと、都会の郵便番号ではレコードがやたらと
多いし、僻地の郵便番号ではレコードはスカスカになります。）
そのため、偏りのあるハッシュ関数を作ることにかなり苦労しましたね。

学生が先祖帰りの研究してるみたいで、ちょっとおもしろかったので。。。

**名無しさん＠お腹いっぱい。** · 2006/11/13(月) 15:28:09

スレタイを見て、俺の知らないことが２ちゃんねるに書いているかと
あせった

中身をみて安心した

ハッシュ関数も一方向性ハッシュ関数も違いが理解できない連中が偉そう
にレスしているので、さらに安心した

レスってなんですか？

**名無しさん＠お腹いっぱい。** · 2006/11/13(月) 20:15:59

>>7
6じゃないけど、↓こういうことじゃないかな。

同じメッセージに対して、SHA1でもMD5でも衝突する。
そんなメッセージを見付けられるかどうか。
もし見付けられないなら、SHA1やMD5を組み合わせるだけで
安全なハッシュ関数になるんじゃないか。

まあ、いろんな意味でスレ違いなんだが。