キャッシュ関数の限界

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

スレタイですべて台無し

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

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

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

中身をみて安心した

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

レスってなんですか？

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

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

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

>>13
あのな、お前みたいなヤシが一番、社会に出ると浮くからさ。
二度と、社会に出てくるな。大学か刑務所にいろ。

てっきりCのregister修飾子みたいなcache修飾子の話かと…

キャッシュ関数てなに？現金なの？ って思ったら
ハッシュ関数のTYPOかよ

>>13
あんたまとも

>>15
恥かしい奴だな

>>18
そんなに悔しかったか?

この板おまえしか来てねぇじゃん

一人でｼｺｼｺｼｺｼｺ自作自演して楽しいですかｗ

gesut
sesut

gesut
gesut

てすと

N人のグループの中に誕生日が同じ人の組みがある確率、
。。。。
そういったことは良く知られている。

第一幼稚園(〒485-0029小牧市中央六丁目101番地) http://www.komaki-aic.ed.jp/youchien/
Red Robin Kindergarten(Australia) http://www.redrobin.com.au/
南立誠幼稚園(〒514-0003津市桜橋2丁目39) http://www.res-edu.ed.jp/y-minamirissei/
Gray Elementary School(Canada) http://www.geocities.com/Athens/Styx/1630/
小中台幼稚園のホームページ(〒263-0043千葉市稲毛区小仲台8-20-1) http://www.ans.co.jp/k/konakadai/
小ヶ倉幼稚園(〒850-0961長崎市小ヶ倉町1丁目570番地の1) ttp://park.zero.ad.jp/~zbf27618/
Mary Kindergarten(Thai) http://www.marykind.th.edu/
mmmmm minkee(Australia) http://forums.nappiesaustralia.com.au/viewtopic.php?id=3185
十三愛光会愛光保育園(〒532-0023大阪市淀川区十三東１丁目13-29) http://www3.ocn.ne.jp/~aikou-n/
中台幼稚園(〒２７４−０８２４船橋市前原東４−１６−１１) ttp://www.kidslink.jp/nakadai/
中台幼稚園・保育内容(〒２７４−０８２４船橋市前原東４−１６−１１) ttp://www.kidslink.jp/nakadai/main_4_0.html
中台幼稚園・一日の活動内容(〒２７４−０８２４船橋市前原東４−１６−１１) ttp://www.kidslink.jp/nakadai/main_4_5.html
中台幼稚園・募集要項(〒２７４−０８２４船橋市前原東４−１６−１１) http://www.kidslink.jp/nakadai/main_12_0.html
少林寺小学校(堺市堺区少林寺町東４丁１−１) http://www.sakai.ed.jp/shorinji-e/
穴切校舎(〒400-0034甲府市宝2丁目8-19) http://www.anagiri-e.kofu-ymn.ed.jp/
九条幼稚園(〒550-0027大阪市西区九条2-19-18) http://www.ocec.ne.jp/yochien/kindergarden/kujo/index.html
西幼稚園(〒５８９−００２１大阪狭山市今熊１丁目５０番地) http://nishi-es.osakasayama.ed.jp/kindergarten/nishiyoutien.htm
四番町保育園(郵便番号１０２−００８１ 千代田区四番町11番地) http://hothot.city.chiyoda.tokyo.jp/yonbantyou-hoikuen.htm
黒東っ子の合言葉(〒939-0634下新川郡入善町小摺戸402) http://www.tym.ed.jp/sc6/gaiyou/aikotoba2.JPG

中間グレイ灰色イエロー黄色中間中間中間中間中間中間中間地球 http://image.space.rakuten.co.jp/lg01/76/0000243776/31/imgdf644215zik0zj.jpeg
Middle gray yellow middle middle middle middle middle the earth http://image.space.rakuten.co.jp/lg01/76/0000243776/31/imgdf644215zik0zj.jpeg

コテタンを処理するすれっど 第8部
http://choco.lv3.net/test/read.cgi/saitama/1190627337/273

