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

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造 2011年7月7日
Advertisements

アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造1 2008年7月22日
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
プログラミング基礎I(再) 山元進.
データ構造とプログラミング技法 (第8回) ーデータの探索ー.
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 2012年7月12日
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
~手続き指向からオブジェクト指向へ[Ⅱ]~
ハッシュテーブル.
アルゴリズムとデータ構造 2011年7月4日
ハッシュ表 データ構造とプログラミング(12)
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年6月17日
独習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日
コンパイラ 2012年11月15日
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
アルゴリズムとデータ構造 2011年7月12日
アルゴリズムとデータ構造 2012年7月17日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
実装編②HashTable,JavaAPI
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
コンパイラ 2012年10月29日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造 2011年7月11日
暗号技術 ~JAVAプログラム②~ (6週目)
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
第11回放送授業.
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 補足資料11-3 「線形リストのオペレータ」
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2013年6月20日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
新人研修発表 平成13年5月14日(月) 探索アルゴリズム ハッシュ法について 株式会社 エーアイネット・テクノロジ          須田 哲生.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

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

期末試験 教室: K101 日時: 2009年7月30日13時10分~14時50分 持ち込み可 学生証必携 入室限度: 13時30分まで 退出可能: 13時40分より 持ち込み可 教科書・資料(自筆・コピー問わず)は持ち込み可 人間・パソコン・携帯電話・PHSなど持ち込み不可 学生証必携 持っていない場合は教務で発行してもらうこと

計算量の考察 キー値の比較を1回行うと候補は半減する ちょうど半分ずつ絞りこめばO(log N) 候補が半減する場合がもっとも効率が良い 半減するようにデータを保持する 例:平衡木を使う ちょうど半分ずつ絞りこめばO(log N) キーの比較という手法を使う限りはこれ以上探索の効率はよくならない。

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

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

ハッシュテーブルのイメージ データ

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

