基本情報 過去問 ファイルシステムについて

質問

こんにちは、２０１０年１０月の基本情報技術者試験を受験して
午後試験で　５０．５０点だったものです。

趣味でプログラミングをしていて、

JavaScriptでポーカーを再現し、

同じくJavaScriptで音声は出ませんが、

http://sdin.jp/browser/casino/blackjack/

と同様の動作をするブラックジャックを作るくらいです。
( CGI, サーバーのことはよくわかりません。)

現在　暇な時間をみて、４月の同試験の受験に向けて勉強しているのですが、
わからないことが出てきましたので、質問させていただきます。

以下のサイトをみていただきたいのですが・・・

http://www.rs.kagu.tus.ac.jp/~infoserv/j-siken/H10a2/pm03.html

問４の「ハッシュ表を用いて実現するファイルシステム」
についてなのですが、

(1)　固定長レコードで，各レコードはキー部とデータ部からなる。

とありますが、キー部はファイル名であり、
問題中にはでてきませんが、
データ部は補助記憶装置に格納されている格納位置（ディレクトリ）である、
という解釈でよいのでしょうか？

ファイルを検索するとき、「与えられた式で計算したエントリ位置」　にある
キー部を捜すと思うのですが、

問題の場合では、ハッシュ表[0]～ハッシュ表[4999]まで走査を行う、
ということでよいのでしょうか？

どなたか教えていただけないでしょうか
よろしくおねがいします。

回答No.2

jjon-com · ベストアンサー

>キー値を指定すれば、なぜ直接アクセスが可能になるのでしょうか。

問題文〔ハッシュ表を用いて実現するファイルシステムの説明〕に次のように書いてあります。
--------
(3)レコードのキー値を格納する位置（エントリ位置）は，次の式で求める。
　　エントリ位置 ＝ キー値をエントリ個数で割った余り
(5)レコードのデータ部へのアクセスは，エントリ位置によって一意に決まる。
--------

----------------------------------------
>SQLをつかって、データを操作することもできないように
>思われますが・・・違うのでしょうか。

データ部の値をどのように操作するかはまったく別の話です。
例えば，5000件の社員データが格納された社員表があり，次のようなSQL文でアクセスするとします。

SELECT 社員名,性別,生年月日,所属部
FROM 社員表
WHERE 社員番号 = 10202

このとき，社員番号という属性に索引(index)が設定されていない場合は5000件全件を対象として順に走査しながら社員番号＝10202の行を見つけねばならないのに対し，社員番号に索引(index)が設定されていれば社員番号＝10202の行に即座にアクセスできることを質問者はご存じですか？　そして索引が有ろうが無かろうが，データを操作するためのSQL文は上記のまま変化はありません。（索引は別途，CREATE INDEX 文で設定しておくものなので）

今回の問４は，そのような「データ部に高速アクセスするための内部的な仕組み」に関する問いであり，データ部の値をどう操作するかについては不問にしています。

----------------------------------------
>問題文のような、ファイルの用途というのは、
>どういったものになるのでしょうか。

ハッシュ表は「キー値の取りうる範囲より，データ総数の方が少ない場合」に用いられます。

例えば，社員番号の取りうる範囲が0000～4999であり，その社員番号と１対１に対応する社員が5000人いるならば，ハッシュ関数など用いなくても，
　　エントリ位置 ＝ 社員番号
とすればよいわけです。

では，社員番号が６桁であり，取りうる範囲が000000～999999だとしてみます。データを格納するために100万件分の空き領域を確保せねばならないのでしょうか？　100万人の社員がいるなら広大なその空き領域を確保する必要があります。しかし社員数が5000人しかいないなら（すなわち，社員番号の全範囲が利用されているわけではなく，歯抜けが多いなら）必要なデータ領域の大きさは200分の１で済むはずです。そこでこの問いでは次のようなハッシュ関数を使いました。
　　エントリ位置 ＝ 社員番号をエントリ個数（=5000）で割った余り

社員番号の利用状況が歯抜けであるとはいえ，5000で割った余りが同じになる社員番号が複数使われている可能性はあります。
ハッシュの採用により，キー値を指定すれば極めて高速にデータ部にアクセスできるという大きな利点がありますが，キー値が異なるのにエントリ位置が同じになるという異常の発生（シノニムレコードといいます）という副作用は避けられません。そこでハッシュではシノニムへの対処が必須となります。これは問題文(4)で説明されています。
http://eow.alc.co.jp/synonym/

お礼

毎回丁寧に解説していただき、ありがとうございます。
とくに、用途についての解説はよく理解することができました。
また、別の過去問で分からないことが出てきたときには、
お忙しい時でなければよろしくお願いします。
貴重な時間をさいての回答、ありがとうございました。

回答No.1

jjon-com

>キー部はファイル名であり、
>データ部は補助記憶装置に格納されている格納位置（ディレクトリ）である、
>という解釈でよいのでしょうか？

違います。
「ハッシュ表には【レコードの】キー値を格納する」と書いてありますから，

キー部(　200) データ部(佐藤 一郎, 男, 1991/01/01生, 技術部)
キー部( 5201) データ部(鈴木 二郎, 男, 1992/02/02生, 営業部)
キー部(10202) データ部(高橋 三郎, 男, 1993/03/03生, 総務部)

のように，キー部１つとデータ部１つを合わせた１組で１レコードとなります。
つまり「ハッシュ表[0]～ハッシュ表[4999]」と「データ部[0]～データ部[4999]」を合わせて全体で「１個のファイル」となります。
各行が１個のファイル（すなわち，全体で5000個のファイル情報）ではありません。

>ハッシュ表[0]～ハッシュ表[4999]まで走査を行う、
>ということでよいのでしょうか？

違います。

　　> 設問１　キー値が 10005 のレコードを格納しよう とすると，
　　> 設問２　取り出すデータのキー値 → ｋ
　　> 設問３　キー指定による

と書いてあるように，キー値を指定してデータ部に「直接アクセス」する用途を想定したファイルシステムの例となります。
問題文(3)(4)で示されたハッシュ関数で求められたそのエントリ位置に直接アクセスしに行きますから，走査（一次元的に [0]～[4999] を順になぞること）はおこないません。

お礼

さっそく回答していただきありがとうございます。
全体で一つのファイルになるのですか。
解釈がちがっているときも指摘していただき、
とても参考になります。

もしよければ、教えていただきたいのですが、
キー値を指定すれば、なぜ直接アクセスが可能になるのでしょうか。
ファイル内の「番地（アドレスのようなもの）」にレコードが一意に
格納されるからでしょうか。
そのキー値から、ほぼ一意に、番地が決まる、
ということで、よろしいでしょうか。
問題文のような、ファイルの用途というのは、
どういったものになるのでしょうか。
アクセスするのにはキー値のみが必要という気がしますが、
SQLをつかって、データを操作することもできないように
思われますが・・・違うのでしょうか。

それと、また、なにかわからないことが出てきたら、
お忙しい時でなければ、よろしくお願いします。
貴重な時間をさいての回答ありがとうございました。