[過去ﾛｸﾞ] /**ファイルシステム総合スレ その7**/ (955ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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種類存在します。
．．．
もうひとつの方法は、同一のハッシュ値をとるデータを線形リストの形で保持し、
66(2): 63 2007/03/15(木)01:05 ID:QpjDINEj(1/2) AAS
いやそうなんだけど、挿入時に何かの理由でエラーとしても、
線形探索がない場合と同様に動くでしょ？(もう寝ます)
70(1): 2007/03/15(木)15:14 ID:8XNS/iOc(1) AAS
>>69
> バージョン3では3段、バージョン4では4段のハッシュを作ってるということのような気がする
それは違うと思うよ。
>63の意見が正しいと思う。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.037s