5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

キャッシュ関数の限界

1 :age:2006/10/10(火) 11:32:35 ID:5yVjp4kp0
今データベースで使われるようなハッシュ関数の限界
というものを調べています。

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

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

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

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

2 :名無しさん@お腹いっぱい。:2006/10/10(火) 16:34:21 ID:EhzedVKa0
俺もデータベースについては疎いけれど,
ハッシュの検索回数ってどういう意味?

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

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

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

3 :age:2006/10/13(金) 11:39:18 ID:LP5+WuTg0
>ハッシュの検索回数ってどういう意味?

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

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

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

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

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

4 :名無しさん@お腹いっぱい。:2006/10/14(土) 12:38:50 ID:k7O0dOEG0
で、キャッシュ関数って何ですか?

5 :名無しさん@お腹いっぱい。:2006/10/14(土) 16:40:54 ID:oO9RQOfd0
k番目に使われたエントリのハッシュが
既に使われている確率をPkとして
ハッシュ関数の値域の大きさをNとすると、
P2=1/N
P(k+1)=Pk+(1-Pk)(1/N)
この漸化式を解くと
Pk=1-(1-1/N)^(k-1)
でいい?

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

6 :名無しさん@お腹いっぱい。:2006/10/14(土) 20:39:20 ID:03LFnMk90
MD5とSHA1とCRC32が同時に衝突することは現実的にありうるだろうか。

7 :名無しさん@お腹いっぱい。:2006/10/14(土) 21:06:12 ID:SEgHUjZ/0
同時に衝突ってどういうことだよ。MD5は16バイトだしSHA1は20バイトだろ。

8 :age:2006/10/15(日) 17:55:39 ID:bSeCK4Fq0
>k番目に使われたエントリのハッシュが
>既に使われている確率をPkとして

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

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

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

9 :age:2006/10/15(日) 22:52:55 ID:bSeCK4Fq0
>ハッシュ関数の検索はO(1)で出来る」と言われたのですが・・・

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


10 :名無しさん@お腹いっぱい。:2006/10/19(木) 01:01:07 ID:K1tounfF0
>>8
つまり、順次データを入れていくとしてk番目に入れられたデータの
ハッシュが衝突する確率がPk

11 :名無しさん@お腹いっぱい。:2006/10/22(日) 11:02:46 ID:1iZTqCwa0
スレタイですべて台無し

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

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

13 :名無しさん@お腹いっぱい。:2006/11/13(月) 15:28:09 ID:LezjVgyG0
スレタイを見て、俺の知らないことが2ちゃんねるに書いているかと
あせった

中身をみて安心した

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

レスってなんですか?

14 :名無しさん@お腹いっぱい。:2006/11/13(月) 20:15:59 ID:Xva1FhEN0
>>7
6じゃないけど、↓こういうことじゃないかな。

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

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


15 :12:2006/11/13(月) 21:45:32 ID:P4q+34MG0
>>13
あのな、お前みたいなヤシが一番、社会に出ると浮くからさ。
二度と、社会に出てくるな。大学か刑務所にいろ。

16 :名無しさん@お腹いっぱい。:2006/12/10(日) 15:23:42 ID:/9Wg7Qh80
てっきりCのregister修飾子みたいなcache修飾子の話かと…

17 :名無しさん@お腹いっぱい。:2006/12/10(日) 17:27:54 ID:raWy8wYd0
キャッシュ関数てなに?現金なの? って思ったら
ハッシュ関数のTYPOかよ

18 :名無しさん@お腹いっぱい。:2007/03/14(水) 19:45:34 ID:ds7xgK/t0
>>13
あんたまとも

>>15
恥かしい奴だな

19 :名無しさん@お腹いっぱい。:2007/03/17(土) 06:10:11 ID:1kaLLIB+0
>>18
そんなに悔しかったか?

20 :名無しさん@お腹いっぱい。:2007/03/17(土) 18:43:40 ID:dD7xK2O40
この板おまえしか来てねぇじゃん

一人でシコシコシコシコ自作自演して楽しいですかw

21 :p4202-ipbf615marunouchi.tokyo.ocn.ne.jp:2007/03/17(土) 18:56:21 ID:JIpsuKNy0
gesut
sesut

22 :p4202-ipbf615marunouchi.tokyo.ocn.ne.jp:2007/03/17(土) 18:58:18 ID:JIpsuKNy0
gesut
gesut

てすと

