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

アルゴリズムとデータ構造1
2007年7月6日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2007/index.html
計算量の考察
• キー値の比較を1回行うと候補は半減する
– 候補が半減する場合がもっとも効率が良い
– 半減するようにデータを保持する
• 例：平衡木を使う
• ちょうど半分ずつ絞りこめば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;
[sakai@star]$ java MyHashtableTest
}
住所データを格納
public boolean remove(String aKey)
1
null
{
2
null
if(null == aKey){
3
null
return false;
4
杉山: 稲城,東京 208
}
5
null
this.table[this.calculateHashCode(aKey)] = null;
6
null
return true;
7
ONGS Inc.: 渋谷,東京 151
}
8
後藤: 川崎,神奈川 214
private int calculateHashCode(String aKey)
9
null
{
10
null
if(null == aKey){
11
佐々木: 座間,神奈川 228
throw new NullPointerException();
12
小澤: 多摩,東京 206
}
13
null
int intkey = 0;
null
for(int count = 0; count < aKey.length(); count++){ 14
15
null
intkey += 0xFFFF & aKey.charAt(count);
16
null
}
17
null
return intkey % this.table.length;
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;
}
private int calculateHashCode(String aKey)
++count;
{
}
if(null == aKey){
return null;
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){
return false;
}
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);
}
public void printAll()
++count;
{
}
for(int count = 0; count < this.table.length; count++){
return false;
if(null == this.table[count]){
}
System.out.println(this.table[count]);
}else{
this.table[count].printAll();
}
}
System.out.println();
}
[sakai@star]$ java ChainHashtableTest
住所データを格納
杉山: 稲城,東京 208
佐々木: 座間,神奈川 228 → 小澤: 多摩,東京 206
ONGS Inc.: 渋谷,東京 151 → 後藤: 川崎,神奈川 214
データの取得: 後藤
後藤: 川崎,神奈川 214
杉山: 稲城,東京 208
佐々木: 座間,神奈川 228 → 小澤: 多摩,東京 206
ONGS Inc.: 渋谷,東京 151 → 後藤: 川崎,神奈川 214
データの削除: ONGS Inc.
杉山: 稲城,東京 208
佐々木: 座間,神奈川 228 → 小澤: 多摩,東京 206
後藤: 川崎,神奈川 214
[sakai@star]$
ハッシュ表の大きさが３なので
衝突が起きたときはリスト保持
開番地法
キー
既にデータが
格納されている
ハッシュ
再ハッシュ
ここも既にデータが
格納されている
再ハッシュの方法
•線形走査法
•二重ハッシュ法
•均一ハッシュ法
再ハッシュ
この場所は空なので
ここに格納する
図2.7.4 教科書131ページ
および教科書134ページ
空き番地法を用いた場合の削除
キー
同じハッシュ値だけ
ど、これじゃない。
ハッシュ
再ハッシュ
削除フラグを格納
削除したい
削除
データは消えてるけ
ど、これでもない。
削除フラグ
再ハッシュ
このデータを
探索したい
これだっ！
教科書134ページ
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)
}
{
1回目のハッシュは剰余演算
2回目以降は一定間隔離す
距離は前の値から1～3
1固定の場合は線形走査法と同じ
固定値にしないときは二重ハッシュ法
}
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;
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;
}
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);
if((null == this.table[hashCode]) || (this.removedData == this.table[hashCode])){
this.table[hashCode] = anAddressData;
return true;
}
}
return false;
}
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);
if(null == this.table[hashCode]){
return null;
}
if(this.removedData != this.table[hashCode]){
if(this.table[hashCode].getName().equals(aKey)){
return this.table[hashCode];
}
}
}
return null;
}
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);
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;
}
}
}
return false;
}
[sakai@star]$ java OpenAddressHashtableTest
null
null
null
null
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
ONGS Inc.: 渋谷,東京 151
削除されました
削除されました
削除されました
削除されました
ONGS Inc.: 渋谷,東京 151
既にデータが
格納されている
キー
配列サイズ１０
ステップ幅５
ハッシュ
再ハッシュ
+5 mod 10
ここも既にデータが
格納されている
再ハッシュ
よくない二重ハッシュ法
空きがあった!
既にデータが
格納されている
キー
ハッシュ
再ハッシュ
配列サイズ１１
ステップ幅５
ここも既にデータが
格納されている
再ハッ
+5 mod 11
シュ
二重ハッシュ法

Download Report