ハッシュ表 データ構造とプログラミング（１２）

Presentation on theme: "ハッシュ表 データ構造とプログラミング（１２）"— Presentation transcript:

1 ハッシュ表 データ構造とプログラミング（１２）
大岩 元 慶応大学環境情報学部

2 ハッシングの考え方 配列をデータベースに用いる キーを配列のインデクスに対応させればO(1)でアクセスできる 欠点
拡張が困難 順序性のアクセスが不利 語の文字が表わす値を足す　－＞衝突 ２７進法（アルファベット）の数値　－＞隙間ばかり

3 ハッシュ関数の一例 モジュロ演算（％）を使って数の範囲を縮小 衝突(collision)が発生する
２３％４=３　１３０５２％４=０　３８％４=２　　　　　６４３％４=３　１２９％４=１　６４％４=０ arrayIndex = hugeNumber % arraySize 衝突(collision)が発生する 空き番地法 arraySize ≒ numberSize * 2 分離連鎖法 arraySize ≒ numberSize

4 find( )メソッド 線型探査による空き番地法
public DataItem find(int key){ //キーの値がkeyの項目を見つける int hashVal = hashFunc(key); //keyをハッシュする while (hashArray[hashVal] != null) //{空のセルに出会うまで if(hashArray[hashVal].iData == key) //キーを見つかたら return hashArray[hashVal]; ++hashVal; //次のセルへ行く hashVal %= arraySize; //必要ならップアラウンドする } return null; //項目が見つからない

5 insert( ) メソッド 線型探査による空き番地法
public vioid insert(DataItem item) { // DataItem を挿入する int key = item.iData: // キーを取り出す int hashVal = hashFunc(key); //　key をハッシュする while (hashArray(hashVal) != null && // 空のセルに出会うまで hashArray(hashVal.iData) != -1 ) {// 　++hashVal; // hashVal %= arraySize; // } hashArray[hashVal] = item; } // insert()の終り

6 Delete( ) メソッド 線型探査による空き番地法
public DataItem delete( int key) { //DeleteItemを削除する int hashVal = hashFunc(key) ; //key をハッシュする while ( hashArray[hashVal] != null) { //空のセルを見つけるまで if ( hashArray[hashVal].iData == key) { //キーを見つけたら DataItem temp = hashArray[hasVal] ; //項目そセーブする hashArray[hashVal] = nonItem : //項目を削除する return temp : //項目を返す } ++hashVal ; //次のセルに行く hashVal %= arraySize ;　 //必要ならラップアラウンドする　　　　　　　　 return null ; //項目が見つからない } //delete () の終り

7 平方探査とダブルハッシュによる空き番地法
表の占有率が２／３をこえると性能が落ちる できれば１／２にしたい 表のサイズは素数にする 線型探査では衝突でクラスター（項目の続き）ができる Ｘ＋１，ｘ＋４，ｘ＋９，……に置く（平方探査） キーに対して別のハッシュ関数を使って２度目のハッシュを行なう（ダブルハッシュ）

8 分離連鎖法