23 :名無しさん@お腹いっぱい。:2007/07/02(月) 02:47:31 ID:GxvgocZB0
N人のグループの中に誕生日が同じ人の組みがある確率、
。。。。
そういったことは良く知られている。

24 :匿名:2007/09/28(金) 18:00:08 ID:0MQ7Sbq80
第一幼稚園(〒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大阪市淀川区十三東1丁目13-29) http://www3.ocn.ne.jp/~aikou-n/
中台幼稚園(〒274−0824船橋市前原東4−16−11) ttp://www.kidslink.jp/nakadai/
中台幼稚園・保育内容(〒274−0824船橋市前原東4−16−11) ttp://www.kidslink.jp/nakadai/main_4_0.html
中台幼稚園・一日の活動内容(〒274−0824船橋市前原東4−16−11) ttp://www.kidslink.jp/nakadai/main_4_5.html
中台幼稚園・募集要項(〒274−0824船橋市前原東4−16−11) http://www.kidslink.jp/nakadai/main_12_0.html
少林寺小学校(堺市堺区少林寺町東4丁1−1) 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
西幼稚園(〒589−0021大阪狭山市今熊1丁目50番地) http://nishi-es.osakasayama.ed.jp/kindergarten/nishiyoutien.htm
四番町保育園(郵便番号102−0081 千代田区四番町11番地) http://hothot.city.chiyoda.tokyo.jp/yonbantyou-hoikuen.htm
黒東っ子の合言葉(〒939-0634下新川郡入善町小摺戸402) http://www.tym.ed.jp/sc6/gaiyou/aikotoba2.JPG

25 :匿名:2007/09/28(金) 18:02:16 ID:0MQ7Sbq80
中間グレイ灰色イエロー黄色中間中間中間中間中間中間中間地球 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

26 :匿名:2007/09/28(金) 18:08:55 ID:0MQ7Sbq80
コテタンを処理するすれっど 第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

27 :匿名:2007/09/28(金) 18:12:41 ID:0MQ7Sbq80
コテタンを処理するすれっど 第8部
http://choco.lv3.net/test/read.cgi/saitama/1190627337/10

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

28 :匿名:2007/09/28(金) 18:29:41 ID:0MQ7Sbq80
コテタンを処理するすれっど 第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.

29 :匿名:2007/09/28(金) 18:34:47 ID:0MQ7Sbq80
第一◆◆◆(〒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大阪市淀川区十三東1丁目13-29) http://www3.ocn.ne.jp/~aikou-n/
中◆◆◆◆(〒274−0824船橋市前原東4−16−11) ttp://www.kidslink.jp/nakadai/
中◆◆◆◆◆◆◆◆◆(〒274−0824船橋市前原東4−16−11) http://www.kidslink.jp/nakadai/main_4_0.html
中◆◆◆◆◆◆◆◆◆◆◆◆(〒274−0824船橋市前原東4−16−11) ttp://www.kidslink.jp/nakadai/main_4_5.html
中◆◆◆◆◆◆◆◆◆(〒274−0824船橋市前原東4−16−11) ttp://www.kidslink.jp/nakadai/main_12_0.html
少◆◆◆◆◆(堺市堺区少林寺町東4丁1−1) 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
西◆◆◆(〒589−0021大阪狭山市今熊1丁目50番地) http://nishi-es.osakasayama.ed.jp/kindergarten/nishiyoutien.htm
四◆◆◆◆◆(郵便番号102−0081 千代田区四番町11番地) http://hothot.city.chiyoda.tokyo.jp/yonbantyou-hoikuen.htm
黒◆◆◆◆◆◆◆(〒939-0634下新川郡入善町小摺戸402) http://www.tym.ed.jp/sc6/gaiyou/aikotoba2.JPG

30 :マイケル・ジャクソン:2008/11/24(月) 21:51:23 ID:9fa7IY9T0
デカいの ブチ込んだ 最後までブチ込んだ
デカいの ブチ込んだ 最後までブチ込んだ
デカいの ブチ込んだ 最後までブチ込んだ
ブチ込んだ ブチ込んだ ブチ込んだ アォー
パラッパッ ブチ込んだ 最後までブチ込んだ
エロッ ブチ込んだ  最後までブチ込んだ
エロッ ブチ込んだ  最後までブチ込んだ
ブチ込んだ ブチ込んだ アォー

31 :名無しさん@お腹いっぱい。:2009/03/18(水) 09:13:45 ID:LYPynITM0
いまさらながらレスしてみる

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

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

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


18 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)