第 13 回 ハッシュテーブルを 使ったプログラム
～高速に検索するには？～
学習目標
ハッシュテーブルの概念を説明できる
ハッシュテーブルの利点･欠点を説明できる
検索における key と value の関係を説明で きる
簡単なハッシュテーブルの仕組みを説明で きる
ハッシュテーブルを実装できる
汎用的なハッシュテーブルを実装できる
13.1 ハッシュテーブルとは
13.1.1 検索と効率
13.1.2 ハッシュテーブル概要
13.1.3 key と value
13.1.1 検索と効率
リニアサーチ
O(N)
バイナリサーチ
O(logN)
ハッシュテーブル→ O(1)
13.1.2 ハッシュテーブル概要
配列の番地にそのまま入れておけば、
直接検索できる
商品番号 1001 のコーラは配列の 1001 番 地に入れておく
0 1 2 3
1000
1001 コーラ
1002 1003
・・・・・
配列番号 インスタンス
13.1.3 key と value
key
検索するためのキー
value
格納されている値
1001 colaObject
1002
1003
1004
sodaObject
chaObject
ddObject
key value
13.2 ハッシュテーブルの仕組 み
13.2.1 名前をキーに検索できるように
する
13.2.2 ハッシュ値を求める
13.2.3 番地の衝突を回避する
13.2.4 ハッシュテーブルの利点･欠点
13.2.1 名前をキー
に検索できるようにする
名前をキーにしよ う
Id で商品種類を扱 うのはややこしい
ハッシュテーブル は文字列のキーが 得意
” コーラ”
colaObject
” ソーダ”
” お茶”
”DD”
sodaObject
chaObject
ddObject
key value
13.2.2 ハッシュ値を求める
① 名前を数字に変換する
② 配列の番号と対応させる
③ 小さい配列で済むようにするには
① 名前を数字に変換する
インデックシング
文字として扱っている間は、コンピュータ では検索できないので、何らかの数字に変 換する
コ
98
－
103
ラ67
変換表コーラ →
9810367
例えば、こんなやり方があります（詳しくは専門書を参照）
Java でハッシュ値を求める
Java では Object クラスに hashcode() メソッドがあるので、どんなオブジェ クトでも、簡単に求めることができま す
String cola = "
コーラ ";int hashCode = cola.hashCode();
もちろん String ク ラスも Object ク ラスを継承してい
るよ
② 配列の番号と対応させる
例えば、コーラを 9810367 という数字 に変換したら対応する配列の番地に挿 入する
こうしておけば、
11 回で検索できる
2 3 4
9810366
9810367 コーラ 9810368
9810369
・・・・・
しかし、そんなに大きな配列を作るのは無駄
③ 小さい配列で
済むようにするには
例えば 1000 要素の配列で済ませること を考える
1000 で割ったあまりを求める
コーラ →
9810367
→367
1 2 3 4
366
367 コーラ
368 369
・・・・・ ・・・
・・
13.2.3 番地の衝突を回避する
① 番地の衝突
② 衝突回避 (1): 空き番地法
③ 空き番地法の問題点
④ 衝突回避 (2): 分離連鎖法
① 番地の衝突
違うオブジェクトが同じハッシュ値に なる可能性がある
コーラ →
31256448
→448
ソーダ →587648448
→448
② 衝突回避 (1): 空き番地法
1 2 3 4
447
448 コーラ
449 ソーダ
500 DD レモ
・・・・・
ソーダも入 りたい！
もし計算された番地にすでにデータが格納さ れていた場合次の番地にデータを格納する
次も格納されていたらさらに次の番地に格納しよ うとする
検索するときにはハッシュ値を求めた後、そ
の番地から順に配列の中身をリニアサーチで
調べる
空き番地法のリスト ( 追加 )
// 新たに商品種類を追加する
// 配列がいっぱいではないと信じる
// 同じkeyが存在していないことを信じる public void add(ItemType value){
String key = value.getName(); //商品名をキーとする // ハッシュ値を求める
int hashCode = key.hashCode();
int arrayLoc = hashCode % ARRAY_SIZE;
//ハッシュした番地から、空のセルを探す while(true){
if(itemTypeArray[arrayLoc] == null){//空のセルがあった
itemTypeArray[arrayLoc] = value;//空のセルに商品種類を追加する return;
}
//空のセルがなかったら arrayLoc++;//次の項目へ
if(arrayLoc >= ARRAY_SIZE ){//必要ならラップアラウンド arrayLoc = 0;
}
例題 13-1
(ItemTypeList.java)
#add
空き番地法のリスト ( 検索 )
// 商品種類を商品名をキーに検索する
public ItemType search(String key){
//ハッシュ値を求める
int hashCode = key.hashCode();
int arrayLoc = hashCode % ARRAY_SIZE;
//空のセルになるまで順番に探す
while(itemTypeArray[arrayLoc] != null){
if(itemTypeArray[arrayLoc].getName().equals(key)){
//Key が等しい商品が見つかった
return itemTypeArray[arrayLoc];
}
arrayLoc++;//次の項目へ
if(arrayLoc >= ARRAY_SIZE ){// 必要ならラップアラウンド arrayLoc = 0;
} }
return null;// 見つからなかった }
例題 13-1
(ItemTypeList.java)
#search
③ 空き番地法の問題点
クラスター化
集中して埋まってしまう個 所ができてしまう
1 2 3 4 5 6 7 8 9 10 11 12
リニアサーチが長くなって効率が 落ちる
クラスター化を防ぐ
平方探索
重複した時に、次の番地ではなく 1,4,9,16 こ先と少し離れた場所に置く
第 2 種クラスター化
ダブルハッシュ
キーの値によって次の番地を決める
分離連鎖法
次に説明する方法
④ 衝突回避 (2): 分離連鎖法
1 2 3 4
447
448 コーラ
449 500
・・・・・
ソーダ DD レモ ン
衝突したら、その番地からさらに連結リスト を使ってデータを格納する
検索するときにはハッシュ値を求めた後、そ
の番地から順に連結リストを使って調べる
分離連鎖法のリスト ( 追加 )
// 同じkeyが存在していないことを信じる public void add(ItemType value){
String key = value.getName();//商品名をキーに設定する // ハッシュ値を求める
int hashCode = key.hashCode();
int arrayLoc = hashCode % ARRAY_SIZE;
LinkObject insertLink = new LinkObject(value);
if (itemTypeLinkArray[arrayLoc] == null){
//ハッシュした番地が未使用だったとき
itemTypeLinkArray[arrayLoc] = insertLink;//追加 }else{
//ハッシュした番地が使用済みだったとき
LinkObject current = itemTypeLinkArray[arrayLoc];//現在検索中のリンク while (true){
if(current.getNext() == null){
//連結リストの最後が見つかった current.setNext(insertLink);
break;
}else{
//次のリンクを検索中のリンクに設定 current = current.getNext();
} }
例題 13-2
(ItemTypeList.java)
分離連鎖法のリスト ( 検索 )
// 商品種類を商品名をキーにして検索する public ItemType search(String key){
//ハッシュ値を求める
int hashCode = key.hashCode();
int arrayLoc = hashCode % ARRAY_SIZE;
LinkObject current = itemTypeLinkArray[arrayLoc];//現在検索中のリンク while (current != null){
// ハッシュした番地に調査していないリンクオブジェクトが残っている if(current.getValue().getName().equals(key)){
// 検索対象が見つかった
return current.getValue();
}else{
// 次のリンクを検索中のリンクに設定 current = current.getNext();
} }
// ハッシュした番地にリンクオブジェクトがなかったとき return null;//見つからなかった
例題 13-2
(ItemTypeList.java)
#search
13.2.4
ハッシュテーブルの利点･欠点
考えてみよう
ハッシュテーブルの利点･欠点
利点
検索が速い →
O(1)
名前でも速く検索できる
バイナリサーチでも工夫すればできる
欠点
あるキーによる検索しかできない
名前をキーにしたら、 idでの検索はリニアサーチ
データの保持に内部的には配列を使用するので、事前に用 意した配列が満杯に近づいてくると検索、挿入の効率が格 段に落ちる
保持するデータを昇順や降順にソートして取り出すといっ た機能はない
13.3 汎用的なハッシュテーブ ル
13.3.1 汎用的なハッシュテーブルの実
装
13.3.2 JavaAPI を利用する
13.3.1 汎用的な
ハッシュテーブルの実装
第 12 回で作った汎用的な List のように 汎用的なハッシュテーブルを作ること を考える
分離連鎖法で実装する
商品種類 - 名前 - 商品番号 - 価格
商品種類リスト + 追加 商品種類( newI temType) + 削除 商品種類( del eteI temType) + 検索(Stri ng 名前)
1
0. . n 1
0. . n
Hashtabl e 汎用
+ 追加(Obj ect key, Obj ect val ue) + 削除(Obj ect key)
+ 検索(Obj ect key)
ObjectHashTable
インターフェイス
void put(Object key,Object value)
key
とvalue
の組を追加する
Object get(Object key)
与えられた
key
で検索する
void remove(Object key)
与えられた
key
とvalue
の組を削除する
Object[] keys()
display
メソッドのために、すべてのキーを取得する
ハッシュテーブルのリスト
/*** 連結リストオブジェクトクラス
*/
public class LinkObject {
private Object key; // キー private Object value; // 値
private LinkObject next; // 次の要素への参照 /**
* コンストラクタ
*/ public LinkObject(Object newKey,Object newValue){
key = newKey;
value = newValue;
}
例題 13-3 (LinkObject.java)
ハッシュテーブルのリスト ( 追加 )
// キーと値のペアをハッシュテーブルに格納する public void put(Object key,Object value){
//ハッシュ値を求める
int hashCode = key.hashCode();
int arrayLoc = hashCode % ARRAY_SIZE;
//追加する
LinkObject insertLink = new LinkObject(key,value);
if (itemTypeLinkArray[arrayLoc] == null){
//ハッシュした番地が未使用だったとき->そのまま追加 itemTypeLinkArray[arrayLoc] = insertLink;
size++;//追加したのでHashTableのサイズを一つ増やす return;
}else{
//ハッシュした番地が使用済みだったとき->連結リストに追加
LinkObject current = itemTypeLinkArray[arrayLoc];//現在検索中のリンクを設定する // 連結リストの最後を探す
while (true){
if(current.getNext() == null){
//連結リストの最後が見つかった
current.setNext(insertLink);//最後に連結する size++;//追加したのでHashTableのサイズを一つ増やす return;//連結完了
}else{
//見つからない
current = current.getNext();//次のリンクを検索中のリンクに設定 }
例題13-3
(ObjectHashTable.java)
#add
13.3.2 JavaAPI を利用する
ハッシュテーブルも良く使われるので
、用意されている
Map
HashMap
key
とvalue
でデータを格納する クラスのインターフェイスHashtable
を使ってMap
を実装 したクラスMap クラスの API
ObjectHashtable と同じメソッド
void put(Object key,Object value)
Object get(Object key)
void remove(Object key)
ObjectHashtable と異なるメソッド
Set keySet()
すべてのキーを
Set
というインターフェイスで取得する
Set
とは重複のないList
のこと 得られた
Set
に対し、toArray()
を呼べばObjectHashtable
と同様の配列が得られるMap map = new HashMap();
