１．辞書クラス
辞書クラスの様々な実現法を通し、アルゴリズムの応用のされかたを見てゆこう。
住所録 【番号】がキー項目
| 項目名 |
【番号】 | 【氏名】 | 【住所】 |
| レコード |
001 | 青森健太 | 青森県青森市… |
| 020 | 宮城遼 | 宮城県仙台市… |
| 017 | 長野愛子 | 長野県長野市… |
| … | … | … |
クラス：型（タイプ）
メソッドとプロパティを持つ
オブジェクト：その型のデータ
プロパティの値を定めたもの
レコードクラス
プロパティ：キー(値はレコード毎に一意で重複しない)、項目リスト
メソッド：get(項目名)、set(項目名)
辞書クラス
プロパティ：キー項目を持つレコードの集合
メソッド：探索(キー）、追加（レコード）、削除（キー）
辞書の基本メソッド（レコードの探索・追加・削除）を効率よく行うために、様々な編成法が考案されている。次表は、これから学ぶ基本的な編成法の計算時間(ステップ数)である。これを見ると直接編成が一番効率が良いが、後で見るように、特別な条件のもとでしか成立しない。
（ ）内はレコード数$N=1,000,000$の時の平均ステップ数
| 編成法 | 探索 | 追加 | 削除 | 備考 |
| 順編成 | $N/2$
(500,000) | $N/2+$1
(500,001) | $N/2+$1
(500,001) | 1は定数ステップの意味
500,001の1にあまり意味はない |
整列
順編成 | $\log_2N$
(20) | $\log_2N+N/2$
(500,020) | $\log_2N+N/2$
(500,020) | |
| 直接編成 | 1 | 1 | 1 |
衝突が生じない場合 |
索引
順編成 | 1$＋N/M/2$
(501) | 1$＋N/M/2$
(501) | 1$＋N/M/2$
(501) |
ブロック数$M=1,000$とした。 |
| 2分探索木 | $\log_2N$
(20) | $\log_2N+$1
(20+1) | $\log_2N+$1
(20+1) |
2分探索と1ステップの追加削除
が可能なデータ構造 |
２．順編成
レコードを単に1列にならべて管理
順探索：頭から順に探す
追加：
無ければ列の最後に追加
削除：
あれば削除し、最終レコードをそこに移す
注．デモで、操作のステップ数は赤字の個数に等しい
| パズル．レコード数$N$の順編成辞書について |
|
探索、追加、削除にかかる(平均あるいは最悪の)ステップ数を示し、理由を説明せよ。
|
３．整列順編成
レコードをキーで整列して管理
2分探索：探索範囲の中央値(赤)と比べて、
「小さければ前半を、大きければ後半を探索範囲(青)とする」を繰り返す
追加：
無ければ挿入する(大きなレコードを後にずらす)
削除：
あれば削除し、後のレコードを順に詰める
注．デモで、操作のステップ数は赤字の個数に等しい
| パズル．レコード数$N$の整列順編成辞書について |
|
探索、追加、削除にかかる(平均あるいは最悪の)ステップ数を示し、理由を説明せよ。
|
４．直接編成
キー値からレコード(の格納)番地を直接計算する
ハッシュ関数を利用
キーの値 ⇒【ハッシュ関数】⇒ レコードの格納位置
ハッシュ関数があれば、
探索、追加、削除は、１(定数)ステップ
例．学生レコードの辞書
2016年入学生(300名以下)の学籍番号が2016001～2016300ならば、ハッシュ関数を$h(k)=k-2016000$とし、レコードを1～300の番地(位置)に置く。
$番地=h(学籍番号)=学籍番号-2016000$
番地 |
学籍番号 | 氏名 | 住所 |
| 1 |
2016001 | 青森健太 | 青森県青森市… |
| 2 |
2016002 | 宮城遼 | 宮城県仙台市… |
| 3 |
| | |
| 4 |
2016004 | 長野愛子 | 長野県長野市… |
| … |
… | … | … |
適当なハッシュ関数があるとは限らない
通常、キー値の候補数はレコード(格納番地)数に比べ莫大
例．$10$文字の英数字($26+10=36$通り)からなるユーザIDをキーとする
キーの候補数は$36^{10}\simeq 3656兆$で、ユーザ数が3656人ならその1兆倍
通常、ハッシュ関数は、異なるキー(の候補値)に対し、同じ値を割り当てる
⇒存在するレコード(のキー値)にハッシュ関数が同じ値を割り当てる（
衝突）
⇒直接編成法は使えない⇒解決策(の1つ)が、索引順編成
| コラム．ハッシュという言葉の意味 |
| ハッシュ(hash)は、本来(肉を)切り刻むという意味で、ハヤシライスのハヤシ(hashed beef)の語源でもある。ハッシュ関数は、衝突をさけるため、単純な関数ではなく、もとのキー値を分解した(切り刻んだ)各部分が関数値に影響するように作る必要があることから付けられた名前である。
|
５．索引順編成
直接編成での
衝突の解決策
レコードの格納領域は、ハッシュ値ごとのブロックに分けられ(索引部)、ブロック内でレコードは順編成
ブロックの探索：直接探索
ブロック内の探索、追加、削除：順編成の探索、追加、削除
右上のデモでは簡単のため、5で割った余りをハッシュ値にしている。
| パズル．レコード数$N$、ブロック数$M$ の索引順編成辞書について |
|
探索、追加、削除にかかる(平均あるいは最悪の)ステップ数を示し、理由を説明せよ。
|
６．２分探索木
2分探索と、探索後に定数ステップでの
追加・削除が可能なデータ構造
各節点は左子と右子を持ち
左子の値＜節点の値＜右子の値
探索：木の根(最上節点)から始めて
節点の値より小⇒左部分木を探す
節点の値より大⇒右部分木を探す
を繰り返す
追加：探索で場所を見つけそこに追加
削除：削除節点$n$を探索。$n$に
左子がない⇒右子を$n$の位置に移動
左子がある⇒
左部分木中の最大値を$n$に代入し
その最大値節点を削除(左子を移動)
| パズル．レコード数$N$ の２文探索木について |
|
探索、追加、削除にかかる平均のステップ数を示し、理由を説明せよ。
|
２分探索木は、
平均的には効率が良いが
レコードの挿入・削除の順番によっては木のバランスが崩れ
最悪の場合、探索・追加・削除にオーダー $N$ の時間がかかるため
木の平衡を保ち、常にオーダー $\log N$ にするための
様々な工夫がなされている。
最後のページ
最後のページ