public class MyHashtable { private MyHashtable() } public MyHashtable(int aMaxSize) this.table = new AddressData[aMaxSize]; public AddressData get(String aKey) if(null == aKey){ throw new NullPointerException(); return this.table[this.calculateHashCode(aKey)]; public void printAll() for(int count = 0; count < this.table.length; count++){ System.out.println(count+1 + "\t" + this.table[count]); System.out.println(); private AddressData[] table;

public boolean put(AddressData anAddressData) { if(null == anAddressData){ return false; } this.table[this.calculateHashCode(anAddressData.getName())] = anAddressData; return true; public boolean remove(String aKey) if(null == aKey){ this.table[this.calculateHashCode(aKey)] = null; private int calculateHashCode(String aKey) throw new NullPointerException(); int intkey = 0; for(int count = 0; count < aKey.length(); count++){ intkey += 0xFFFF & aKey.charAt(count); return intkey % this.table.length; [sakai@star]$ java MyHashtableTest 住所データを格納 1 null 2 null 3 null 4 杉山: 稲城,東京 208 5 null 6 null 7 ONGS Inc.: 渋谷,東京 151 8 後藤: 川崎,神奈川 214 9 null 10 null 11 佐々木: 座間,神奈川 228 12 小澤: 多摩,東京 206 13 null 14 null 15 null 16 null 17 null 18 null 19 null

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

住所録として以下の項目を持つ 名前 市 都道府県 郵便番号 public class AddressData { public AddressData(String aName, String aMetropolice, String aCity, String aZipcode) if((null == aName) || (null == aMetropolice) || (null == aCity)|| (null == aZipcode)){ throw new NullPointerException(); } this.name = aName; this.metropolice = aMetropolice; this.city = aCity; this.zipcode = aZipcode; public String getName() return this.name; public String getAddress() return this.city + "," + this.metropolice + " " + this.zipcode; public String toString() return this.name + ": " + this.city + "," + this.metropolice + “ " + this.zipcode; private String city; private String metropolice; private String name; private String zipcode; 住所録として以下の項目を持つ 名前 市 都道府県 郵便番号

public class ChainHashtable { private ChainHashtable() } public ChainHashtable(int aMaxSize) this.table = new MyLinkedList[aMaxSize]; private MyLinkedList[] table; public boolean put(AddressData anAddressData) { if(null == anAddressData){ return false; } int hashCode = this.calculateHashCode(anAddressData.getName()); if(null == this.table[hashCode]){ this.table[hashCode] = new MyLinkedList(); this.table[hashCode].insert(anAddressData); return true;

public AddressData get(String aKey) { if(null == aKey){ throw new NullPointerException(); } MyLinkedList list = this.table[this.calculateHashCode(aKey)]; if(null == list){ return null; int limit = list.size(); int count = 1; AddressData address = null; while(count <= limit){ address = (AddressData)list.get(count); if(address.getName().equals(aKey)){ return address; ++count; private int calculateHashCode(String aKey) { if(null == aKey){ throw new NullPointerException(); } int intkey = 0; for(int count = 0; count < aKey.length(); count++){ intkey += 0xFFFF & aKey.charAt(count); return intkey % this.table.length;

public boolean remove(String aKey) { if(null == aKey){ return false; } MyLinkedList list = this.table[this.calculateHashCode(aKey)]; if(null == list){ int limit = list.size(); int count = 1; AddressData address = null; while(count <= limit){ address = (AddressData)list.get(count); if(address.getName().equals(aKey)){ return list.remove(count); ++count; public void printAll() { for(int count = 0; count < this.table.length; count++){ if(null == this.table[count]){ System.out.println(this.table[count]); }else{ this.table[count].printAll(); } System.out.println();

ハッシュ表の大きさが3なので衝突が起きたときはリスト保持 [sakai@star]$ java ChainHashtableTest 住所データを格納 杉山: 稲城,東京 208 佐々木: 座間,神奈川 228 → 小澤: 多摩,東京 206 ONGS Inc.: 渋谷,東京 151 → 後藤: 川崎,神奈川 214 データの取得: 後藤 後藤: 川崎,神奈川 214 データの削除: ONGS Inc. [sakai@star]$ ハッシュ表の大きさが3なので衝突が起きたときはリスト保持

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

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

1回目のハッシュは剰余演算 2回目以降は一定間隔離す 距離は前の値から1~3 1固定の場合は線形走査法と同じ public class OpenAddressHashtable { public OpenAddressHashtable(int aMaxSize) this.table = new AddressData[aMaxSize]; } private final AddressData removedData = new AddressData("", "", "", ""); private AddressData[] table; private int calculateHashCode(String aKey) { if(null == aKey){throw new NullPointerException();} int intkey = 0; for(int count = 0; count < aKey.length(); count++){ intkey += 0xFFFF & aKey.charAt(count); } return intkey % this.table.length; 1回目のハッシュは剰余演算 2回目以降は一定間隔離す  距離は前の値から1~3 1固定の場合は線形走査法と同じ 固定値にしないときは二重ハッシュ法 private int calculateHashCodeAgain(String aKey, int aHashCode) { if(null == aKey){throw new NullPointerException();} int intkey = 0; for(int count = 0; count < aKey.length(); count++){ intkey += 0xFFFF & aKey.charAt(count); } int rehashCode = (aHashCode + 3 - (intkey % 3)) % this.table.length; System.err.println("再ハッシュ: " + aKey + " " + aHashCode + “ → " + rehashCode); return rehashCode;

1回目のハッシュで衝突が起きたときは衝突が起きなくなるまで別のハッシュ関数でハッシュしなおす。 public boolean put(AddressData anAddressData) { if(null == anAddressData){ return false; } int hashCode = this.calculateHashCode(anAddressData.getName()); if((null == this.table[hashCode]) || (this.removedData == this.table[hashCode])){ this.table[hashCode] = anAddressData; return true; int limit = this.table.length -1; String key = anAddressData.getName(); for(int count = 0; count < limit; count++){ hashCode = this.calculateHashCodeAgain(key, hashCode); 1回目のハッシュで衝突が起きたときは衝突が起きなくなるまで別のハッシュ関数でハッシュしなおす。

public AddressData get(String aKey) { if(null == aKey){ throw new NullPointerException(); } int hashCode = this.calculateHashCode(aKey); if(null == this.table[hashCode]){ return null; if(this.removedData != this.table[hashCode]){ if(this.table[hashCode].getName().equals(aKey)){ return this.table[hashCode]; int limit = this.table.length -1; for(int count = 0; count < limit; count++){ hashCode = this.calculateHashCodeAgain(aKey, hashCode);

public boolean remove(String aKey) { if(null == aKey){ throw new NullPointerException();} int hashCode = this.calculateHashCode(aKey); if(null == this.table[hashCode]){ return false; } if(this.removedData != this.table[hashCode]){ if(this.table[hashCode].getName().equals(aKey)){ this.table[hashCode] = removedData; return true; int limit = this.table.length -1; for(int count = 0; count < limit; count++){ hashCode = this.calculateHashCodeAgain(aKey, hashCode);

ハッシュ表の大きさが5なので衝突が起きている [sakai@star]$ java OpenAddressHashtableTest null 住所データを格納 再ハッシュ: 後藤 1 → 2 再ハッシュ: 後藤 2 → 3 再ハッシュ: ONGS Inc. 1 → 2 再ハッシュ: ONGS Inc. 2 → 3 再ハッシュ: ONGS Inc. 3 → 4 佐々木: 座間,神奈川 228 杉山: 稲城,東京 208 小澤: 多摩,東京 206 後藤: 川崎,神奈川 214 ONGS Inc.: 渋谷,東京 151 データの削除: 杉山 データの削除: 小澤 データの削除: 後藤 再ハッシュ: 後藤 1 → 2 再ハッシュ: 後藤 2 → 3 データの削除: 佐々木 削除されました ONGS Inc.: 渋谷,東京 151 データの取得: ONGS Inc. 再ハッシュ: ONGS Inc. 1 → 2 再ハッシュ: ONGS Inc. 2 → 3 再ハッシュ: ONGS Inc. 3 → 4 ハッシュ表の大きさが5なので衝突が起きている

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

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