問題の解き方

質問

基本情報技術者の、この問題がよくわかりません。
この問題はどうやって解くのでしょうか？解く前に問題の意味もあまり理解できなく、解説をお願いいたします。

●００００～４９９９のアドレスを持つハッシュ表があり、レコードのキー値からアドレスに変換するアルゴリズムとして基数変換法を用いる。キー値が５５５５０のときのアドレスはどれか。ここで、基数変換法ではキー値を１１進数と見なし、１０進数に変換した後、下４けたに対して０．５を乗じた結果（小数点以下は切捨て）をレコードのアドレスとする。

回答No.1

jjon-com · ベストアンサー

例として，キー値の範囲として00000～99999が考えられるデータを配列に格納したいとします。配列の大きさがTABLE[0]～TABLE[99999]の10万要素あれば確実に格納できますね。

では「キー値は00000～99999の10万パターンだけれどデータ総数は数千件しかない（キー値の歯抜けが多い）」場合はどうでしょう。データが数千しかないのに10万の配列を確保するのはムダですから次のような方法をとります。

例）格納配列の大きさを5000要素と決めた場合（TABLE[0]～TABLE[4999]）

データのキー値 00000～99999
　　↓
何らかの計算（ハッシュ関数と呼ぶ）
　　↓
格納位置の添字 0～4999（ハッシュ値と呼ぶ）

のように，入力値(00000～99999)→出力値(0000～4999)を求める何らかの計算をおこない，それを格納位置の添字とすればよいわけです。このときの格納配列をハッシュ表と呼びます。

何らかの計算（ハッシュ関数）はどんな計算式でもかまわないのですが，この問題では次のアルゴリズムを採用したとのこと。

レコードのキー値 55550
　　↓
キー値を11進数と見なし，10進数に変換後，下４けたに対して×0.5という基数変換法
　　↓
レコードの格納アドレス

あとの計算は，過去問の解説サイトがありますので，それを見てください。
（基本情報，17秋，問２）

参考URL：

http://computer.trident.ac.jp/examin/h171016_kihon_amkai.html

お礼

ありがとうございました。