酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2012年6月21日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html

比較に頼らない方法 ハッシュ法 データに関する情報を比較によらないで取得 データの性質が明らかであればO(1)に近づくことができる ハッシュ関数が命 ハッシュ関数を設計するときに、データに関する情報を取得し盛り込む （連想記憶機構があれば…）

ハッシュテーブル (123ページ以降で詳しく) 並べたデータを「鍵」を用いてアクセス 「鍵」からハッシュテーブル内のデータを特定するための関数　→　ハッシュ関数 ハッシュ関数 合同法(除算法) H(k) = k mod n (k: 鍵, n:素数) 平方抽出法 重ね合わせ法

ハッシュテーブル データ キー１ キー２ キー３ ハッシュ関数

この実装では、ハッシュ値が同じ(衝突した)場合に データが上書きされて消えてしまうことがある。 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; 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; この実装では、ハッシュ値が同じ(衝突した)場合に データが上書きされて消えてしまうことがある。

衝突 異なった鍵を用いてもハッシュ値が同じ 衝突を解決する方法 先に格納されているデータ → ホーム 後から格納するデータ → シノニム 先に格納されているデータ　→　ホーム 後から格納するデータ　　　　→　シノニム 衝突を解決する方法 分離連鎖法 空き番地法

分離連鎖法(チェイン法) 連結リスト ハッシュ テーブル 図2.7.1 教科書125ページ

