2003年 4月 1日 ハッシュ・キー >> 目次 (テーマ ごと)


 
 データ に対する アクセス 法には、以下の 3つがある。

 (1) セット・アット・ア・タイム 法 (set-at-a-time)
 (2) レコード・アット・ア・タイム 法 (record-at-a-time)
 (3) ハッシュ 法 (hashing)

 セット・アット・ア・タイム 法は (直積集合を使った) 「column 単位 (view 単位)」 の アクセス 法である。
 レコード・アット・ア・タイム 法は (キー を使った) 「indexing」 の アクセス 法である。
 ハッシュ 法は 「indexing」 を使わない。ページ のなかに収められている データ を直接に アクセス する手法である。

 複数の ページ (page)を束ねた 1つの単位を 「バケット (bucket)」 という。
 データ を バケット のなかに収める (割り振る) ために 「ハッシュ 関数」 を使う。
 ハッシュ 関数は、通常、以下の算式が使われる。

  h (n) = v mod n (v を n で割った余りの値)

 ただし、v は キー 値、n は バケット の数とする。
 例えば、バケット 数が 4 であれば、キー の値が 13 である レコード は 1番目の バケット に収められる。
 [ h (13) = 13 mod 4 = 1 ]。

 今回は、ハッシュ の 「からくり」 を示すために、単純な以下の前提を使う。

 (1) キー の桁数は 2桁とする (たとえば、01, 02, ・・・)
 (2) ハッシュ 関数は 「1 の位と 10 の位を合計した数値」 とする。
 (3) バケット は、9つの ページ から構成される。

 したがって、キー 値が 01 であれば、1番目の ページ に収められ、キー 値が 02 であれば、2番目の ページ に収められ、キー 値が 09 であれば、9番目の ページ に収められる。



バケット
ページ ページ ページ ページ ページ ページ ページ ページ ページ
01 02 03 04 05 06 07 08 09

 
 さて、キー の値が 10 である データ を考えてみる。
 与えられた ハッシュ 関数は 「1 の位と10 の位を合計した値」 であるから、10 は バケット の 1番目に収められる。
 1番目の ページ には、すでに、01 が収められているので、1番目 ページ から データ を得ようとすれば、01 なのか 10 なのかを判断しなければならない。
 1つの ページ のなかに複数の データ が収められている状態を 「ハッシュ の衝突 (conflict)」 という。

 さらに、たとえば、キー の桁数を 5桁くらいにしてみれば、100 や 1000 や 10000 も 1番目の ページ に収められることになる。そして、たとえば、1つの ページ のなかに データ を収める領域が足らなくなれば、「オーバーフロー 域 (overflow)」 を用意して、オーバーフロー 域のなかに データ を収めて、ページ と オーバーフロー 域を チェーン を使って結んで (chained) アクセス・パス (path) を生成することになる。
 これを 「バケット の溢れ (overflow)」 という。

 1つの ページ のなかに 1つの データ を収めれば、レコード・アット・ア・タイム 法の indexing (パス を 「たぐる」 構造) に比べて、高 パフォーマンス を実現する。ただし、メモリー などの資源を多大に費消することになる。
 したがって、高 パフォーマンス の実現と資源の費消を天秤にして、最適な ハッシュ 関数を考えなければならない。



  << もどる ベーシックス すすむ >>
  データベースの基礎知識