【JavaScriptでアルゴリズム】ハッシュ表探索(オープンアドレス法・チェイン法)

アルゴリズム

今回はハッシュ表探索の基礎から、オープンアドレス法・チェイン法のアルゴリズムについて、JavaScript でコードをみていきたいと思います。

ハッシュ表探索の基礎

ハッシュ表探索とは、データの格納位置を決める際に求めるハッシュ値を使い、特定のデータを探す探索法になります。

データを格納する配列などをハッシュ表と呼び、データの格納位置を決めるときやデータを取り出すときに利用するハッシュ値を求めるための計算式をハッシュ関数といいます。



今回は例として、ハッシュ表の大きさを10、ハッシュ関数を(データ Mod 10)とし、
3桁の整数(435,283,167,692)をハッシュ値と同じ位置に格納します。

A Mod B = A を B で割ったあまり

435 Mod 10 = 5



すると、以下のようなハッシュ表になります。

格納位置データ
0
1
2692
3283
4
5435
6
7167
8
9



ここから167というデータの格納位置を検索する場合、
まず167のハッシュ値を求め(=7)、
格納位置が7であるレコードのデータをみると167となっています。

検索データと一致しているため、格納位置を取得できました。

実装

データの格納

let hashTable = Array(10);

let datas = [435, 283, 167, 692];

for (let i = 0; i < datas.length; i++) {
  let hashVal = datas[i] % hashTable.length;
  hashTable[hashVal] = datas[i];
}
console.log(hashTable);

データの探索

let searchData = 167;
let hashVal = searchData % hashTable.length;

if (hashTable[hashVal] == searchData) {
  console.log(hashVal);
}else{
  console.log('該当データなし');
}

解説

データの格納

let hashVal = datas[i] % hashTable.length;

でハッシュ値を求め、

hashTable[hashVal] = datas[i];

でハッシュ値と同じ格納位置にデータをいれています。

データの探索

特に難しいところはないかと思います。
if 文で格納されているデータと検索データが一致しているか調べています。

if (hashTable[hashVal] == searchData) {
  console.log(hashVal);
}else{
  console.log('該当データなし');
}

オープンアドレス法

ハッシュ関数で格納位置を求めると、同じ位置になる衝突が発生することがあります。

たとえば先ほどのハッシュ表に312を追加しようとすると、格納位置が2になるためすでに入っているデータと衝突してしまいます。

すでに入っているレコード(データ)をホームレコード
衝突のために格納できないレコードをシノニムレコードといいます。



これを解消するため、オープンアドレス法では、衝突したら再ハッシュ値を求めます。
ハッシュ値+1を使うことが多いです)

つまり、衝突が発生したら空きレコードが見つかるまで次々と調べ、見つかったらそこに格納するという方法になります。


今回の場合だと、

格納位置2で衝突

次の3でもまた衝突

次の4は空

となるため、312は格納位置4に入ることになります。

格納位置データ
0
1
2692
3283
4312
5435
6
7167
8
9



ではここからは、312というデータの格納位置を検索してみます。

まず312のハッシュ値を求め(=2)、
格納位置が2であるレコードのデータをみると692となっています。

検索データと一致しないため、次の格納位置3のデータをみると283でありまだ一致しません。

その次の格納位置4をみると312であり、検索データと一致したため、格納位置が取得できました。

実装

このプログラムを実装するにあたり、あらかじめ空きデータに-1をいれておき、データが格納されたら上書きするようにしています。

格納位置データ
0-1
1-1
2692
3283
4312
5435
6-1
7167
8-1
9-1

データの格納

let hashTable = Array(10);
hashTable.fill(-1);

let datas = [435, 283, 167, 692, 312];

for (let i = 0; i < datas.length; i++) {
  let hashVal = datas[i] % hashTable.length;

  while (hashTable[hashVal] != -1) {
    hashVal++;

    if (hashTable.length == hashVal) {
      hashVal = 0;
    }
  }
  hashTable[hashVal] = datas[i]; 
}
console.log(hashTable)

データの探索