(↓1024byteちょうど)
gw.T.Ygwudab.V.Tacisdlis.Tdldlc,.S.Vacacugud.Vc,beisdludisis.V.Yabgwbeac.K.Kdlc,.Y.Vacabgwbe.V.Y.Yis
c,ugis.Kac.Kacab.V.S.Tisud.Ybeisbeisisisc,.Sc,.K.Kugdlababgw.Y.Sac.Sgwisdl.Yudc,ugacuddlacugbe.Kgw.V
ugug.V.Sabbe.S.Kab.Vgwdl.Sugisdldl.Tgw.Ydlc,dlgw.Kugacac.Sac.T.Yisgwdl.T.Ydlgw.Yug.Vugbeisdlugud.Y.V
.Vdl.Vudisc,.S.Vis.Y.Tgwc,.Tisc,dlbe.Y.Tug.Tc,.Kisacug.Yugc,c,udgwisisdlacgwdldlabdl.Kgwudacab.T.Kdl
gw.S.V.Tc,.Tc,.K.K.Yis.Y.Yug.T.Vgwdlbe.V.Tug.Kc,isudbedlab.Vabbe.K.Tdlbeabacud.V.Sacudbeisc,.K.Sc,.Y
c,.Kdlud.K.Tc,.Y.Kgwc,isugdlbe.Sbec,.Sugisugc,abc,c,.Ybec,gwug.Sugbedlac.Yc,.Y.Yc,bebeisc,dlc,acacc,
beisugc,gw.Tisbeugugdl.S.S.Tacug.V.K.Sac.Kacc,.Vc,ac.Ybeudgw.Kababud.Kabgw.Kc,.Vc,.Tacbe.Y.V.S.Ybegw
.Y.Vbe.Ybebeud.Vdl.S.Vbe.Kugbe.Kisuggwdldldlug.Tc,acgw.Kbebe.V.T.Kuddlc,abacug.Visis.K.Kgwug.Vab.Kgw
.Ygw.Tgw.S.T.Kdlgwgwdl.Sgwabdlab.T.S.Tc,is.Sudac.Sabud.Kudabgw.Ygw.Sacbeabis.Sugisis.Tudbeudbe.Yacis
.V.Yacugc,.Sisacc,ac.V.T.Y.Kc,ab.Sac.V.T.Tbeisac.Vud.Kbe.V.Vac.Ybeabbegw.Visab.Vc,.Vgwabisac.T.K.K.V
ugab.T.K.Yc,c,.V.Sacacug

コテタンを処理するすれっど 第8部
http://choco.lv3.net/test/read.cgi/saitama/1190627337/10

(↓1024byteちょうど)
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンンン
ンンンンンンンンンンンン

コテタンを処理するすれっど 第8部
http://choco.lv3.net/test/read.cgi/saitama/1190627337/281

(↓1024byteちょうど)
Beudugugis.Kdl.K.K.Vbe.Vc,udbeacudud.Tis.Kudab.V.S.K.Kud.V.S.Tdlc,gwis.Yac.Tacacc,ac.Vac.Yudac.Tud.K
abug.Kgw.Kisbeugisisbe.T.Sdlc,.Vab.K.Tis.Tac.Yug.2230837isuggwgwugdlgw.Sisbe.Vgwdlbebeugab.Vdlis.Kdl
beis.K.S.Kc,udc,is.T.K.Kacud.Ybe.Tdlbe.Vbec,.Tabuddl.Tbec,gwabacbec,ugisbeac.Sis.K.Ydlbebeacug.Sc,.Y
c,ugc,.S.Sugdldlac.T.T.Sgwuggwugac.Yc,beis.Y.Tgw.Kgw.Yisab.T.V.V.Vbedlabud.R.Tabacud.Ydl.K.Ygw.Vdlug
ababc,.Tdlacisgwgw.Kugbec,.Kacudab.Vab.S.Vc,gw.Sc,.Kugdlacgwbebebe.Vabugud.Yugugugug.Sc,.V.T.Kud.Tud
ac.Yacc,ugacac.2787789767464797681292696508751103631576599476859391204527659264888725469127263isgwud
gwdldlud.Kdl.K.Yab.Vdlacabdlisuggw.Kc,dlacdlacisabdl.Yabbeac.Sug.Kgw.Kuddlbeud.Tc,is.Tdlbec,gw.Kc,.S
ac.Sc,dlud.Sudab.Yuguggw.V.Sugugacdl.Ybeisdlisab.Tabgwis.Tgwc,be.Kudududc,dl.Vudbeacdlisgw.S.K.S.Yis
acac.T.Kis.Tdludgwacbedl.Kisabbeabab.V.Vdl.Y.Y.T.K.Sacbegw.Yug.V.T.Kacgw.Tabugud.Vbeac.V.Vbedlac.S.T
.Sisabgwdldl.S.Yugbegw.Visabababc,.Vabc,.T.Sabgwab.Ygwab.Kud.Kgwudacc,.Sisacacisgwgwbeab.Tudud.Sug.S
acud.S.Kbe.V.S.Tbe.Sugi.

