[過去ﾛｸﾞ] /**ファイルシステム総合スレ その7**/ (955ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
48(1): 2007/03/13(火)00:29 ID:lXY/NdrB(2/2) AAS
ハッシュ関数
外部ﾘﾝｸ:ja.wikipedia.org
wikiでも読んでろよ。
スレ違い。
49: 45 2007/03/13(火)00:42 ID:6KZPETmR(2/2) AAS
あいたた。そこまで叩かんでも。
コリジョンがあったら元のキーで照合すればいいのではないかと思っただけ。
十分一意で現実的にそうする必要がないということならそう言ってくれれば
いいのに...って力不足でごめんね。
50: 2007/03/13(火)00:56 ID:6rUQ9uSk(1) AAS
>>48
外部ﾘﾝｸ:ja.wikipedia.org
51(1): 2007/03/13(火)16:15 ID:s8sklJsb(1) AAS
wikipediaをwikiと呼ぶヴぉけ
52: 2007/03/13(火)16:20 ID:Wa+ulsOs(1) AAS
>>51
日本語でOK
53(2): 2007/03/13(火)16:25 ID:nRFOZCQM(1) AAS
Don't call wiki wikipedia (の日本語訳)
54: 2007/03/13(火)16:30 ID:p10FW4hW(1) AAS
>>53
おまえ・・・。
55(1): 2007/03/13(火)22:22 ID:AMgfTU3v(1) AAS
>>53
そりゃまwikiのことをwikipediaと呼ぶ人はほとんどいないだろ。
56: 2007/03/13(火)22:52 ID:/S3jfaN8(1) AAS
>>55
おまえは世間を甘く見すぎている。いつか手痛いしっぺ返しを食らうだろう。
57(4): 45 2007/03/14(水)00:37 ID:y4c2ZpRt(1/3) AAS
>>45 自己レスです。
外部ﾘﾝｸ[php]:homes.cerias.purdue.edu
を見たところ、確かにファイル名のハッシュ値を使っているようですが
2.6.20.2のfs/reiserfs/namei.c:1575
を見るに少なくとも指定ディレクトリ(エントリ)の指定ファイル名の
ファイルを探すときはこの値を探索した後線形探索するように
読めました(無論細部は追ってないし動かしてもいない)。
で、コリジョン＝エラーではないと思う。それだけ。
58: 2007/03/14(水)00:41 ID:y4c2ZpRt(2/3) AAS
ごめん1575行じゃなくて311行だった。
59: 2007/03/14(水)19:02 ID:VBYYEpgo(1) AAS
新ネタ投下
外部ﾘﾝｸ:journal.mycom.co.jp
外部ﾘﾝｸ:journal.mycom.co.jp
LinuxというよりBSD筋になるのかな？どうだろう？
60(1): 2007/03/14(水)21:46 ID:/NerAE7J(1/3) AAS
>>57
コリジョンが起こったファイル名で書き込みに行った場合、
衝突されたファイルを上書きしてしまうと思うが？
これを避けようとすると、毎回コリジョンの有無を調べなければならず、
ハッシュの優位性はなくなってしまわないか？
61: 2007/03/14(水)22:04 ID:/NerAE7J(2/3) AAS
>>57
レスがかみ合ってなくてスマソ。
ハッシュで探索後に、線形探索。
これではハッシュの意味が無い上にもの凄く遅くない？
62(1): 2007/03/14(水)22:16 ID:/NerAE7J(3/3) AAS
>>57
連投スマソ。
これは俺の無知だね．．．
>57はコリジョンが起こった際の処理方法についてカキコしてたわけだ。
申し訳ない。
だとすると>35の意見は果たしてどうなんだろうか？
63(3): 57 2007/03/14(水)23:53 ID:y4c2ZpRt(3/3) AAS
ハッシュを使っているのは文字列の代わりに固定サイズの短い数字を使った方が
B木のキー(の一部)として優秀なだけだと思います。ただハッシュなので、B木を
降りていった後にハッシュの元の文字列かどうかは確認する必要があり、B木の
キーで同じ値になっている部分を走査したり探索したりする必要があるのかなぁ
と思いました。
元の文字列に対してハッシュ値が現実的に十分1:1になっている(一意になって
いる)なら最後に走査したり探索したりする必要はないんだけど、B木まで使う
(レコード数が大きいことを想定している)ファイルシステム(手堅い印象)で
ハッシュが重ならないことを前提にしたりするの？と疑問が残ったので、資料と
ソースを探してみました。で、>>57 というわけ。
省9
64(1): 62 2007/03/15(木)00:34 ID:bcv11DeB(1/3) AAS
>>63
俺は>60のレスの後調べてみてわかったんだが、
> 取得側のロジックで単に同一ハッシュを線形探索している
これってコリジョンが発生した場合の対応法だよ。
検索アルゴリズム
外部ﾘﾝｸ[htm]:www2.starcat.ne.jp
さて、ハッシュ表が衝突した場合の処理方法ですが、大きく分けて2種類存在します。
．．．
もうひとつの方法は、同一のハッシュ値をとるデータを線形リストの形で保持し、
65: 2007/03/15(木)01:04 ID:bcv11DeB(2/3) AAS
あくまで個人的な意見だけれども、>25の
> ドキュメントをみるとハッシュ空間がファイル数上限を規定していると書かれてるんだが
> これってどういうことなんだろう？
これは、ハッシュテーブルの大きさに制限される、という意味じゃないかな？
66(2): 63 2007/03/15(木)01:05 ID:QpjDINEj(1/2) AAS
いやそうなんだけど、挿入時に何かの理由でエラーとしても、
線形探索がない場合と同様に動くでしょ？(もう寝ます)
67: 2007/03/15(木)01:07 ID:QpjDINEj(2/2) AAS
あ、>>66 は >>64 へのレスです。
上下前次1-新書関写板覧索設栞歴
あと 888 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.025s