期末試験
7/1 3限
3A202
持ち込み不可
クイズの類題から出題

データの探索

表探索
・線形探索
順序に制約がない
キーの探索
順番に調べる O(n)
キーの追加 表の最後に追加 O(1)
キーの削除
1. 削除して後ろのキーをシフト
2. 削除したキーをマーク
データが少ない
追加のほうが圧倒的に多い
新しいキーへの探索が多い

二分探索
よく出てくる

ハッシュ表
サイズ9の表を用意する。
アルファベット順、キーの頭の文字をmod9した番地にたたきこむ
SuzukiならSmod9=19mod9=1、1番地に入る
先住者がいる→衝突　なんとかして別の領域に入れる (2番地ずらすとか)

ごみが固まると効率が悪くなる
* 第1クラスタ (Primary Cluster)
同族でないキーがおる
* 第2種クラスタ

例: Uedaは1=21mod9=3番地に要るはず
3番地にはSatohがいる→5番地に301→5番地にはNakamuraがおる→7番地に301→Watanabeがおる→0番地に301→Abeがおる→2番地に301→Uedaがいた　探索5回。やばい。

開番地法 (Open Addressing)
衝突が起こると、代わりの番地を探す。ハッシュ関数を0とすると、h,,0,,(k)がkを格納する理論上の番地を表す。そこがだめなら代わりのh,,1,,(k)を示す。これをデータの格納が完了するまで繰り返す。
h,,0,,(k), h,,1,,(k), ...

探索周期
同じ番地が再び出てくるまでの回数

線形走査法
h,,i,,(k)をこうやって求める:
h,,i,,(k) = [h,,0,,(k) + d * i] mod M
where d = ハッシュ増分(定数)、M = 表のサイズ