# CMU DB 6. Hash Tables
tags: CMU DB
宿題も出てきた．これは確実にやらない．
授業
ページから読み書きをする実行エンジンをどう支えるかについて話す．
- Hash Tables
- Trees
data organizationとconcurrencyを考え出てデザインする必要がある．
ハッシュテーブルとは順不同のキーを値に対応させる連想配列．ハッシュ関数を使いオフセットを与えられたキーにとっての配列に計算する．
- 空間計算量: $O(n)$
- 時間計算量
- 平均: $O(1)$
- 最悪: $O(n)$
static hash tableではキーのmodを取り，配列から要素を探す．
これはキーの衝突が起きないことを仮定している．
ハッシュテーブルとハッシュスキームに関してデザインによるトレードオフがある．
Hash Functions
あるキーに対応する整数を返す．DBMSでは暗号のためのハッシュ関数を使いたくはないのでそれよりは早く低い衝突率のものが欲しい．
Static Hashing Schemes
- linear probe hashing
- robin hood hashing
- cuckoo hashing
という方法がある．
Liner Probe Hashing
巨大なテーブルを用意する．
テーブルの次の空のスロットを線形探索して衝突を解決する．
削除のときに空のスロットが値の入ったスロットの間に生じて問題と成るかも知れない．
- 削除した所に印をつける
- 次の値が入ったスロット達の位置をずらす
という解決方法がある．
Robin Hood Hashing
- seperate linked list
- 値を他のストレージに保存する
- redundant keys
- 複製したものをハッシュテーブルに入れる
linear probe hashingの変種．衝突した回数を数えて，その回数を使ってあれこれする．
Cuckoo Hashing
異なるハッシュ関数で複数のハッシュテーブルを使う．
Dynamic Hashing Schemes
これまでは格納する要素の数をDBMSが知っている必要があった．
Dynamic hashing tablesは必要に応じてサイズを変えられる
Chained Hashin
bucketsの連結リストをハッシュテーブルのスロットとして保持する．
Extendible Hashing
連結リストを無限に増やす代わりにbucketsを分割する
ハッシュ化したときのbitの先頭をいくつか見てbucketsに入れる．bucketの大きさが最大になったら見るbitの数を増やす
Linear Hashing
overflowしたときにbucketをポインタの場所で分割する
結論
DBMSの内部では$O(1)$を支える早いデータ構造が使われる
ハッシュテーブルはよくtable indexを使うためにほしいものではない．
次はB+ Treesをやるらしい←最高のデータ構造
感想
データ構造の選択が重要だというのは感じた．この授業は総復習という感じで本当に面白い．
