A型システムエンジニアの勉強メモ

情報処理試験の午前問題をネタにして、解説をじっくり書きながら勉強しています。基礎は大事。

広告

基本情報技術者試験 令和元年度 秋季 午前 問16

よくある稼働率の計算問題。無理やり関係させて PC クラスタの話も。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問16

 

2 台の処理装置から成るシステムがある。少なくともいずれか一方が正常に動作すればよいときの稼働率と、2 台とも正常に動作しなければならないときの稼働率の差は幾らか。ここで、処理装置の稼働率はいずれも 0.9 とし、処理装置以外の要因は考慮しないものとする。

 

ア 0.09

イ 0.10

ウ 0.18

エ 0.19

--------------------------

解説

 

ひとつ前の問題で RAID0 と RAID1 の稼働率を計算して書いたけど、こっちの問題で書けばよかった。

koki2016.hatenadiary.com

  • "少なくともいずれか一方が正常に動作すればよいとき" ≒ RAID1 の状況 
  • "2 台とも正常に動作しなければならないとき“ ≒ RAID0 の状況

 

 

問題が聞いているのは両方の状況における稼働率の差なので、素直に各々の稼働率を計算するところからスタートする。

 

"少なくともいずれか一方が正常に動作すればよいとき"

処理装置 1 台の稼働率は 0.9 なので、故障率は 0.1 となる。

 

(少なくとも一方は正常の確率)

 = 1 -(2 台とも壊れている確率 = 0.1 × 0.1 = 0.01)

 = 0.99

 

となるので、稼働率は 0.99 であると分かる。

ちなみに全く工夫なしに以下のようにしても計算できる。

あまり意味はないけど、どうしても検算したいときには使えるかも。

 

(少なくとも一方は正常の確率)

 =(2 台とも正常の確率)+(装置 A のみ正常の確率)+(装置 B のみ正常の確率)

 =(0.9 × 0.9)+(0.9 × 0.1)+(0.1 × 0.9)

 = 0.81 + 0.09 + 0.09

 = 0.99

 

 

"2 台とも正常に動作しなければならないとき"

こちらは単純に計算できる。

 

(2 台とも正常の確率)

 = 0.9 × 0.9

 = 0.81

 

となるので、稼働率は 0.81 である。

 

0.99 と 0.81 の差が問題の聞いていることなので、正解は選択肢ウの 0.18 である。

 

 

稼働率 0.9 の機器 2 台を冗長化すれば稼働率は 0.99 になる。3 台で冗長化すれば稼働率は 0.999 にもなる。

安価な機器でも複数台で冗長化すれば、高信頼なシステムが作れる。ついでに、どれも壊れていない間は複数台分の性能を使うこともできる。

 

科学の数値シミュレーションに利用される PC クラスタシステム にもこの考え方が当てはまる。

性能も信頼性も高い特注のサーバーではなく、一般的なサーバーを数百台並べてシステムを構成する。

1 つのシミュレーションはシステムの一部(サーバー 10 台分とか)を確保して実行されるので、その時点で正常稼働しているサーバーが必要な台数だけあれば業務は進めることができる。

 

数百台もあると 2 日に 1 台くらいは壊れるので頻繁に復旧作業はしているが、利用者の業務(シミュレーション)には影響しない。

運悪くシミュレーション実行中のサーバーが故障すると影響してしまうけど、別のサーバーを確保して再実行すればいい。

 

業務に必要な物量を保てるなら、毎日何かが壊れる前提でも問題はない。

(運用する人たちは大変だけど)

 

 

前後の問題はこちら。

koki2016.hatenadiary.com

 

基本情報技術者試験 令和元年度 秋季 午前 問15

RAID についての問題。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問15

 

RAID の分類において、ミラーリングを用いることで信頼性を高め、障害発生時には冗長ディスクを用いてデータ復元を行う方式はどれか。

 

ア RAID1

イ RAID2

ウ RAID3

エ RAID4

--------------------------

解説

 

RAID(Redundant Array of Independent Disk)

Redundant:冗長

Array:アレイ、配列

Independent:独立した

なので、複数ディスクを並べて冗長な配列を作る仕組み(余計わかりにくい)。

 

RAID は複数のディスクを纏めて 1 つのディスクに見せる技術である。

ディスクを纏めるときにどのように纏めるかで、RAID0 ~ RAID6(RAID7?)の方式に分かれる。

 

