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

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

ハッシュ表探索の基礎

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

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

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

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

例） 435 Mod 10 = 5

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

格納位置	データ
0
1
2	692
3	283
4
5	435
6
7	167
8
9

ここから１６７というデータの格納位置を検索する場合、
まず１６７のハッシュ値を求め（＝７）、
格納位置が７であるレコードのデータをみると１６７となっています。

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

実装

データの格納

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('該当データなし');
}

オープンアドレス法

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

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

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

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

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

今回の場合だと、

格納位置２で衝突
↓
次の３でもまた衝突
↓
次の４は空

となるため、３１２は格納位置４に入ることになります。

↓

格納位置	データ
0
1
2	692
3	283
4	312
5	435
6
7	167
8
9

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

まず３１２のハッシュ値を求め（＝２）、
格納位置が２であるレコードのデータをみると６９２となっています。

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

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

実装

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

格納位置	データ
0	-1
1	-1
2	692
3	283
4	312
5	435
6	-1
7	167
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します。
もし再ハッシュ値が１０になった場合は０に戻します。

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

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

データの探索

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

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

let flg = -1;

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

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

②-１（空き）である場合、
flg に-２を入れます。（flg が-１ではなくなったのでループは終了します）

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

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

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

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

チェイン法

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

たとえば、１００，２００，１０１，１０２，１０３，１０４の順に格納するとしましょう。

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

もし２００がなければ…

格納位置	データ
0	100
1	101
2	102
3	103
4	104
5
6
7
8
9

実際は…

格納位置	データ
0	100
1	200
2	101
3	102
4	103
5	104
6
7
8
9

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

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

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

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

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

ではチェイン法で１００，２００，１０１，１０２，１０３，１０４，３００，４００の順に格納してみます。

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

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

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

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

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

格納位置	データ	ポインタ
0	100	5
1	101
2	102
3	103
4	104
5	200
6
7
8
9

続いて３００ですが、格納位置０で再び衝突が発生します。
格納位置６に３００を入れ、衝突が発生したレコードのポインタ（５）をたどり、そこに格納位置を保存します。

格納位置	データ	ポインタ
0	100	5
1	101
2	102
3	103
4	104
5	200	6
6	300
7
8
9

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

格納位置０で衝突が起きるため、格納位置７に４００を格納し、
衝突が起きたレコードのポインタをたどり（５→６）、
格納位置６のポインタに７を保存します。

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

格納位置	データ	ポインタ
0	100	5
1	101
2	102
3	103
4	104
5	200	6
6	300	7
7	400
8
9

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

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

格納位置５、一致せず
↓
ポインタが示す６をみる
↓
格納位置６、一致せず
↓
ポインタが示す７をみる
↓
格納位置７，一致

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

実装

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

格納位置	データ	ポインタ
0	100	5
1	101	-1
2	102	-1
3	103	-1
4	104	-1
5	200	6
6	300	7
7	400	-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 の値が０以上の場合は格納位置を示し、
-１の場合は「該当データなし」を示します。

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

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

参考書