let searchData = 312;
let hashVal = searchData % hashTable.length;

let rehashVal = hashVal;
let flg = -1;

while (flg == -1) {
  if (hashTable[rehashVal] == searchData) {
    flg = rehashVal;
    break;
  }else if(hashTable[rehashVal] == -1) {
    flg = -2;
  }else{
    rehashVal++;
  }
  
  if (rehashVal == hashTable.length) {
    rehashVal = 0;
  }

  if (rehashVal == hashVal) {
    flg = -2;
  }
}

if (flg > -1) {
  console.log(flg);
}else{
  console.log('該当データなし');
}

解説

データの格納

格納位置にすでにデータが入っている場合は、空きを見つけるまでハッシュ値を+1します。
もし再ハッシュ値が10になった場合は0に戻します。

  while (hashTable[hashVal] != -1) {
    hashVal++;

    if (hashTable.length == hashVal) {
      hashVal = 0;
    }
  }

データの探索

変数 flg は、最終的な格納位置を管理します。

flg が0以上の場合は格納位置を示し、
-2の場合は「該当データなし」を示します。

let flg = -1;



ハッシュ値(再ハッシュ値)と同じ格納位置にあるデータが

①検索データと一致する場合、
flg にそのハッシュ値を入れてループを終えます。

②-1(空き)である場合、
flg に-2を入れます。(flg が-1ではなくなったのでループは終了します)

③それ以外(別のデータが入っている場合)
再ハッシュ値を+1します。

  if (hashTable[rehashVal] == searchData) {
    flg = rehashVal;
    break;
  }else if(hashTable[rehashVal] == -1) {
    flg = -2;
  }else{
    rehashVal++;
  }


再ハッシュ値が元々のハッシュ値と同じ値になった場合、
つまり、すべてのデータを調べたが見つからず配列を一周した場合
flg に-2を入れます。

  if (rehashVal == hashVal) {
    flg = -2;
  }

チェイン法

オープンアドレス法は、シノニムレコードを空いているところに格納しますが、そのため本来その位置に格納されるはずのデータが格納できないことがあります。


たとえば、100,200,101,102,103,104の順に格納するとしましょう。

もし200がなければ、101以降は本来の位置に一発で格納できたはずが、200のせいでことごとく再ハッシュが必要になります。


もし200がなければ…

格納位置データ
0100
1101
2102
3103
4104
5
6
7
8
9


実際は…

格納位置データ
0100
1200
2101
3102
4103
5104
6
7
8
9


ハッシュ表が小さかったりシノニムレコードが多いなどの理由で衝突が頻繁に発生すると効率が悪くなってしまうため、これを解消するためのチェイン法をみていきたいとおもいます。



チェイン法は、あらかじめシノニムレコード用の領域を用意しておき、衝突が発生したらそこへポインタでつなぐというものになります。

ここでいうポインタとは、同じハッシュ値になるデータを示す添字と思ってください。


今回の例では、ハッシュ表の大きさは変わらず10のままですが、
格納位置0~4をホームレコードの領域、
5~9をシノニムレコードの領域としています。

格納位置データポインタ
0
1
2
3
4
5
6
7
8
9


ではチェイン法で100,200,101,102,103,104,300,400の順に格納してみます。

ホームレコードの大きさが5であるため、今回はハッシュ関数を(データ Mod 5)とします。


まずは100を格納位置0に入れます。
すると次の200も格納位置が0になるため衝突が発生します。

ここで200をシノニムレコードの領域に入れ、ポインタでつながりを示します。

格納位置データポインタ
01005
1
2
3
4
5200
6
7
8
9


衝突が起きた200をシノニムレコードの領域に移したことによって、つづく101~104のデータがずれることなくそのまま格納されます。

格納位置データポインタ
01005
1101
2102
3103
4104
5200
6
7
8
9


続いて300ですが、格納位置0で再び衝突が発生します。
格納位置6に300を入れ、衝突が発生したレコードのポインタ(5)をたどり、そこに格納位置を保存します。

格納位置データポインタ
01005
1101
2102
3103
4104
52006
6300
7
8
9


