ハッシュ法
ハッシュ関数 $ H(x) $ には
- 単純なこと
- 用意している配列の要素数以下を返すこと
- なるべく一様に結果を返す（かぶりが少ないこと）
が要求されます。が、要求されるだけで確実に満たすものを作るのは困難です。
ハッシュ関数にはよくMod演算（余りを求める）が使われます。
例） $ H(x) = x \space Mod \space 25 $
理由は、2番目の条件を満たすためです。
配列が25個あれば、とりあえずデータを25で割ったあまりを求めておけば０～２４の配列のインデックス範囲内に収まります。
こうすることで、値xがデータ配列のどのインデックスの位置に保存されているかダイレクトにわかることになります。
すなわち、データx は データ配列 Data[] の Data[H(x)]（Data[H(x)] = x）に格納されるということになります。
被りがない時の理想的なハッシュテーブル
#include <iostream> using std::cout; using std::cin; using std::endl; int hashTable[8] = {-1, -1, -1, -1, -1, -1, -1, -1}; //ハッシュ関数 x Mod 8 int H(int _x) { return( _x % 8); } //ハッシュ探索関数 int HashSearch(int key) { int hash = H(key); if (hashTable[hash] != -1) { return(hash); } else { cout << "データなし" << endl; return(-1); } } //ハッシュ関数を使って配列に値を格納する int main() { //データdat [26, 53, 59, 84, 142, 161, 175] int dat[7] = {26, 53, 59, 84, 142, 161, 175}; //データをハッシュ値を使って格納していくよ //hashTable[H(26)] = 26; //hashTable[H(53)] = 53; // … = … for(int i=0; i < 7; i++) { hashTable[H(dat[i])] = dat[i]; } for(int i=0; i < 8; i++) { cout << "hashTable[" << i << "] = " << hashTable[i] << endl; } //53を検索 cout << "53はindex" << HashSearch(53) << "に入ってます。"<< endl; return 0; }
しかしながらデータによっては、複数のデータが同一のインデックスを指してしまうことがあります。
授業でやった基本情報技術者試験の問題の例
ハッシュ関数 $ H(x) = x \space Mod \space 8 $
データ列 ： [ 26, 53, 59, 84, 142, 161, 175, 178, 179 ]
のときハッシュ値 $ H(x) $ は、
$ H(x) $ ： [ 2, 5, 3, 4, 6, 1, 7, 2, 3]
すなわち、整数配列dat[8]があった時に
$$
\begin{array}{lll}
データ値& 26 の時&： H(26) = 26 \space Mod \space 8 = 2 & dat[2] = 26\\
データ値& 53 の時&： H(53) = 53 \space Mod \space 8 = 5 & dat[5] = 53\\
データ値& 59 の時&： H(59) = 59 \space Mod \space 8 = 3 & dat[3] = 59\\
データ値& 84 の時&： H(84) = 84 \space Mod \space 8 = 4 & dat[4] = 84\\
データ値& 142の時&： H(142) = 142 \space Mod \space 8 = 6 & dat[6] = 142 \\
データ値& 161の時&： H(161) = 161 \space Mod \space 8 = 1 & dat[1] = 161\\
データ値&175の時&： H(175) = 175 \space Mod \space 8 = 7 & dat[7] = 175\\
データ値&178の時&： H(178) = 178 \space Mod \space 8 = 2 & dat[2] = 178\\
データ値&179の時&： H(179) = 179 \space Mod \space 8 = 3 & dat[3] = 179\\
\end{array}
$$
すなわち
dat[0] = 空 dat[1] = 161 dat[2] = 26, dat[2] = 178 dat[3] = 59, dat[3] = 179 dat[4] = 84 dat[5] = 53 dat[6] = 142 dat[7] = 175
となります。
dat[2]とdat[3]に複数のデータが割り当たってしまってますね。
ここで、
$$
\begin{array}{lll}
データ値& 26 の時&： H(26) = 26 \space Mod \space 8 = 2 & dat[2] = 26\\
データ値& 59 の時&： H(59) = 59 \space Mod \space 8 = 3 & dat[3] = 59\\
データ値&178の時&： H(178) = 178 \space Mod \space 8 = 2 & dat[2] = 178\\
データ値&179の時&： H(179) = 179 \space Mod \space 8 = 3 & dat[3] = 179\\
\end{array}
$$
のように、$ H(x) $の出力値によりインデックスが被ってしまうことがある。
これを、衝突またはシノニムの発生という。
衝突を回避するには
絶賛執筆中
とか書きましたが、仕組み的に回避は無理なので、衝突をなんとか解決するには、配列のデータ構造を工夫します。
当然ですが、配列は「変数」＝「データを入れる箱」の列なので箱１個あたりに値は１個しか入らない。というのが衝突の原因になります。
したがって、１つ箱当たりに複数のデータを入れることを考えればよいことになります。（そりゃそうだ）
そこで、こんな感じのデータを考えてみます（今のところただの２次元配列）
このような配列があると、複数のデータが同じインデックスに割り当たっても対応できそうです。
そして、以下のアルゴリズムを考えてみます。
あるデータxを配列 dat[]に格納する（datの要素数は十分にあるものとする） 配列dat[]の要素はあらかじめ-1で初期化されている ハッシュ関数 H(x) で格納先のIndexが決まっているとき 値Keyがどのインデックスに入っているか探索する ▲ dat[ H(x) ] ≠ -1 | ▲ dat[H(x)] == key | | ・H(x)にデータは存在する | +------------------ | | ・H(x)にデータは存在するが、先頭にはない | ▼ +---------------------- | ・データなし ▼
つまり、
- dat[H(x)]が初期値以外であれば、必ずデータが格納されているはず
- dat[H(x)]が-1ではなく、Keyなら探している値はそこにある
- dat[H(x)]が-1ではなく、keyでなければ、そのIndexにはkey以外にもほかの値がある
ということである。
- dat[H(x)]が-1ではなく、keyでなければ、そのIndexにはkey以外にもほかの値がある
の時は、上の図のdat[H(x)]を横に線形探索することで、keyが見つかるはずである。
２次元配列を使うと
あるデータxを配列 dat[][]に格納する（datの要素数は十分にあるものとする） 配列dat[][]の要素はあらかじめ-1で初期化されている ハッシュ関数 H(x) で格納先のIndexが決まっているとき 値Keyがどのインデックスに入っているか探索する ▲ dat[ H(x) ][0] ≠ -1 | ▲ dat[H(x)][0] == key | | ・H(x)にデータは存在する | +------------------ | | ・H(x)にデータは存在するが、先頭にはない | | ・dat[H(x)][0] ～dat[H(x)][ｎ]まで線形探索 | ▼ +---------------------- | ・データなし ▼
int dat[8][20]
={{xx,-1,-1,…-1},//dat[0][] -1x20個
{xx,-1,-1,…-1},//dat[1][] -1x20個
{xx,-1,-1,…-1},//dat[2][] -1x20個
{xx,-1,-1,…-1},//dat[3][] -1x20個
{-1,-1,-1,…-1},//dat[4][] -1x20個
{xx,-1,-1,…-1},//dat[5][] -1x20個
{xx,-1,-1,…-1},//dat[6][] -1x20個
{xx,xx,xx,…-1},//dat[6][] -1x20個
};
リスト構造（データ構造）
list<int> dat[8] //int型のlistを８個
list[0]:〇→〇
list[1]:〇→〇→〇
list[2]:〇
list[3]:〇→〇
list[4]:〇→〇→〇
list[5]:〇
list[6]:〇→〇
list[7]:〇
リスト構造について
- 配列
- 同じ型のデータの集まり
- Indexを使うことで要素にアクセス可能
- ランダムアクセス可能
- 要素数の追加や削除が大変
- リスト構造
- 同じ型のデータのつながり
- 今指している位置（見ている位置）を表す指標になるデータをつながっている前後にだけ動かせる
- シーケンシャルアクセス
- 要素の追加や削除が楽
C++のSTL::listを使って簡単にリスト構造を実現するよ
#include <iostream> #include <list> using std::cout; using std::cin; using std::endl; using std::list; //STLのlistを使うよっていうinclude //テンプレート（いろんな方に対応できる便利な奴） int main() { //intのリストを作りたいな list<int> ilist; //floatのリストを作りたいな list<float> flist; int indata; do{ cout << "整数を入力："; cin >> indata; if(indata != -1) ilist.push_back(indata); else break; //リストのすべての要素を表示するfor文（ヘッドから勝手にシーケンシャルに最後までアクセス） for(auto& i: ilist) { cout << i << "→"; } //１個ずつきちんとアクセスしたい場合は、イテレータというポインタを使う（ちょっと難しい） //イテレータを使って手動で一個ずつ後ろにシーケンシャルアクセス //list<int>::iterator theI; //for(theI=ilist.begin(); theI !=ilist.end(); theI++) //{ // cout << *theI << "→"; //} cout << endl; }while(true); //ランダムアクセスできないので、配列みたいなアクセスはできない //cout << ilist[2] << endl; }
基本情報の問題解いてみる
https://www.fe-siken.com/kakomon/16_haru/q13.html
16 2 10 （基数） mod 8 int Data[10][5]（ハッシュテーブル） 1A 0001 1010 16+8+2 = 26 2 〇Data[2]←26 [2][0] 35 0011 0101 32+16+5 = 53 5 Data[5]←53 3B 0011 1011 32+16+11 = 59 3 ★Data[3]←59 [3][0] 54 0101 0100 64+16+4 = 84 4 Data[4]←84 8E 1000 1110 128+14 = 142 6 Data[6]←142 A1 1010 0001 128+32+1 =161 1 Data[1]←161 AF 1010 1111 128+32+15 =175 7 Data[7]←175 B2 1011 0010 128+32+16+2=178 2 〇Data[2]←178 [2][1] B3 1011 0011 128+32+16+3=179 3 ★Data[3]←179 [3][1] 〇★が衝突（シノニムの発生） dat[127] 出力 データあり →データ dat[2]←94 インデックス 2 データない → -1 dat[2]←-1 データなし データが複数→データ列 dat[2]←94, 8, 3 異なるデータ