講義＃07：ハッシュテーブル

カバー

1. データ構造#

DBMS には、次のようなデータが含まれます。

内部メタデータ：データベースとシステムに関する情報を記録します。
コアデータストレージ：タプルの情報を記録します。
一時データ構造
テーブルインデックス

次の 2 つの問題を主に考慮します。

データの組織化
データの信頼性

2. ハッシュテーブル#

ハッシュテーブル

ハッシュテーブルのターゲット

ハッシュ関数

値をより小さなキーに変換します。
速度と 衝突率 の間でバランスを取ります。

ハッシングスキーム

衝突の処理方法
ハッシュテーブルのサイズ と 追加情報の維持 のバランスを取る必要があります。

3. ハッシュ関数#

入力のキーに関係なく、特別な 数字を出力する関数です。

ハッシュ関数

ハッシュ関数のベンチマーク

4. 静的ハッシュスキーム#

4.1 線形プローブハッシング#

線形プローブハッシングは、ハッシュの衝突を解決する方法です。ハッシュ関数が返す位置が既に占有されている場合、表の空の値が見つかるまで位置を下に移動し続けます。

削除操作では、ハッシュ関数によって直接生成された値ではなく、連続的な位置の値が削除される場合があります。

この場合、次の方法を採用します。

オフセットに影響を受ける値を調整します。再ハッシュの方法で調整しますが、効率は低いです。
削除された値を削除済みとしてマークします。これらの値は、新しい値が使用される必要がある場合に再利用できますが、定期的なガベージコレクションが必要です。

同じ値を格納する

ユニークキーではない

同じキーを持つが異なる値を持つ値を格納する場合、次の 2 つの方法で解決できます。

各キーに対して個別のスペースを割り当てます。
すべてのキーをハッシュ関数でハッシュ化し、1 つのストレージ空間に散在させます。

4.2 Robin Hood ハッシング#

これは線形プローブアルゴリズムのアップグレードバージョンであり、分布の不均一性の問題を解決することを目指しています。上記のアルゴリズムでは、ハッシュ計算後に一部のキーがクラスタリングされ、ハッシュアルゴリズムが劣化する可能性があります。 Robin Hood ハッシングは、衝突を回避する方法として、一部のrichキーをpoorキーに割り当てます。

この衝突を回避する方法は、各値にオフセット値を記録し、表の値と比較する必要があります。現在のオフセット値が表の値のオフセット値よりも大きい場合、現在の値と表の値を交換します。空きスペースが見つかるまで続けます。

void Robin_hood_Hashing(int key) {
     int val = hash(key);
     int offset = 0;
     for (int i = val ; ; i ++ , offset ++ ) {
          if(hash_table->is_empty(i)){ 
               hash_table->insert(i , val , offset);
               break;
          }

          if(hash_table->get_offset(i) < offset) {
               auto [n_val , n_offset] = hash_table->get_data(i);
               hash_table->insert(i , val , offset);
               val = n_val , offset = n_offset;
          }
          if(i == MAXSIZE) i = 0;
     }
}