ハッシュ表
データ構造とプログラミング（１２）
大岩 元
慶応大学環境情報学部
[email protected]
ハッシングの考え方
配列をデータベースに用いる
キーを配列のインデクスに対応させればO(1)
でアクセスできる
欠点
拡張が困難
順序性のアクセスが不利
語の文字が表わす値を足す －＞衝突
２７進法（アルファベット）の数値 －＞隙間ば
かり
ハッシュ関数の一例
モジュロ演算（％）を使って数の範囲を縮小
２３％４=３ １３０５２％４=０ ３８％４=２
６４３％４=３ １２９％４=１ ６４％４=０
arrayIndex = hugeNumber % arraySize
衝突(collision)が発生する
空き番地法 arraySize ≒ numberSize * 2
分離連鎖法 arraySize ≒ numberSize
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; //項目が見つからない
}
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()の終り
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 () の終り
平方探査とダブルハッシュによる空き
番地法
表の占有率が２／３をこえると性能が落ちる
できれば１／２にしたい
表のサイズは素数にする
線型探査では衝突でクラスター（項目の続き）
ができる
Ｘ＋１，ｘ＋４，ｘ＋９，……に置く（平方探査）
キーに対して別のハッシュ関数を使って２度
目のハッシュを行なう（ダブルハッシュ）
分離連鎖法