H17秋 問２

質問

この問題を解く前に何を言っているのかが分かりません。教えてください。その次に解き方を教えてください。

0000 ～ 4999 のアドレスをもつハッシュ表があり，レコードのキー値からアド
レスに変換するアルゴリズムとして基数変換法を用いる。キー値が 55550 のとき，
アドレスはどれか。ここで，基数変換法ではキー値を 11 進数と見なし，10 進法
に変換した後，下 4 けたに対して 0.5 を乗じた結果(小数点以下は切捨て)を
レコードのアドレスとする。

　ア　0260

　イ　2525

　ウ　2775

　エ　4405

回答No.4

noname#50176

メモリアドレスが以下のようにあります。
0000（番地）: 0（0000番地のデータ）
0001（番地）: 1（0001番地のデータ）
：
：
4999（番地）: 255（4999番地のデータ）
※本来アドレスは16進数で表示するので、0000h～1387h です。
（問題文では一度10進に変換してその後、16進変換していないので
必然的にアドレスは10進数です）
上のカッコの説明は理解しなくても大丈夫ですができるだけ
理解してみてください。

ここでキー値をハッシュ値変換プログラム（以後プログラムと言う）
に渡してプログラムが専用の計算で実アドレスを算出します。
（パスワードを入力して目的の何かを得る感覚と考えてください）

≪流れ≫
１．ユーザーがキー値 55550 をプログラムに入力
２．プログラムがキー値を実アドレス
すなわち実際に欲しいデータが格納されているアドレスに変換
・11進数の 55000 を 10進数にするので 11(桁-1)乗の重みを
かければよく、
5*11(5-1)乗+5*11(4-1)乗+5*11(3-1)乗+5*11(2-1)乗+0*11(1-1)乗
=73205+6655+605+55+0=80520
下4桁は、0520=520 これに 0.5 をかけて、520*0.5=260=0260
（先頭の0は4桁合わせのものです）
冒頭のメモリアドレス内に存在する、0260番地 に目的のデータ
があります。

ハッシュ法はハッシュ編成形式のファイルなどで使われ
ハッシュ探索を用います。
キー値から直接アドレスを導くので探索法の基礎である
線形探索法、二分探索法、ブロック探索法と違い理論上1回で探索
できる（目的データを取得できる）わけです。

ただしハッシュではあくまで一意外計算（計算の答えがダブる）で
例えば、キー値の10進上4桁と下4桁の和の下4桁が答えなら
（実際はこんな簡単な計算はありませんが考え方として)
41000=4100+1000=5100
95546=9554+5546=15100=5100
と重なりますね。
これが「シノニム現象」（衝突する、重複すると言うこと）です。

回答No.3

ymmasayan

解き方はNo.1さんの書かれたとおりです。

なぜこんな面倒なことをするのかですが。
ハッシュというのは非常に多くのキーの種類が存在する可能性があるが
同時に存在するものは非常に少ないと言うときテーブルのレコード数を節約しようとするものです。
できるだけバラバラに入れたいので凝ったことをやるわけです。
この問題では少なくとも55550種類のキーが存在する可能性が有りますが
マックス同時存在キー数を5000(実際はその何割か)としています。

回答No.2

tysdtyhsdy

答えのみ書いてしまったので説明を。

0000 ～ 4999 にデータが記録されています。
記録されているアドレスを教えたくないが、他の人にもデータが見れるようにしたいときに、キー値を使います。
この例の場合は、利用者はキー値「55550」をいれると「0260」に記録してあるデータを読めます。

この使い方は一例なので、他にも記録するときに使用したりなど、使い道は多様です。

回答No.1

tysdtyhsdy

11進数[55550]
↓
10進数[80520]
↓
下4桁[0520]
↓
×0.5[260]
↓
答え[ア 0260]