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

カバー

1. データ構造#

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

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

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

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

2. ハッシュテーブル#

ハッシュテーブル

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

ハッシュ関数

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

ハッシングスキーム

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

3. ハッシュ関数#

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

ハッシュ関数

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

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

4.1 リニアプローブハッシング#

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

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

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

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

同じ値を保存する

ユニークでないキー

同じキーを持つが異なる値を持つ値を保存する場合、2 つの方法があります。

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

4.2 ロビンフッドハッシング#

これはリニアプローブアルゴリズムのアップグレードバージョンであり、分布の不均衡を解決することを目指しています。上記のアルゴリズムでは、ハッシュ計算後、一部のキーがクラスタリングされてハッシュアルゴリズムが劣化する可能性があります。ロビンフッドハッシングは、衝突を解決する方法として、一部の 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;
     }
}