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