第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番地に入れておく 配列番号 インスタンス 1 2 3 1000 1001 コーラ 1002 1003 ・・・・・

13.1.3 keyとvalue key value key value 検索するためのキー 格納されている値 1001 colaObject 1002 sodaObject 1003 chaObject 1004 ddObject

13.2 ハッシュテーブルの仕組み 13.2.1 名前をキーに検索できるようにする 13.2.2 ハッシュ値を求める 13.2.3 番地の衝突を回避する 13.2.4 ハッシュテーブルの利点･欠点

13.2.1 名前をキー に検索できるようにする key value 名前をキーにしよう Idで商品種類を扱うのはややこしい ハッシュテーブルは文字列のキーが得意 key value ”コーラ” colaObject ”ソーダ” sodaObject ”お茶” chaObject ”DD” ddObject

13.2.2 ハッシュ値を求める ①名前を数字に変換する ②配列の番号と対応させる ③小さい配列で済むようにするには

①名前を数字に変換する インデックシング 文字として扱っている間は、コンピュータでは検索できないので、何らかの数字に変換する 例えば、こんなやり方があります（詳しくは専門書を参照） 変換表 コ 98 コーラ　　　　→ 9810367 － 103 ラ 67

もちろんStringクラスもObjectクラスを継承しているよ Javaでハッシュ値を求める JavaではObjectクラスにhashcode()メソッドがあるので、どんなオブジェクトでも、簡単に求めることができます もちろんStringクラスもObjectクラスを継承しているよ String cola = "コーラ"; int hashCode = cola.hashCode();

②配列の番号と対応させる 例えば、コーラを9810367という数字に変換したら対応する配列の番地に挿入する こうしておけば、1回で検索できる 1 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 コーラ　　　　→ 31256448　　　　→　　　　448 ソーダ　　　→ 587648448　　　　→　　　　448

②衝突回避(1):空き番地法 もし計算された番地にすでにデータが格納されていた場合次の番地にデータを格納する 次も格納されていたらさらに次の番地に格納しようとする 検索するときにはハッシュ値を求めた後、その番地から順に配列の中身をリニアサーチで調べる ソーダも入りたい！ 1 2 3 4 447 448 コーラ 449 ソーダ 500 DDレモン ・・・・・

空き番地法のリスト(追加) 例題13-1 (ItemTypeList.java) #add //新たに商品種類を追加する //配列がいっぱいではないと信じる //同じ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

空き番地法のリスト(検索) 例題13-1 (ItemTypeList.java) #search //商品種類を商品名をキーに検索する 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;//見つからなかった

③空き番地法の問題点 クラスター化 集中して埋まってしまう個所ができてしまう リニアサーチが長くなって効率が 落ちる 1 2 3 4 5 6 7 8 9 10 11 12 13 リニアサーチが長くなって効率が 落ちる

クラスター化を防ぐ 平方探索 ダブルハッシュ 分離連鎖法 重複した時に、次の番地ではなく1,4,9,16こ先と少し離れた場所に置く 第2種クラスター化 ダブルハッシュ キーの値によって次の番地を決める 分離連鎖法 次に説明する方法

④衝突回避(2):分離連鎖法 衝突したら、その番地からさらに連結リストを使ってデータを格納する 検索するときにはハッシュ値を求めた後、その番地から順に連結リストを使って調べる 1 2 3 4 447 448 コーラ 449 500 ソーダ DDレモン ・・・・・

分離連鎖法のリスト(追加) 例題13-2 (ItemTypeList.java) //同じ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; //次のリンクを検索中のリンクに設定 current = current.getNext(); } 例題13-2 (ItemTypeList.java)

分離連鎖法のリスト(検索) 例題13-2 (ItemTypeList.java) #search //商品種類を商品名をキーにして検索する 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のように汎用的なハッシュテーブルを作ることを考える 分離連鎖法で実装する

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)

(ObjectHashTable.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);//最後に連結する return;//連結完了 //見つからない current = current.getNext();//次のリンクを検索中のリンクに設定 } 例題13-3 (ObjectHashTable.java) #add

13.3.2 JavaAPIを利用する ハッシュテーブルも良く使われるので、用意されている keyとvalueでデータを格納する クラスのインターフェイス Hashtableを使ってMapを実装 したクラス (実は、Hashtableを使わなくても keyとvalueでデータを格納する方法がある)

MapクラスのAPI ObjectHashtableと同じメソッド 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(); Object keys[] = map.keySet().toArray();