【基本情報技術者】ハッシュ関数

Question

基本情報技術者

10進法で5桁の数字a1,a2,a3,a4,a5をハッシュ法を用いて配列を格納したい。
ハッシュ関数をmod（a1+a2+a3+a4+a5,13）とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321は配列のどの位置に入るか？

ここで、mod(x,13)の値は、xを13で割った余りとする。

【答え 2】

mod（a1+a2+a3+a4+a5,13）でいう13とはa1というのはどういった意味を持つ
数字ですか？

また、５＋４＋３＋２＋１を13で割ればなんで、この問題の
答えが出るのかいまいちわからないです。

お手数ですが、ご教授お願いします。

Comments

[swordone]

とりあえず、勉強しているその本にここで書いた文章がそのまま載っているなら、説明以前に日本語が不自然なので本を変えた方がいいかも

[退会済みユーザー]

以下に全く同じ問題があるので過去問そのままでしょう。http://www.web-mondai.com/common-question-data/detail/bid/30/qn/7

Answer 1

そもそもハッシュ関数がどんなものなのか理解できていない、のがあるのでしょうね……
例えば…そうですね、高校あたりの全校生徒の名簿を考えましょうか。
これを分類するために、姓が「あ」行、「か」行、「さ」行……とで分類するようにしましょう。
鈴木さん、を捜したければ、全部を捜すのではなく、「さ」行の中からだけ探せばよいですね。

これもハッシュの考え方が入っています。この場合のハッシュ値は「姓の先頭1文字の子音」です。
※ですから鈴木さんも佐藤さんも島田さんも瀬名さんも曽我さんも、同じ「さ」のハッシュ値です

この方法でいけば、どんな姓の人でも、10種類（あかさたなはまやらわ）に分類できます。（海外には「ん」で始まる姓をもつ方もいらっしゃいますが…）
こうすることで探索や一致判定を素早く行えるのです。
※ハッシュの性格上、同じハッシュ値＝同一 は必ずしも正しくありませんが、違うハッシュ値＝同一ではない、は正しいので、判定が楽になる

問題だと、5桁の数値を、13個ある配列のどこかに格納したいから、0～12 のいずれかの値が返るようなハッシュ関数を作っているわけですね。（13で割った余り(mod) は、0～12 のいずれか）

Answer 2

また、５＋４＋３＋２＋１を13で割ればなんで、この問題の

答えが出るのかいまいちわからないです。

↓

mod(x,13)の値は、xを13で割った余りとする。

Comments

[ai5]

お返事遅くなり申し訳ございません。
皆様ありがとうございました。
最初と比べ前進しました。

Answer 3

<最初に簡単な説明をしておきます>
データを配列に追加したり削除したりするようなプログラムでは、データをいれる場所(配列中の位置)が集中しないにしたほうがデータの衝突（既に値が入っている配列要素に値を入れようとする事）する可能性が低くなるのでプログラムが高速になります。
こうしたプログラムで、データをいれるバラついた位置を決めるのに使われるのがハッシュ値です。（ハッシュは英語のHashで、値をまとめずバラバラな位置にデータを置く事から、そう呼ばれます）
そして、ハッシュ値を算出する関数は、ハッシュ関数と呼ばれます。

<ここから本題>
「10進法で5桁の数字a1,a2,a3,a4,a5」というのは、a1が５ケタの数字の最上位桁の数字、a2が上から２桁目の数字、、、a5が上から5桁目の数字を表すという事です。
10進法で5桁の数字が54321だとすると
a1=5
a2=4
a3=3
a4=2
a5=1
となります。

ハッシュ関数が、mod（a1+a2+a3+a4+a5,13）で
a1=5
a2=4
a3=3
a4=2
a5=1
なのですから、ハッシュ値（ハッシュ関数で求まる値）は、mod(5+4+3+2+1,13)=mod(15,13)=2 となります。（15÷13= 1 余り 2)

このハッシュ関数 "mod（a1+a2+a3+a4+a5,13）" では、０～１２の範囲の整数が求まります。
それをデータを格納する位置に使うという事は、大きさが１３の配列をつかうようなコードで、配列のインデックスが０から始まるようなプログラミング言語で記述する事を想定しているのだろうと推測されます。
これが１３の持つ意味です。

Answer 4

ハッシュ値というのは、あるデータをコンパクトに圧縮したもので、その圧縮をする関数をハッシュ関数といいます。

圧縮というと、gzip などを思い浮かべられるかもしれませんが、これらは可逆圧縮と言って、圧縮された値から元の値を復元できます。ハッシュは、復元不可能なほどに圧縮(不可逆圧縮)することによってごく小さなデータに変換することを目的にしています。
ハッシュ関数を使えば、同じデータは必ず同じハッシュ値に変換されます。しかし、同じハッシュ値から元の値は求められず、違うデータが同じハッシュ値に変換されることもあります。

ハッシュ関数はハッシュ値を求める関数というくらいの意味で、この場合は 5 桁の数値を圧縮するために各桁を足して 13 で割った余りを求めるという操作をしています。これにより、0 から 12 までのハッシュ値が得られます。
そのようにハッシュ関数のアルゴリズムを決めたので、そのアルゴリズムに従って変換すれば求めるハッシュ値が決まるということです。

Answer 5

「10進法で5桁の数字a1,a2,a3,a4,a5」と言っているので、5桁の各位がa1,a2,…に対応すると言うことでしょう(不親切な書き方ですが)。
13は適当です。強いて言えば、このような「割り算の余り」をハッシュに用いる場合、素数が使われることが多いのです。

また、５＋４＋３＋２＋１を13で割ればなんで、この問題の

答えが出るのかいまいちわからないです。

ハッシュ関数をそう決めたからです。

Answer 6

そういう関数だからです。

mod(x,13)の13の部分は何でもいいのです。
その問題がたまたま13を指定していただけと考えるのがいいかと思います。