最後の400も同様に考えて格納します。

格納位置0で衝突が起きるため、格納位置7に400を格納し、
衝突が起きたレコードのポインタをたどり(5→6)、
格納位置6のポインタに7を保存します。



では、このハッシュ表から400というデータの格納位置を検索します。

格納位置データポインタ
01005
1101
2102
3103
4104
52006
63007
7400
8
9

まず400のハッシュ値を求め(=0)、その位置のデータを確認します。
すると、検索データと一致しません。
したがってポインタをたどります。

ポインタが示す格納位置5のデータをみると、まだ一致しません。
これをデータが一致するまで続けます。

格納位置5、一致せず

ポインタが示す6をみる

格納位置6、一致せず

ポインタが示す7をみる

格納位置7,一致


これで、格納位置7が取得できました。

実装

今回もこのプログラムを実装するにあたり、あらかじめ空きデータに-1をいれておき、データが格納されたら上書きするようにしています。

格納位置データポインタ
01005
1101-1
2102-1
3103-1
4104-1
52006
63007
7400-1
8-1-1
9-1-1

データの格納

let recordsNumber = 10;
let hashTable = Array(recordsNumber);
let pointerTable = Array(recordsNumber);
let homeRecordLength = 5;
hashTable.fill(-1);
pointerTable.fill(-1);

let datas = [100, 200, 101, 102, 103, 104, 300, 400];

for (let i = 0; i < datas.length; i++) {
  let hashVal = datas[i] % homeRecordLength;
  let rehashVal = hashVal; 
 
  if (hashTable[hashVal] != -1) {
    rehashVal = homeRecordLength;

    while (hashTable[rehashVal] != -1) {
      rehashVal++;
    }

    let pointer = pointerTable[hashVal];

    if (pointer == -1) {
      pointerTable[hashVal] = rehashVal;
    }else{
      while (pointerTable[pointer] != -1) {
        pointer = pointerTable[pointer];
      }
      pointerTable[pointer] = rehashVal;
    }         
  }
   
  hashTable[rehashVal] = datas[i]; 
}
console.log(hashTable);
console.log(pointerTable);

データの探索

let searchData = 400;
let hashVal = searchData % homeRecordLength;
let rehashVal = hashVal;
let flg = -1;

while (rehashVal != -1) {
  if (hashTable[rehashVal] == searchData) {
    flg = rehashVal;
    break;
  }else{
    rehashVal = pointerTable[rehashVal];
  }
}

if (flg > -1) {
  console.log(flg);
}else{
  console.log('該当データなし');
}

解説

データの格納

格納位置にすでにデータが入っている場合は、再ハッシュ値がシノニムレコード領域の最初のレコードの格納位置になるようにしています。

  if (hashTable[hashVal] != -1) {
    rehashVal = homeRecordLength;
    ...
  }


そして、while 文で空きがみつかるまで再ハッシュ値を+1します。

    while (hashTable[rehashVal] != -1) {
      rehashVal++;
    }


続いて衝突が起きたレコードのポインタを取得し、

let pointer = pointerTable[hashVal];


ポインタが空(-1)であればそこに再ハッシュ値を保存し、
そうでなければ、空のポインタを見つけるまでたどっていき、そこに再ハッシュ値を保存します。

    if (pointer == -1) {
      pointerTable[hashVal] = rehashVal;
    }else{
      while (pointerTable[pointer] != -1) {
        pointer = pointerTable[pointer];
      }
      pointerTable[pointer] = rehashVal;
    }  


そして、再ハッシュ値と同じ格納位置にデータを格納します。

hashTable[rehashVal] = datas[i]; 

データの探索

最終的に、変数 flg の値が0以上の場合は格納位置を示し、
-1の場合は「該当データなし」を示します。

検索データが見つかるまでポインタをたどって探索を続け、見つかったらループを終了します。

検索データが存在しない場合、rehashVal が必ず-1となり、flg も初期値の-1から変わらないため、「該当データなし」を表示させることができます。





参考書

コメント

コンタクトフォーム

    タイトルとURLをコピーしました