アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2012年6月21日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html
1
比較に頼らない方法
ハッシュ法
データに関する情報を比較によらないで取得
データの性質が明らかであればO(1)に近づく
ことができる
ハッシュ関数が命
ハッシュ関数を設計するときに、データに関す
る情報を取得し盛り込む
（連想記憶機構があれば…）
2
ハッシュテーブル
(123ページ以降で詳しく)
並べたデータを「鍵」を用いてアクセス
「鍵」からハッシュテーブル内のデータを特
定するための関数 → ハッシュ関数
ハッシュ関数
合同法(除算法)
H(k) = k mod n (k: 鍵, n:素数)
平方抽出法
重ね合わせ法
3
ハッシュテーブル
データ
データ
キー１
データ
データ
キー２
データ
データ
キー３
データ
ハッシュ関数
データ
4
public class MyHashtable {
public MyHashtable(int aMaxSize) {
this.table = new MyData[aMaxSize];
}
public MyData get(String aKey) {
return this.table[this.calculateHashCode(aKey)];
}
public boolean put(MyData aMyData) {
this.table[this.calculateHashCode(aMyData.getName())] = aMyData;
return true;
}
public boolean remove(String aKey) {
this.table[this.calculateHashCode(aKey)] = null;
return true;
}
private int calculateHashCode(String aKey) {
int intkey = 0;
for(int count = 0; count < aKey.length(); count++){
intkey += 0xFFFF & aKey.charAt(count);
}
return intkey % this.table.length;
}
private MyData[] table;
}
この実装では、ハッシュ値が同じ(衝突した)場合に
データが上書きされて消えてしまうことがある。
5
衝突
• 異なった鍵を用いてもハッシュ値が同じ
– 先に格納されているデータ → ホーム
– 後から格納するデータ
→ シノニム
• 衝突を解決する方法
– 分離連鎖法
– 空き番地法
6
分離連鎖法(チェイン法)
ハッシュ
テーブル
連結リスト
図2.7.1 教科書125ページ
7
public class MyData {
public MyData(String x) {
name = x;
}
private final String name;
public String getName() {
return name;
}
public boolean equals(Object x) {
MyData y;
try {
y = (MyData) x;
} catch (ClassCastException e) {
return false;
}
return this.name.equals(y.getName());
}
public int hashCode() {
int intkey = 0;
for (byte e : name.getBytes()) {
intkey += e;
}
return intkey;
}
public String toString() {
return name;
}
}
ハッシュテーブルに保持したいデータの例
インスタンス固有のhashCode()を返すことと、
equals()メソッドを実装していること。
これらはObjectクラスに実装があるが、
オーバーライドして実装する。
そうすることで、設計者の意図したとおりに
動作を変えることができる。
このデータ構造は分離連鎖法と開番地法の
両方で使うことができる。
しかしながら、必ずしも使わなくてもいい。
8
public class ChainHashtable<T> {
public ChainHashtable(int max_size) {
総称型を使った実装の例
this.table = new List[max_size];
}
インスタンスを生成したときに
private List<T>[] table;
取り扱う要素データの型が決まる、
private int hashCode(T data) {
といった場合に設計の段階では
int hashcode = Math.abs(data.hashCode());
要素型を（この例では）Tとして仮定
return hashcode % this.table.length;
する。
}
public boolean put(T data) {
ただし、型が決まるのは実行時
int hashcode = hashCode(data);
なので、Tは実際の型ではないし、
if (this.table[hashcode] == null)
コンパイルの際にTは消される。
this.table[hashcode] = new LinkedList<T>();
this.table[hashcode].add(data);
要素型を代入・参照するときに、
return true;
矛盾なく同じ型として取り扱えると
}
いうことをコンパイル時に検査する。
public T get(T data) {
List<T> list = this.table[hashCode(data)];
if (null == list) return null;
for (T e : list) if (e.equals(data)) return e;
return null;
}
public boolean remove(T data) {
List<T> list = this.table[hashCode(data)];
if (null == list) return false;
return list.remove(data);
テスト用のデータやメソッドは次のページ。
}
9
}
テストデータを入れます。
public String toString() {
[0] -> 北海道
StringBuffer sb = new StringBuffer();
[1] -> 東京 -> 高知 -> 兵庫 -> 鹿児島 -> 沖縄
int index = 0;
[2] -> 青森
for (List<T> list : this.table) {
「高知」を削除します。
sb.append('[').append(index++).append("]");
[0] -> 北海道
if (list != null)
[1] -> 東京 -> 兵庫 -> 鹿児島 -> 沖縄
for (T e : list)
[2] -> 青森
sb.append(" -> ").append(e.toString());
テストデータを入れます。
sb.append('\n');
[0] -> 東京 -> 鹿児島
}
[1] -> 兵庫
return sb.toString();
[2] -> 北海道 -> 高知 -> 沖縄 -> 青森
}
「高知」を削除します。
private final static String[] test_data = {
[0] -> 東京 -> 鹿児島
"東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"};
[1] -> 兵庫
public static void main(String args[]) {
[2] -> 北海道 -> 沖縄 -> 青森
System.out.println("テストデータを入れます。");
ChainHashtable<String> hashtable1 = new ChainHashtable<String>(3);
for (String e : test_data) hashtable1.put(e);
System.out.print(hashtable1.toString());
System.out.println("「高知」を削除します。");
hashtable1.remove("高知");
System.out.print(hashtable1.toString());
}
System.out.println("テストデータを入れます。");
ChainHashtable<MyData> hashtable2 = new ChainHashtable<MyData>(3);
for (String e : test_data) hashtable2.put(new MyData(e));
System.out.print(hashtable2.toString());
System.out.println("「高知」を削除します。");
hashtable2.remove(new MyData("高知"));
System.out.print(hashtable2.toString());
10
開番地法
キー
既にデータが
格納されている
ハッシュ
再ハッシュ
ここも既にデータが
格納されている
再ハッシュの方法
•線形走査法
•二重ハッシュ法
•均一ハッシュ法
再ハッシュ
この場所は空なので
ここに格納する
図2.7.4 教科書131ページ
および教科書134ページ
11
空き番地法を用いた場合の削除
キー
同じハッシュ値だけ
ど、これじゃない。
ハッシュ
再ハッシュ
削除フラグを格納
削除したい
削除
データは消えてるけ
ど、これでもない。
削除フラグ
再ハッシュ
このデータを
探索したい
これだっ！
教科書134ページ
12
public class OpenHashtable<T extends Object> {
public OpenHashtable(int max_size) {
this.table = new Object[max_size];
}
private Object[] table;
private final static Object removed_data = new Object();
public boolean put(T data) {
int hashcode = hashCode(data);
for (int count = 0; count < this.table.length; count++) {
if ((null == this.table[hashcode]) || (removed_data == this.table[hashcode])) {
this.table[hashcode] = data;
return true;
1回目のハッシュで衝突が起きたときは
}
衝突が起きなくなるまで別のハッシュ関
hashcode = hashCode(data, hashcode);
数でハッシュしなおす。
}
return false;
}
public T get(T data) {
int hashcode = hashCode(data);
for (int count = 0; count < this.table.length; count++) {
if (null == this.table[hashcode]) return null;
if (removed_data != this.table[hashcode])
if (this.table[hashcode].equals(data)) return (T) this.table[hashcode];
hashcode = hashCode(data, hashcode);
}
return null;
}
13
remove,
hashCode
メソッドなどは次ページに…
}
public boolean remove(T data) {
int hashcode = hashCode(data);
for (int count = 0; count < this.table.length; count++) {
if (null == this.table[hashcode]) {
return false;
}
if (removed_data != this.table[hashcode]) {
if (this.table[hashcode].equals(data)) {
this.table[hashcode] = removed_data;
return true;
}
}
hashcode = hashCode(data, hashcode);
}
return false;
}
1回目のハッシュは剰余演算
2回目以降は一定間隔離す
距離は前の値から1～3
1固定の場合は線形走査法と同じ
固定値にしないときは二重ハッシュ法
private int hashCode(T data) {
int hashcode = Math.abs(data.hashCode());
return hashcode % this.table.length;
}
private int hashCode(T data, int hashcode) {
int intkey = hashCode(data);
return ((hashcode + 3 - (intkey % 3)) % this.table.length);
}
14
テストデータを入れます。
0: 高知(0)
1:
2: 東京(2)
3: 鹿児島(3)
4:
5:
6: 沖縄(6)
7: 北海道(7)
8: 兵庫(8)
9: 青森(8)
10:
「高知」を削除します。
0: [removed]
1:
2: 東京(2)
3: 鹿児島(3)
4:
5:
6: 沖縄(6)
7: 北海道(7)
8: 兵庫(8)
9: 青森(8)
10:
← Stringを要素型に使った例
MyDataを要素型に使った例 →
hashCode()の仕様を変えることで
動作を変えることができる。
テストデータは１０ページと同じ。
テスト方法はクラス名を差し替えただけで同じ。
ということで、テスト用コードは割愛します。
テストデータを入れます。
0:
1: 鹿児島(1)
2: 東京(2)
3: 高知(3)
4:
5: 北海道(5)
6: 兵庫(5)
7: 青森(7)
8: 沖縄(8)
9:
10:
「高知」を削除します。
0:
1: 鹿児島(1)
2: 東京(2)
3: [removed]
4:
5: 北海道(5)
6: 兵庫(5)
7: 青森(7)
8: 沖縄(8)
9:
10:
15
既にデータが
格納されている
キー
配列サイズ１０
ステップ幅５
ハッシュ
再ハッシュ
+5 mod 10
ここも既にデータが
格納されている
再ハッシュ
よくない二重ハッシュ法
16
空きがあった!
既にデータが
格納されている
キー
ハッシュ
再ハッシュ
配列サイズ１１
ステップ幅５
ここも既にデータが
格納されている
再ハッ
+5 mod 11
シュ
二重ハッシュ法
17
アルゴリズムとデータ構造演習
学生番号：
名前：
テストデータを入れます。
0: 高知(0)
1:
2: 東京(2)
3: 鹿児島(3)
4:
5:
6: 沖縄(6)
7: 北海道(7)
8: 兵庫(8)
9: 青森(8)
10:
← Stringを要素型に使った例
「兵庫」と「青森」が衝突している
MyDataを要素型に使った例 →
「北海道」と「兵庫」が衝突している
テストデータを入れます。
0:
1: 鹿児島(1)
2: 東京(2)
3: 高知(3)
4:
5: 北海道(5)
6: 兵庫(5)
7: 青森(7)
8: 沖縄(8)
9:
10:
カッコ（）の中の数字は一回目のハッシュ値で、
衝突した場合はハッシュ値を計算しなおしている。
要素型としてStringとMyDataを用いたそれぞれの例において、
衝突が起きたデータのうちホームとシノニムを答えよ。
シノニムについて、計算しなおしたハッシュ値を計算式とともに答えよ。

Download Report