「みんなのデータ構造」学習メモ：5.1 ChainedHashTable, 5.2 LinearHashTable

みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート

amazon

みんなのデータ構造

作者:Pat Morin
ラムダノート

Amazon

これまでのメモ

今回は第5章にとんで

[P91] 5.1 ChainedHashTable: チェイン法を使ったハッシュテーブル
[P97] 5.2 LinearHashTable: 線形探索法

を読む。

始めに書いておくと、5.1.1 乗算ハッシュ法の数学的な証明部分をちゃんと理解するのを諦めた。
また、LinearHashTable は冒頭の概要説明しか読んでいない。

TypeScript によるソースコード
 https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/ChainedHashTable.ts

ハッシュテーブルとは

ハッシュテーブルとは、広範囲（ $U = 0, 1, ... 2^{w} - 1$ ）に渡る整数のうち、少数（ $n$ ）の要素を格納するのに能率の良い方法。

ハッシュテーブル自体は配列。格納するデータから「ハッシュ値」と呼ばれる整数値を計算し、それを配列の添字とする。
5.1 のChainedHashTableと5.2 LinearHashTableは、異なるデータでハッシュ値が衝突してしまった場合にどうするか、という部分が異なる。

5.1 ChainedHashTable: チェイン法（別名：連鎖法）を使ったハッシュテーブル

ChainedHashTable の場合、ハッシュテーブルとなる配列 t の各要素がリストになっており、ハッシュ値 i が衝突した場合はリスト t[i] に順番にデータを追加していく。

f:id:dackdive:20200310012257p:plain:w480

上の図の場合、データ i および c はともにハッシュ値が 3 であることを示している。

データ数を n としたとき、 $n \leq t.length$ という不変条件を保持する。
こうすると、リストの平均要素数は常に1以下になる。

t の各要素について、書籍では単に「リスト」と表現しているが、web上の情報だとLinked Listとしているものが多いようだった。

ハッシュテーブルの性能

先に5.1.2 要約に記載されている結果を書く。

ChainedHashTable は、ハッシュテーブルの拡張のコストを無視すると、add(x), remove(x), find(x) の期待実行時間は O(1)
空の ChainedHashTable に対して m 個のadd(x), remove(x)からなる任意の操作列を順に実行するとき、ハッシュテーブルの拡張に要する償却実行時間は O(m)

要素の追加・削除・探索に分けて、実行時間を考えてみる。

要素の追加

ハッシュテーブルに要素 x を追加するには、

ハッシュテーブル（配列 t）にデータがすでにたくさんある場合は、配列の大きさを増やす
ハッシュ値 i を計算する
リスト t[i] に x を追加する

という手順が必要。

1 の操作は、ArrayStack のときと同じく、償却実行時間は定数となる（証明は補題2.1らしいが理解できなかった）。
3 の操作は（常に末尾に要素を追加するので）ArrayStackやDLListなど、第2章、第3章で登場したどのリストを使っても、定数時間で可能である。

要素の削除

ハッシュ値 i を計算する
x が見つかるまでt[i] を走査する

となるので、実行時間はリスト t[i] の長さに比例する。 $n_i$ をリスト t[i] の長さとするとき、 $O( n_{hash(x)} )$ である。

要素の探索

削除と同じように x が見つかるまでt[i] を走査するので、実行時間はリスト t[i] の長さに比例する。

まとめると

ハッシュテーブルの性能はリスト t[i] の長さに左右される。つまり、すべてのデータをいい感じにハッシュテーブルの各要素に分散してくれるようなハッシュ関数を選択することが重要である。

たとえば、良いハッシュ関数のおかげでリスト t[i] の長さが1以下におさえられれば、追加・削除・探索をいずれも定数時間（O(1)）で実行できる。

f:id:dackdive:20200310015054p:plain:w320

反対に、最悪のケースとしてはすべてのデータでハッシュ値が衝突する（同じになってしまう）状況であり、この場合リスト t[i] の長さは n。

f:id:dackdive:20200310015103p:plain:w320

で、書籍の後半では効率の良いハッシュ関数と、それによってハッシュ値の衝突がうまく回避されることの証明が紹介されている。

5.1.1 乗算ハッシュ法

乗算ハッシュ法は、剰余算術と整数の割り算からハッシュ値を効率的に計算する方法。
ある整数 d について、大きさ 2^d であるハッシュテーブルを使う。dは次数と呼ばれる。

${\rm hash}(x) = ((z \cdot x) \ {\rm mod} \ 2^{w}) \ \ {\rm div}\ \ 2^{w-d}$

$z$ は奇数の集合からランダムに選択する。

わからなかったこと：式の意味は？どうして効率が良いの？

この定義式および補題5.1, 5.2 がハッシュテーブルの性能が良いことを証明する大事なポイントだったのだが、結局最後まで理解できなかった。

一応、理解できたところまでのメモを残しておく。

まず、書籍 p94 の前半部分を、図も含めて引用する。

f:id:dackdive:20200310020901p:plain

整数のビット数を w とするとき、整数の演算の結果は $2^{w}$ を法として合同になることを思い出すと、このハッシュ関数の効率がとても良いことがわかる（図 5.2 参照）。しかも、 $2^{w-d}$ による整数の割り算は、二進法で右側の $w - d$ ビットを落とせば計算できる

冒頭の

整数のビット数を w とするとき、整数の演算の結果は $2^{w}$ を法として合同になる

について。

w ビットの整数は、ある数を $2^{w}$ で割った余りと捉えることもできる。
また、整数の足し算、引き算、掛け算、割り算をしても、結果を w ビットに丸めたら $2^{w}$ で割った余りであることは同じ。
この一文が示しているのはこういう性質のことだと解釈した。ただ、続く

このハッシュ関数の効率がとても良いことがわかる

については、何を持って効率が良いと言っているのかわからなかった。
おそらくハッシュ関数としての効率が良い（ハッシュ値が衝突しにくい関数である）とは別のことを指していると思われる。それは補題5.1で示しているので。

しかも、 $2^{w-d}$ による整数の割り算は、二進法で右側の $w - d$ ビットを落とせば計算できる

ここはビット演算とかを調べると出てくるし、理解できた。

その他調べたこと

web上で乗算ハッシュ法について調べると、「乗算法」などのキーワードでいくつか記事が見つかる。（講義の資料っぽいのが多い）

多かったのが以下のような定義式

f:id:dackdive:20200310022014p:plain:w480

（ [アルゴリズムイントロダクション勉強会] ハッシュより引用）

この定義式では、元のデータ k に掛ける数が整数でなく実数となっている。が、やっていることはほぼ同じ。

その他の検索結果

5.2 LinearHashTable: 線形探索法

こちらは紹介程度に。
ハッシュテーブルの別の方法として、 t[i] をリストとするのではなく、直接要素を収める方法がある。これをオープンアドレス法と呼ぶ。
日本語版 Wikipedia だと開番地法として紹介されている。

この方法では、要素 x のハッシュ値 i を求めた後、素直に t[i] に要素を格納しようとする。
もしすでに他の要素が格納されている場合は、1つずらした t[(i + 1) mod t.length] を試す。それも無理ならさらに1つずらして...というのを格納できる場所が見つかるまで繰り返す。

f:id:dackdive:20200310023723p:plain:w320