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

Slides:



Advertisements
Similar presentations
独習JAVA Chapter 6 6.6 クラスの修飾子 6.7 変数の修飾子 結城 隆. 6.6 クラスの修飾 abstract インスタンス化できないクラス。1つまたは複数のサブクラスで 実装してはじめてインスタンス化できる。 final 継承されたくないことを明示する。これ以上機能拡張 / 変更でき.
Advertisements

アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造1 2007年6月12日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造 2012年7月23日
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
アルゴリズムとデータ構造 2011年6月13日
アルゴリズムとデータ構造 2011年7月14日
第20章 Flyweight ~同じものを共有して無駄をなくす~
アルゴリズムとデータ構造 2011年6月14日
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
~手続き指向からオブジェクト指向へ[Ⅱ]~
アルゴリズムとデータ構造 2011年7月4日
ハッシュ表 データ構造とプログラミング(12)
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとプログラミング (Algorithms and Programming)
第9章 例外処理,パッケージ 9.1 例外処理 9.2 ガーベッジコレクション.
オブジェクト指向 プログラミング 第八回 知能情報学部 新田直也.
独習JAVA 6.8 コンストラクタの修飾子 6.9 メソッドの修飾子 6.10 ObjectクラスとClassクラス 11月28日(金)
オブジェクト指向 プログラミング 第十一回 知能情報学部 新田直也.
オブジェクト指向 プログラミング 第十三回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
オブジェクト指向 プログラミング 第十四回 知能情報学部 新田直也.
オブジェクト指向 プログラミング 第七回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
アルゴリズムとデータ構造 2012年7月17日
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
オブジェクト指向 プログラミング 第十ニ回 知能情報学部 新田直也.
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
pointcut に関して高い記述力を持つ アスペクト指向言語 Josh
実装編②HashTable,JavaAPI
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
アルゴリズムとプログラミング (Algorithms and Programming)
オブジェクト指向 プログラミング 第八回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 2012年6月25日
JAVA入門⑥ クラスとインスタンス.
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

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

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

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

ハッシュテーブル データ キー1 キー2 キー3 ハッシュ関数

この実装では、ハッシュ値が同じ場合に データが上書きされて消えてしまうことがある。 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()の仕様を変えることで 動作を変えることができる。 テストデータは10ページと同じ。 テスト方法はクラス名を差し替えただけで同じ。 ということで、テスト用コードは割愛します。

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

キー 二重ハッシュ法 配列サイズ11 ステップ幅5 +5 mod 11 ハッシュ 再ハッシュ 再ハッシュ 空きがあった! 既にデータが 格納されている ハッシュ キー 再ハッシュ 再ハッシュ 配列サイズ11 ステップ幅5 +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を用いたそれぞれの例において、 衝突が起きたデータのうちホームとシノニムを答えよ。 シノニムについて、計算しなおしたハッシュ値を計算式とともに答えよ。