[過去ﾛｸﾞ] /**ファイルシステム総合スレ その7**/ (955ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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 へのレスです。
68: 2007/03/15(木)01:16 ID:bcv11DeB(3/3) AAS
>>66
その通りなんだけど、
取得時に線形探索をしていて、挿入時に線形リストを作っていない
これは考えにくいよね。
俺も寝ます．．．
69(2): 25 2007/03/15(木)05:37 ID:D+pJpsyj(1) AAS
いろいろ調べていただきありがとう。
結局、最初の疑問にもどるのだけど、コリジョン処理をきちんとしているなら
効率的なファイル管理のできる上限は限られるものの、ファイル数は制限されないよね？
とすると…と思っているうちに動作の説明図を思い出した。
バージョン3では3段、バージョン4では4段のハッシュを作ってるということのような気がする（数値はうろ覚えなので4と5だったかも）。
B+（B*かも）Treeのはずなのに子ノードがたくさんあるような図だったので
なんでだろうなと不思議に思っていたけどやっとつながった感じです。
ありがとう。
70(1): 2007/03/15(木)15:14 ID:8XNS/iOc(1) AAS
>>69
> バージョン3では3段、バージョン4では4段のハッシュを作ってるということのような気がする
それは違うと思うよ。
>63の意見が正しいと思う。
71: 70 2007/03/15(木)19:35 ID:jde9a+dY(1) AAS
>>69
今更悪いけど、
ハッシュ値のBTreeを３−４段作っているという意味なら、
それは正しいかも。
72: 2007/03/17(土)01:34 ID:G8ouJGaS(1) AAS
ディレクトリってどういう仕組みでできてるんですか？
ディレクトリマークのついたファイルに
ファイル名と対応するinodeが羅列してあるとかですか？
73: 2007/03/17(土)01:37 ID:Nt6qQYb8(1) AAS
大昔のSysVはそうだったな
74: 2007/03/17(土)12:34 ID:nFh7s+ol(1) AAS
linuxはext4がデフォになったんだって？（ｗｋｔｋ
75(1): 2007/03/18(日)10:53 ID:CpnI9Z16(1) AAS
わくつき？わかたけ？なに？
76: 2007/03/18(日)10:56 ID:6pRaIZ5X(1) AAS
わくてか
77: 2007/03/18(日)13:18 ID:VQ3UO8en(1) AAS
>>75
若貴(わかたか)。
昔一世を風靡した兄弟横綱だよ。
78(1): 2007/03/20(火)01:30 ID:WFL4qjLS(1/2) AAS
とかち・・・つくちて・・・
79: 2007/03/20(火)01:49 ID:5ZGCVJjs(1) AAS
Reiserfs以外盛り上がらないスレだね
80(13): 2007/03/20(火)02:05 ID:aZRbC5iM(1) AAS
Linux板だしね
上下前次1-新書関写板覧索設栞歴
あと 875 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.061s