よく見るのは RAID0、RAID1、RAID5、RAID1+0 あたり。

RAID2、RAID3、RAID4 は仕事でも見たことない。ので、無視する。

 

 

RAID の説明のため、以下の様な状況を考えることにする。

 

f:id:koki2016:20211121163748p:plain

あるデータがディスクに書き込みされている。

データは一定のサイズでブロック単位(図では A, B, C, D)に分割され、順番にディスクに書き込まれていく。

この状況でディスクを複数にして、RAID を構成してみる。

 

 

まずは RAID0(ストライピング) から。

 

f:id:koki2016:20211121164228p:plain

RAID0 は書き込みの高速化を目的にしている。

 

図のように、ブロック単位にしたデータを複数のディスクに分散して同時に書き込む。

ディスクが 1 台だった時と比較すると、ディスク当たりに書き込まれるブロックが 4 個から 2 個になっている。

RAID0 のメリットは、

  • データの書き込みが高速化される(複数ディスクに分散して同時に書き込むため)。
  • RAID でまとめるディスクの容量を合算した、大きな単一のディスクとして扱える。

一方のデメリットは、

  • ディスクが 1 台でも壊れるとデータが復元できなくなる(データを構成するブロックのどれかは無くなってしまうため)。

 

 

次に RAID1(ミラーリングについて。

 

f:id:koki2016:20211121165643p:plain

RAID1 は信頼性の向上を目的にしている。

ということで、問題の正解は選択肢アの RAID1 である。

 

図のように、複数のディスクに同じようにデータを書き込む。

ディスクが 1 台だった時と比較すると、各ディスクが同じデータを持つことになるので、冗長なことをしている。

RAID1 のメリットは、

  • ディスクが 1 台壊れたとしてもデータが復元できる(各ディスクに全てのブロックが存在しているため)。

一方のデメリットは、

  • ディスクが 2 台あっても、ディスク 1 台分の容量しか使えない(複製したデータの保管だけに 1 台分のディスクが消費されるため)。
  • ディスクが 2 台あっても、RAID0 のように高速化はされない。

 

 

RAID5 や RAID1+0 の説明も書こうと思ったけど、図を作るのが疲れたので省略。。。

  • RAID5 はパリティという考え方で、信頼性の向上と高速化を両立している。最低でも 3 台のディスクが必要になる。
  • RAID1+0 は、RAID1 の考えでミラーリングした環境を 2 組用意して、RAID0 の考えでそれらに分散して書き込みをするもの。最低でも 4 台のディスクが必要になる。

 

 

RAID0 も RAID1 も原理としてはディスクを 3 台、4台と増やしていくことができる。

ただし、増やすほどに RAID0 はデータが消失しやすくなり、RAID1 は不要なほど信頼性が高くなる。

 

非常に雑な定義ではあるが、障害で 1 年に 1 日使えなくなるディスクを考えてみる。

稼動率は 364日/365日 ≒ 99.726 % とする。

※ディスクの稼動率でこんな考え方は微妙ですが、そこはご容赦を。

 

RAID0 はどれか 1 台でも壊れたらデータが消失する。

RAID1 はどれか 1 台でも残っていればデータは保たれる。

 

稼動率を計算すると以下のようになる。

 

ディスク台数 稼動率(RAID0) 稼動率(RAID1)
2台 0.99452 0.999992
5台 0.98637 0.99999999...
10台 0.97293 0.99999999...

 

RAID1 は 2 台もあれば 1 年で使えない時間が 1 日から 4 分まで短くなる。5 台とかにしたらもう 1 秒にもならない。

RAID0 は 2 台だと 1 年で使えない時間が 1 日から 2 日と倍になる。5 台だと約 5 日 使えなくなる。

 

RAID0 がもっと劇的に使えなくなる時間増えるかと思ったけどそうはならず、非常につまらない結果である(定義のせい)。

 

 

前後の問題はこちら。

koki2016.hatenadiary.com

 

基本情報技術者試験 令和元年度 秋季 午前 問14

デイジーチェーン接続についての問題。スター型との比較も。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問14

 

次に示す接続のうち、デイジーチェーンと呼ばれる接続方法はどれか。

 

PC と計測機器とを RS-232C で接続し、PC とプリンタを USB を用いて接続する。

 

Thunderbolt 接続ポートが 2 口ある 4K ディスプレイ 2 台を、PC の Thunderbolt 接続ポートから 1 台目のディスプレイにケーブルで接続し、さらに、1 台目のディスプレイと 2 台目のディスプレイとの間をケーブルで接続する。

 

キーボード、マウス及びプリンタを USB ハブにつなぎ、USB ハブと PC とを接続する。

 

数台のネットワークカメラ及び PC をネットワークハブに接続する。

--------------------------

解説

 

デイジーチェーン(daisy chain)

複数の機器を数珠つなぎにする(もしくは 1 つの輪にする)ような接続方法のこと。

 

daisyヒナギクという意味で、daisy chain はヒナギクの花輪といった意味もある。

機器が数珠つなぎに接続されている様がヒナギクの花輪に似ているから、その様な接続方法をデイジーチェーンと呼ぶとのこと。

"デイジーチェーン" という言葉の響きと "ヒナギクの花輪" というイメージが個人的には全くあわない。

 

 

PC の周辺機器についても、PC から各周辺機器が順番に数珠つなぎになっていればデイジーチェーン接続と呼ばれる。

問題にある各選択肢の接続を絵にしてみると次のようになる。

 

f:id:koki2016:20211114154905p:plain

 

選択肢から除外しやすいのは選択肢ウと選択肢エの 2 つ。

どちらも分岐があって一直線の数珠繋ぎになっていないので、正解ではない。

 

選択肢アは一直線だよね、と言われそうであるが、選択肢イのように PC "から" 各周辺機器が数珠つなぎになっている接続がデイジーチェーンと呼ばれる。

ということで、正解は選択肢イである。

 

デイジーチェーンのメリットとしては接続する機器が多くなっても PC 本体に多数のコネクタを必要としない点である。

選択肢イではディスプレイを 2 台繋いでいるが、PC 本体にはコネクタが 1 つあればいい。

 

一方のデメリットとしては全ての周辺機器との通信が同じ経路を通ることと、故障の影響範囲が(箇所によっては)大きい点である。

選択肢イでは PC とディスプレイ 2 との通信も、PC とディスプレイ 1 との接続ケーブルを通ることになる。機器を増やすと経路の負荷が高まり、応答が遅くなってしまう。

また、ディスプレイ 1 が故障したら、PC からはディスプレイ 2 も使えなくなってしまう。

 

デイジーチェーン接続でつなぐ機器を増やしすぎるとデメリットの影響がどんどん大きくなるので注意が必要である。

 

 

選択肢ウやエはスター型と呼ばれる接続方法になる。

デイジーチェーンのデメリットを(全てではないが)回避できているが、ハブやスイッチなどの多数のポートを備える中継機器が必要になる点がスター型のデメリットになる。

 

選択肢ウでは中継機器として USB ハブを用いている。

USB ハブには PC からの給電のみで動くバスパワー方式と、USB ハブそのものが電源につながるセルフパワー方式がある。

キーボードやマウス程度であればバスパワー方式でも十分であるが、HDD 等を多数つなげる場合はセルフパワー方式にしないと周辺機器への給電が足りなくなる可能性がでてくる。

 

 

選択肢エでは中継機器としてネットワークハブを用いている。

複数のネットワークカメラから同時に PC へ映像データが転送されていると推測できるので、ネットワークハブには接続されているネットワークカメラ台数分のデータ転送を遅延なく処理できる性能が必要になる。

この性能はスイッチング容量という仕様で表示される。

ネットワークハブの各ポート毎の性能がどれだけ高くても、ネットワークハブ内部の転送性能(スイッチング容量)が低いと各ポートの性能が活かせなくなる。

 

 

 

前後の問題はこちら。

koki2016.hatenadiary.com

 

 

基本情報技術者試験 令和元年度 秋季 午前 問13

CPU の割込み処理についての問題。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問13

 

メイン処理、及び表に示す二つの割込み A、B の処理があり、多重割込みが許可されている。割込み A、B が図のタイミングで発生するとき、0 ミリ秒から 5 ミリ秒までの間にメイン処理が利用できる CPU 時間は何ミリ秒か。ここで、割込み処理の呼出し及び復帰に伴うオーバヘッドは無視できるものとする。

 

f:id:koki2016:20211107150520p:plain

 

ア 2

イ 2.5

ウ 3.5

エ 5

--------------------------

解説

 

選択肢の有効桁数表示があっていないことにムズムズする。

ア 2.0

イ 2.5

ウ 3.5

エ 5.0

 

 

この問題は CPU の割込みについての問題。

 

CPU が何かの処理(メイン処理)をしているときでも、ユーザのキーボード操作等があればそちらの処理を優先する。

そうしないと、キーボードを操作しても画面に反映されるのがメイン処理が終わった後になってしまい、操作性が非常に悪くなってしまう。

この場合はキーボード操作の処理が割込み処理になる。

 

 

問題の図に CPU がその時間にどの処理をしているかと、メイン処理の列を追加する。

 

f:id:koki2016:20211107172110p:plain

 

図の ①~⑨ の処理状況について以下に記載する。

 

[①:メイン処理を実行中]

割込み B が発生するまでは CPU でメイン処理が実行されている。

問題が聞いているのは図の 0 ミリ秒以降のことなので、この時間は関係ない。

 

[②:割込み B 処理を実行中]

割込み B が発生したので、CPU は割込み B の処理を実行している。

 

[③:割込み A 処理を実行中]

割込み A が発生し、割込み B と割込み A では割込み A の方が優先度高いため、CPU は割込み A の処理を実行することになる。

問題文より多重割込みが許可されているので、割込み B の処理中にさらに別の割込み A がはいってこれる。

 

[④:割込み B 処理を実行中]

割込み A が 0.5 ミリ秒で終了するので、割込み B の処理に戻る。

②で割込み B は 1.0 ミリ秒処理済みなので、④の長さは 0.5 ミリ秒になる。

 

[⑤:メイン処理を実行中(0.5ミリ秒)]

割込み B も終了したので、やっと CPU がメイン処理を実行できる。

 

[⑥:割込み A 処理を実行中]

割込み A が発生したので、また CPU が割込み処理の実行をすることになる。

 

[⑦:メイン処理を実行中(0.5ミリ秒)]

割込み A が終了したので、再び CPU がメイン処理を実行できる。

 

[⑧:割込み A 処理を実行中]

また割込み A が発生したので、また CPU が割込み処理の実行をすることになる。

 

[⑨:メイン処理を実行中(1.0ミリ秒)]

割込み A が終了したので、再び CPU がメイン処理を実行できる。

問題文が聞いている 5.0 ミリ秒まで処理が続けられる。

 

 

⑤、⑦、⑨でメイン処理を実行できていて、その時間は合計で 2.0 ミリ秒になる。

ということで正解は選択肢アとなる。

 

 

この問題では割込み処理への切り替えにかかるオーバヘッドを無視できるとしているが、実際には多少なりオーバヘッドで無駄な時間がかかるため、割込みにより切り替えが頻繁に起きないような設計が必要になる。

 

例としてこの問題の割込み A と割込み B の優先度を反対にした場合は以下のようになる。

f:id:koki2016:20211107175903p:plain

 

優先度を反対にする前と比較して、切り替えの回数が 1 回減っている。

一方で、1.0 ミリ秒で発生した割込み A の開始が 0.5 ミリ秒遅れてしまっている(割込み A の応答性が悪くなっている)。

 

割込み A の応答性を優先するのか、全体としてオーバヘッドの削減を優先するのかは、そのシステムの目的次第で決めるものになる。

 

 

前後の問題はこちら。

koki2016.hatenadiary.com

 

基本情報技術者試験 令和元年度 秋季 午前 問12

CPU のクロックに関しての問題。ついでに演算性能(FLOPS)についても。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問12

 

1 GHz のクロックで動作する CPU がある。この CPU は、機械語の 1 命令を平均 0.8 クロックで実行できることが分かっている。この CPU は 1 秒間に平均何万命令を実行できるか。

 

ア 125

イ 250

ウ 80,000

エ 125,000

--------------------------

解説

 

 

CPU についての問題。

Central Processing Unit:中央演算装置

システムエンジニアは CPU を「石」と呼ぶこともある。なんでだろう。

 

 

「1 GHz のクロックで動作する CPU」

CPU は一定間隔のリズムで CPU 内部の各パーツを動かして処理をしている。

リズムが早いほど、高速に処理ができる。

そのリズム(クロック)が 1 GHz であるということ。

 

つまり、1 秒間に 1 G(ギガ)クロック分の処理ができる CPU となる。

G(ギガ)は 10⁹ なので、1 G クロック = 1 × 10⁹ クロック = 1,000,000,000 クロックである。 

 

 

機械語の 1 命令を平均 0.8 クロックで実行できる」

0.8 クロックあれば平均して 1 命令を処理できるということ。

この CPU は 1 秒間に 1,000,000,000 クロックなので、1 秒間に処理できる命令は

1,000,000,000 [クロック] ÷ 0.8 [クロック/命令] =1,250,000,000 命令となる。

 

 

「この CPU は 1 秒間に平均何万命令を実行できるか」

1 秒間に 1,250,000,000 命令を実行できるが、問題が聞いているのは何万命令かなので、

1,250,000,000 命令 = 125,000 × 10,000 命令 = 125,000 万命令 であり、正解は選択肢エとなる

 

 

CPU の問題ついでに CPU の演算性能について少し書いてみる。

Intel Xeon Gold 6152 という CPU を例にしてみる。

Intel Xeon Gold 6152 Processor 30.25M Cache 2.10 GHz 製品仕様

周波数 2.10 GHz で、コア数が 22 となっている。

 

昔の CPU は 1 コアしかないものもあったが、今の CPU はほぼマルチコアプロセッサとなっている。

コア毎に異なる処理を割り当てて、複数の命令を並列に処理することができる。

人によっては 「CPU の数は?」 と言いながら、意図としては 「コアの数は?」 を聞いているケースもあるので注意が必要である。

 

Intel Xeon Gold 6152 は周波数 2.10 GHz で動くコアが 22 個搭載されている。

各コアは浮動小数点演算ができるユニットを 32 個搭載している(この個数は CPU のアーキテクチャで決まってくるもの)。

※「32個搭載」と書くと厳密には異なるけども、概念の説明ということでご勘弁を。。。

 

これら数値の掛け算が FLOPS(Floating-point Operations Per Second)という性能指標になる。

2.10 GHz × 22 コア × 32 ユニット = 1,478.4 GFLOPS

 

FLOPS は 1 秒あたり(Per Second)に何回の浮動小数点演算(Floating-point Operations)ができるか、という指標である。

 

22 コアが各々 32 個の浮動小数点演算ユニットをもつので、CPU としては 22 × 32 = 704 個の浮動小数点演算ユニットをもつことになる。

704 個の各ユニットが 2.10 GHz(=1 秒間に 2.10 G回)のリズムで動作ができるので、

1 秒間に 704 × 2.10G = 1,478.4 G 回の浮動小数点演算ができる CPU である、ということになる。

 

ただし、この CPU には AVX という機能があり、その機能を利用した場合は周波数が 1.40GHz となるため、 性能は 985.6 GFLOPS となる。

GFLOPS の数値は低く見えるが AVX の機能で効率よく計算ができるので、計算にかかる時間は短くなる(可能性もある)。

 

 

FLOPS の性能指標は上のとおり全ての浮動小数点演算ユニットが常に動いた場合の数値となっているが、実際に使われるようなソフトウェアで、そんな状況はまず起こらない。

ディスクやメモリの I/O 待ち、複数コアを使うために処理を割り振るオーバーヘッド等で仕事をしていないユニットは必ず発生する。

また、コア数を多くすれば CPU としての FLOPS はよくなるが、業務で使うソフトウェアが複数コアを使う並列化に向いていないものであると全く意味がない。

 

CPU の FLOPS 値は理論上の参考値とはなるが、業務で実際に使うソフトウェアの特性も考慮にいれて最適な CPU を選ぶ必要がある。

とはいっても精度の高い推測は難易度が高いので、いくつかの CPU で実際にソフトウェアを動かしてみるベンチマークがよく行われる。

 

 

前後の問題はこちら。

koki2016.hatenadiary.com

 

基本情報技術者試験 令和元年度 秋季 午前 問11

再帰的に定義される関数の問題。ついでに自然数で少し脱線。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問11

 

自然数 n に対して、次の通り再帰的に定義される関数  f(n) を考える。  f(5) の値はどれか。

 

 f(n) :  if  n ≦ 1  then  return  1  else  return   n + f(n-1)

 

ア 6

イ 9

ウ 15

エ 25

--------------------------

解説

 

再帰的に定義される関数については以下で書いてみている。

koki2016.hatenadiary.com

 

再帰(さいき)とは、ある記述をする際に、その記述の中に自身への参照が含まれていること。

 

 f(n) :  if  n ≦ 1  then  return  1  else  return   n + f(n-1)

 

一行で書くとわかりにくいので、少し工夫して、プログラムみたく改行とインデントを加えてみる。

 

 f(n) :

if  n ≦ 1

then

    return  1

else

    return   n + f(n-1)

 

n が 1 以下のときは 1 を返し、そうでないときは  n + f(n-1) を返すということ。

 

 

問題としては  f(5) を聞いているので、 f(n) の定義に従うと以下のようになる。

 

 f(5)

=  5 + f(5-1)

=  5 + f(4)  

=  5 + 4 + f(4-1)

=  5 + 4 + f(3)

=  5 + 4 + 3 + f(3-1)

=  5 + 4 + 3 + f(2)

=  5 + 4 + 3 + 2 + f(2-1)

=  5 + 4 + 3 + 2 + f(1)  

=  5 + 4 + 3 + 2 + 1  f(1) は n ≦ 1 のときなので 1 になる

=  15

 

となるので、正解は選択肢ウの 15

 

 

計算の途中を見ての通り、この関数は n 以下の正の整数の和を求めている。

等価な数式にするとこんな感じ。

 f(n) = \sum_{k=1}^n k

 

 

ちなみに問題では自然数 n と書いているが、自然数には 0 を含まない流儀と含む流儀がある。

 

  • 0 を含まない流儀の場合は、ここまでの話に問題はない。
  • 0 を含む流儀の場合は、ちょっと問題が起きてくる。

 

問題の  f(n) では n ≦ 1 で return 1 なので、 f(0) = 1 になる。

一方で、

 f(n) = \sum_{k=1}^n k

では  f(0) = 1 とはならないので、等価な数式ではなくなってしまう。

 

勝手に等価な数式は~とか言い出して、勝手に問題が~とか言っているだけなのでどうでもいいことではあるけれど。

関数は定義域もちゃんと意識しましょう、という話でした。

 

 

 

前後の問題はこちら。

koki2016.hatenadiary.com

 

基本情報技術者試験 令和元年度 秋季 午前 問10

ハッシュ法についての問題。ついでに衝突時の話も。

 

--------------------------

基本情報技術者試験

令和元年度 秋期 午前 問10

 

10 進法で 5 桁の数  a_1 a_2 a_3 a_4 a_5 を、ハッシュ法を用いて配列に格納したい。ハッシュ関数 mod ( a_1 + a_2 + a_3 + a_4 + a_5 , 13 ) とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321 は配列のどの位置に入るか。

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

f:id:koki2016:20210918134255p:plain

--------------------------

解説

 

5 + 4 + 3 + 2 + 1 = 15

mod(15 , 13) = 2

なので正解は選択肢イの 2

 

としか書くことがない。。。

 

ハッシュ法については以下の問題で少し書いてみてはいる。

koki2016.hatenadiary.com

 

 

折角なので、ハッシュ値が衝突した場合のことを書いてみる。

ハッシュ値が衝突することはコリジョン(collision)とも呼ばれる。英単語そのまま。

ハッシュ値が衝突するデータの集まりをシノニム(synonym)と呼ぶ。

 

この問題のように格納先が 13 種類(0 ~ 12)しかないと、かなり頻繁に衝突が起きる。

 

衝突が起きた場合にどうするか。

 

オープンアドレス法

衝突が起きたら、何らかの手順で次の空いている格納先を探す。

  1. 54321 が問題のとおり配列 2 に格納されている。
  2. 54388 は mod(28 , 13) = 2 となるが、配列 2 にはもう 54321 がいる。
  3. なので、一つ後ろの配列 3 に 54388 を格納する(線形走査法)

線形走査法埋は単純でわかりやすいが、連続して配列が埋まってしまうことで衝突が起こりやすくなってしまうデメリットがある。

 

ちょっとだけ改良したのが二重ハッシュ法

  1. 54321 が問題のとおり配列 2 に格納されている。
  2. 54388 は mod(28 , 13) = 2 となるが、配列 2 にはもう 54321 がいる。
  3. 54388 に mod(28 , 13) とは別のハッシュ関数を当てはめて格納配列を決める。

 

 

そもそもの考え方を変えてみる。

直接連鎖法(ハッシュチェイン法)

格納先を一つの箱ではなく、連結リストとする。

  1. 54321 が問題のとおり配列 2(の 1 番目)に格納されている。
  2. 54388 は mod(28 , 13) = 2 となるので、配列 2(の 2 番目)に格納される。

連結リストが長くなってしまうと検索のときに結局時間がかかってしまう。

 

どちらにせよ、ハッシュ値が衝突しないような工夫が大事になる。

 

 

前後の問題はこちら。

koki2016.hatenadiary.com