第一◆◆◆(〒485-0029小牧市中央六丁目101番地) http://www.komaki-aic.ed.jp/youchien/
Red ***** ************(Australia) http://www.redrobin.com.au/
南◆◆◆◆◆(〒514-0003津市桜橋2丁目39) http://www.res-edu.ed.jp/y-minamirissei/
Gray *****************(Canada) http://www.geocities.com/Athens/Styx/1630/
小◆◆◆◆◆◆◆◆◆◆◆◆(〒263-0043千葉市稲毛区小仲台8-20-1) http://www.ans.co.jp/k/konakadai/
小◆◆◆◆◆(〒850-0961長崎市小ヶ倉町1丁目570番地の1) ttp://park.zero.ad.jp/~zbf27618/
M*** ************(Thai) http://www.marykind.th.edu/
mmmmm m*****(Australia) http://forums.nappiesaustralia.com.au/viewtopic.php?id=3185
十三◆◆◆◆◆◆◆◆(〒532-0023大阪市淀川区十三東１丁目13-29) http://www3.ocn.ne.jp/~aikou-n/
中◆◆◆◆(〒２７４−０８２４船橋市前原東４−１６−１１) ttp://www.kidslink.jp/nakadai/
中◆◆◆◆◆◆◆◆◆(〒２７４−０８２４船橋市前原東４−１６−１１) http://www.kidslink.jp/nakadai/main_4_0.html
中◆◆◆◆◆◆◆◆◆◆◆◆(〒２７４−０８２４船橋市前原東４−１６−１１) ttp://www.kidslink.jp/nakadai/main_4_5.html
中◆◆◆◆◆◆◆◆◆(〒２７４−０８２４船橋市前原東４−１６−１１) ttp://www.kidslink.jp/nakadai/main_12_0.html
少◆◆◆◆◆(堺市堺区少林寺町東４丁１−１) http://www.sakai.ed.jp/shorinji-e/
穴◆◆◆(〒400-0034甲府市宝2丁目8-19) http://www.anagiri-e.kofu-ymn.ed.jp/
九◆◆◆◆(〒550-0027大阪市西区九条2-19-18) http://www.ocec.ne.jp/yochien/kindergarden/kujo/index.html
西◆◆◆(〒５８９−００２１大阪狭山市今熊１丁目５０番地) http://nishi-es.osakasayama.ed.jp/kindergarten/nishiyoutien.htm
四◆◆◆◆◆(郵便番号１０２−００８１ 千代田区四番町11番地) http://hothot.city.chiyoda.tokyo.jp/yonbantyou-hoikuen.htm
黒◆◆◆◆◆◆◆(〒939-0634下新川郡入善町小摺戸402) http://www.tym.ed.jp/sc6/gaiyou/aikotoba2.JPG

デカいの　ブチ込んだ　最後までブチ込んだ
デカいの　ブチ込んだ　最後までブチ込んだ
デカいの　ブチ込んだ　最後までブチ込んだ
ブチ込んだ　ブチ込んだ　ブチ込んだ　アォー
パラッパッ　ブチ込んだ　最後までブチ込んだ
エロッ　ブチ込んだ 　最後までブチ込んだ
エロッ　ブチ込んだ 　最後までブチ込んだ
ブチ込んだ　ブチ込んだ　アォー

いまさらながらレスしてみる

>>1 そもそもハッシュ関数というのがデータの偏りに限りなく依存しないように設計されていて、1文字違っただけでもまったく異なるハッシュを生成する。
例えばCRCなんかは演算でオーバーフローやアンダーフローを故意に発生させて逆算不可能にさせていたりする。（→どのタイミングでフローしたかがわからないので逆算できなくなる）
ちなみにハッシュ関数は検索を行わないので検索能力が変わることはない。検索能力が変わるのは与えられたハッシュ値を検索するアルゴリズムのほう。
もちろんハッシュ関数が生成するハッシュ値のとりうる範囲以上のデータ量が与えられたら、そのうちの少なくとも1組は衝突する。

>>6 >>14の言っている意味だと解釈すれば、衝突を起こす可能性はある。
だが、その衝突するファイルを演算して故意生成するのが難しくなるように考えられているのがハッシュ関数だから、いくつかのハッシュを組み合わせて同時に衝突するというのは現実的にはありえない。
ものすごい記憶空間とものすごい演算速度を持ったコンピュータが出現すればそのうち見つかるかもしれない･･･

>>9 O(1)になるかO(N)になるかとかは検索に使うアルゴリズムに依存する。
つまり無限に利用できるメモリ空間（現実にはありえないが）を使ってテーブルをつくり、ハッシュ値をインデックスにしてメモリにアクセスすればO(1)になるし、線形探索すればO(N)になるってだけ。