情報構造

---

◆　キュー 　キューとは、リストの中に先に入ったデータが最初に取り出される構造 First In First Out （ FIFO ）の事を言います。 　イメージ的には右の図の様な感じです。 　主に共有プリンタの印刷タスクや、CPUの処理待ちタスクなどで使用されています。 ◆　スタック 　スタックとはデータ構造の１つで、リストの中に最後に入ったものが最初に取り出せない構造 Last In First Out （ LIFO ）の事を言います。 　イメージ的には左の図の様な感じです。 　エディタや絵画ツールなどの、「やり直し」とかの処理で使用されています。 ◆　ハッシュ法 　ハッシュ法とは、検索したいキー値を元にハッシュ関数というものを用いて、 配列の何番目に格納されているかという情報を取得する、または配列の何番目に格納されるようになる方法です。 　・・・と言ってもちょっと分からないので、以下のような感じだと思います。 個人名「ABCD」さんのデータを格納したい。 ↓ ハッシュ関数に「ABCD」というのをキー値として渡す ↓ 配列のｘ番目に格納されている（もしくは格納しなさい） 　では、ハッシュ関数って何かと言いますと、キー値をもらってある計算式からｘ番目の ｘ を算出しますが、その ｘ がなるべく重複した値にならないようにするのが好ましい。 要は、その計算式やらは自分で考えろという事です。（とくに計算式に決まりがないのです）ここで言う ｘ がハッシュ値と言われています。 　例として下は「ABCD」からハッシュ関数を使用して取得したハッシュ値が 3 だった場合。 配列 0 1 AAAA 2 BBCCDD 3 ← ハッシュ値が3と出たのでここに「ABCD」を格納 4 5 ： ： 　だいたい過去問題では、このハッシュ関数は 　キー値 mod 配列の大きさ 　で出てきます。（おそらく配列に数値を格納するというのが前提なのでしょう。） 　よく問題になるのがハッシュ値の衝突と言って、キー値が異なっていてもハッシュ値は余りの値なので、重複してしまう可能性はあります。 上の場合だと、キー値が「a」と「b」（整数とします）とあった場合、a - b が配列の大きさの倍数であればハッシュ値が衝突してしまいます。 衝突してしまった時の対処は実は自由なのですが、 例としてはハッシュ値＋α番目の位置が空いているかどうかを調べ、空いていればそこに格納、空いてなければまた＋α番目を調べる手法があります。 　下はαを 3 とした場合の例です。 配列 0 1 AAAA ← ハッシュ値が1と出たがすでに格納されている（いわゆる衝突）。 ので＋3の位置に格納しよう。 2 BBCCDD 3 ABCD 4 ← ここは空いているので、ここに格納 5 ： ：

TOPページに戻る