インスタンス固有のhashCode()を返すことと、 equals()メソッドを実装していること。 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() { ハッシュテーブルに保持したいデータの例 インスタンス固有のhashCode()を返すことと、 equals()メソッドを実装していること。 これらはObjectクラスに実装があるが、 オーバーライドして実装する。 そうすることで、設計者の意図したとおりに 動作を変えることができる。 このデータ構造は分離連鎖法と開番地法の 両方で使うことができる。 しかしながら、必ずしも使わなくてもいい。

テスト用のデータやメソッドは次のページ。 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()); return hashcode % this.table.length; public boolean put(T data) { int hashcode = hashCode(data); if (this.table[hashcode] == null) 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) { if (null == list) return false; return list.remove(data); 総称型を使った実装の例 インスタンスを生成したときに 取り扱う要素データの型が決まる、 といった場合に設計の段階では 要素型を（この例では）Tとして仮定 する。 ただし、型が決まるのは実行時 なので、Tは実際の型ではないし、 コンパイルの際にTは消される。 要素型を代入・参照するときに、 矛盾なく同じ型として取り扱えると いうことをコンパイル時に検査する。 テスト用のデータやメソッドは次のページ。

テストデータを入れます。 [0] -> 北海道 [1] -> 東京 -> 高知 -> 兵庫 -> 鹿児島 -> 沖縄 [2] -> 青森 「高知」を削除します。 [1] -> 東京 -> 兵庫 -> 鹿児島 -> 沖縄 [0] -> 東京 -> 鹿児島 [1] -> 兵庫 [2] -> 北海道 -> 高知 -> 沖縄 -> 青森 [2] -> 北海道 -> 沖縄 -> 青森 public String toString() { StringBuffer sb = new StringBuffer(); int index = 0; for (List<T> list : this.table) { sb.append('[').append(index++).append("]"); if (list != null) for (T e : list) sb.append(" -> ").append(e.toString()); sb.append('\n'); } return sb.toString(); private final static String[] test_data = { "東京", "北海道", "高知", "兵庫", "鹿児島", "沖縄", "青森"}; public static void main(String args[]) { 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("高知"); ChainHashtable<MyData> hashtable2 = new ChainHashtable<MyData>(3); for (String e : test_data) hashtable2.put(new MyData(e)); System.out.print(hashtable2.toString()); hashtable2.remove(new MyData("高知"));

開番地法 キー 再ハッシュの方法 線形走査法 二重ハッシュ法 均一ハッシュ法 図2.7.4 教科書131ページ および教科書134ページ 既にデータが 格納されている ハッシュ キー 再ハッシュ 再ハッシュの方法 線形走査法 二重ハッシュ法 均一ハッシュ法 ここも既にデータが 格納されている 再ハッシュ この場所は空なので ここに格納する 図2.7.4　教科書131ページ および教科書134ページ

空き番地法を用いた場合の削除 キー 削除したい 削除 教科書134ページ ハッシュ 再ハッシュ 再ハッシュ 削除フラグを格納 同じハッシュ値だけど、これじゃない。 キー ハッシュ 再ハッシュ データは消えてるけど、これでもない。 削除したい 削除フラグ 削除フラグを格納 削除 再ハッシュ これだっ！ このデータを 探索したい 教科書134ページ

remove, hashCode メソッドなどは次ページに… 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; hashcode = hashCode(data, hashcode); return false; public T get(T data) { if (null == this.table[hashcode]) return null; if (removed_data != this.table[hashcode]) if (this.table[hashcode].equals(data)) return (T) this.table[hashcode]; return null; 1回目のハッシュで衝突が起きたときは衝突が起きなくなるまで別のハッシュ関数でハッシュしなおす。 remove, hashCode　メソッドなどは次ページに…

1回目のハッシュは剰余演算 2回目以降は一定間隔離す 距離は前の値から1～3 1固定の場合は線形走査法と同じ 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); 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); 1回目のハッシュは剰余演算 2回目以降は一定間隔離す 　距離は前の値から1～3 1固定の場合は線形走査法と同じ 固定値にしないときは二重ハッシュ法

hashCode()の仕様を変えることで 動作を変えることができる。 テストデータを入れます。 0: 高知(0) 1: 2: 東京(2) 3: 鹿児島(3) 4: 5: 6: 沖縄(6) 7: 北海道(7) 8: 兵庫(8) 9: 青森(8) 10: 「高知」を削除します。 0: [removed] テストデータを入れます。 0: 1: 鹿児島(1) 2: 東京(2) 3: 高知(3) 4: 5: 北海道(5) 6: 兵庫(5) 7: 青森(7) 8: 沖縄(8) 9: 10: 「高知」を削除します。 3: [removed] ←　Stringを要素型に使った例 MyDataを要素型に使った例　→ hashCode()の仕様を変えることで 動作を変えることができる。 テストデータは１０ページと同じ。 テスト方法はクラス名を差し替えただけで同じ。 ということで、テスト用コードは割愛します。

キー よくない二重ハッシュ法 配列サイズ１０ ステップ幅５ +5 mod 10 ハッシュ 再ハッシュ 再ハッシュ 既にデータが 格納されている ハッシュ キー 配列サイズ１０ ステップ幅５ +5 mod 10 再ハッシュ 再ハッシュ ここも既にデータが 格納されている よくない二重ハッシュ法

キー 二重ハッシュ法 配列サイズ１１ ステップ幅５ +5 mod 11 ハッシュ 再ハッシュ 再ハッシュ 空きがあった! 既にデータが 格納されている ハッシュ キー 再ハッシュ 再ハッシュ 配列サイズ１１ ステップ幅５ +5 mod 11 ここも既にデータが 格納されている 二重ハッシュ法

アルゴリズムとデータ構造 演習 学生番号： 名前： ← Stringを要素型に使った例 「兵庫」と「青森」が衝突している アルゴリズムとデータ構造　演習 学生番号：　　　　　　　　　　　　　　　　 　　　名前：　　　　　　　　　　　　　　　　 テストデータを入れます。 0: 1: 鹿児島(1) 2: 東京(2) 3: 高知(3) 4: 5: 北海道(5) 6: 兵庫(5) 7: 青森(7) 8: 沖縄(8) 9: 10: テストデータを入れます。 0: 高知(0) 1: 2: 東京(2) 3: 鹿児島(3) 4: 5: 6: 沖縄(6) 7: 北海道(7) 8: 兵庫(8) 9: 青森(8) 10: ←　Stringを要素型に使った例 　　　　　「兵庫」と「青森」が衝突している 　　　　　　MyDataを要素型に使った例　→ 「北海道」と「兵庫」が衝突している カッコ（）の中の数字は一回目のハッシュ値で、 衝突した場合はハッシュ値を計算しなおしている。 要素型としてStringとMyDataを用いたそれぞれの例において、 衝突が起きたデータのうちホームとシノニムを答えよ。 シノニムについて、計算しなおしたハッシュ値を計算式とともに答えよ。