質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • 基本情報技術者

    53questions

    基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

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

解決済

回答 6

投稿

  • 評価
  • クリップ 0
  • VIEW 1,252

ai5

score 32

基本情報技術者

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というのはどういった意味を持つ
数字ですか?

また、5+4+3+2+1を13で割ればなんで、この問題の
答えが出るのかいまいちわからないです。

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • swordone

    2017/03/03 15:15

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

    キャンセル

  • 退会済みユーザー

    退会済みユーザー

    2017/03/03 15:48

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

    キャンセル

  • 退会済みユーザー

    2017/03/04 16:19

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 6

checkベストアンサー

+3

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+3

また、5+4+3+2+1を13で割ればなんで、この問題の
答えが出るのかいまいちわからないです。 

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/23 16:44 編集

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

    キャンセル

+2

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

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

また、5+4+3+2+1を13で割ればなんで、この問題の 
答えが出るのかいまいちわからないです。

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

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

<ここから本題>
「10進法で5桁の数字a1,a2,a3,a4,a5」というのは、a1が5ケタの数字の最上位桁の数字、a2が上から2桁目の数字、、、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)" では、0~12の範囲の整数が求まります。
それをデータを格納する位置に使うという事は、大きさが13の配列をつかうようなコードで、配列のインデックスが0から始まるようなプログラミング言語で記述する事を想定しているのだろうと推測されます。
これが13の持つ意味です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • 基本情報技術者

    53questions

    基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。