Zenn
⛳

Hash Table

2021/05/25に公開
algorithm
tech

Hash Tableのアイデアも、元を正せば、値を配列上に保存するというテクニックだ。この文章では、配列がもつ個別の保存空間をスロット、個別の保存空間の位置をインデックスと称している。配列は、15個のスロットをもち、インデックスにより各保存空間にアクセスする、というような具合だ。それでは行ってみよう。

計算機上で、動的に追加、削除されるような集合データを保存する方法としては、Direct Addressingという方法がある（そして、この保存に使うデータ構造はDirect Address Tableという）。keyを直接、テーブル内部でインデックスとして利用する。この方法では

  • insertするデータは全て異なるkeyを持つ
  • insertするデータ全体は、配列がもつスロット数より小さい

というような状況でなければ使えない。また、集合データのために割り当てたスロット数が多い一方、insertするデータ数が少ない場合は、未使用のスロットがたくさんできてしまい、memory spaceの無駄である。

そこでHash Tableというデータ構造が登場する。

Direct Address Tableでは、値kをインデックスkに保存していたが、Hash Tableでは値kをインデックスh(k)に保存する。h(k)はHash関数というものだ。

Hash Table

Hash tableでは、insertしたい値をHash関数h(k)の計算を経て、どのスロットに入れるか決める。Hash関数は入れるべき値のインデックスを弾き出してくれるわけだ。この仕組み上、スロット数をmとした場合、ハッシュ関数の出力は{0,1,…,m-1}の間におさまる必要がある。

「insertするデータ全体は、配列がもつスロット数より小さい」場合はどうしたら良いのだろうか。どのinsertデータかはわからないが、鳩の巣原理より少なくとも一つのスロットにinsertデータが2つ存在するという状況が発生する（Hash関数の結果のHash値の衝突であり、Key collisionという）ことがわかる。

Chaining

この解決策として、chainingがある。一つのスロットに複数のデータを持たなければならない場合には、linked listのデータ構造を使用する。新しいデータは順次、linked listの先頭に追加するという方法だ。詳細にいうと、Hash Tableの実体はデータを持つ場合はlinked listの先頭のポインタをもち、データがない場合はNIL。

また、Hash関数においても、insertするデータをスロットに対して満遍なく分配できるような計算機構が大事である(simple uniform hashing)。

以下2つのアイデアがある。

  • Division method
  • Multiplication method

Division method

Hash関数を以下の計算方法とするやりかた。

h(k) = k mod m

kはkeyの値で、mがHash Tableのスロット数。
例えばスロット数m = 12でkeyがk = 100であればh(k) = 4となる。

このmの値の選び方であるが、計算機の基数である２の累乗を選ぶのは悪手だ。それは、k mod mの計算結果が、単にkの最下位桁(他の桁とは無関係)となってしまう。同様に、10の累乗を選んでも、良い結果生えられない。

Multiplication method

Hash関数を以下の計算方法とするやりかた。

let A ∈ (0; 1) be constant,
h(k) = ⌊{k ∗ A} ∗ m⌋

{x}は、xの小数部分、[x]はxの整数部分を指す。
手順は以下。

  • 0より大きく、1未満の定数Aとkeyの値kを掛ける。
  • k*Aの小数部分とmと掛ける。
  • 整数部分を結果とする。

Knuthは、A = (√5 − 1)/2 = 0.618が最もよく計算可能ということを提案している。Division methodに比べると、mの値が結果に及ぼす影響が小さくなっている。

Open Addressing

https://en.wikipedia.org/wiki/Open_addressing

Chaining以外の、Hash値の衝突の回避方法にOpen addressingがある。配列がlinked listをもって数珠のようにデータを持つ必要がない方法だ。

このやり方でも要素をinsertするとき、ハッシュ関数でハッシュ値（=インデックス）を計算し、格納されるべきスロットを求めるが、もしすでにそのスロットが別のデータを格納済みであった場合、別のスロットの空き場所を探索して格納する。

「もしすでにそのスロットが別のデータを格納済みであった場合、別のスロットの空き場所を探索して格納する」

これをどうやるか。これまでHash関数はinsert対象の要素のkしかparameterとしてとっていなかったが、ここにもう一つ値を追加する。仮にiとしよう。ハッシュ関数はh(k,i)となる。
そして、Hashの衝突があったときには、すでに使用されていたそのスロットの位置から数えてi番目に値を格納することとする。つまり最初はi=0で計算し、使用済みであれば1からm-1（mはHash tableのスロット数）を順次入れていき、空きスロットに到達するまでiの値を変えていき繰り返すということを行う。このときの探索したスロットの位置は、1つ以上の数値の羅列になるが、これをprobe sequenceとかprobing sequenceといい、Hash Tableへのこのような問い合わせ方法をprobeという。

insertのときは上のやり方でやっていけばよいし、searchも空きスロットに到達するまでHash関数の結果からスロットをしらべて行けば良いよう感じがするが、deleteの場合がやや複雑そうだ。それは削除のやり方次第ではHash Tableがうまく機能しなくなるからだ。

deleteの場合、対象のデータが見つかったあとそのスロットを「Empty」としてしまうと、searchの時にそのスロットで探索が終わってしまう。これが不都合なのは、そのスロットより先にデータが入れられていた場合には実際にHash tableに値があるのに、探索が打ち切られてしまう。結果、データが見つからなかったという誤った状況になる。これを回避するためHash Tableのスロットから要素を削除した場合は、「Empty」ではなく「Deleted」という印をつける必要がある。

「Deleted」があることでinsertとsearchをちょっと変更する必要がある。

Hash Tableは同じキーが存在してはいけないので、insertの場合、まずsearchをしてそのkeyがすでにスロットにあるかどうか調べる。Hashの衝突は異なるkeyが同じ値になってしまう場合のことであり、searchをしてそのkeyがすでにスロットにあるかとは別の問題である。

searchが成功 = そのkeyを持つスロットがあるとする。

  • searchが成功した場合、Hash Tableはすでにそのkeyを持つので、insertはできない。(insert失敗)
  • searchが失敗した場合かつ「Deleted」がHash Tableにある場合、「Deleted」のスロットにkeyを入れる。(insert成功)
  • searchが失敗した場合かつ「Deleted」がHash Tableにない場合、searchは「Empty」のスロットで止まってるはずなので、そこにkeyを入れる。(insert成功)
  • searchが失敗した場合かつ「Deleted」も「Empty」もHash Tableにない場合、Hash Tableがfullになっており、insertは失敗(insert失敗)

さてこの方法では、Chainingと異なり、一度のinsert, delete, searchでHash Tableのスロットを複数回問い合わせる必要がある。さきほどにこの問い合わせの数値、つまりスロットのインデックスの羅列をprobing sequenceと言ったが、このprobeing seqeunceをどのように作るかが問題となる。

戦略が３つある。

  • Linear probing
  • Quadratic probing
  • Double hashing

繰り返すがHash関数は、格納したい要素をどのスロットに入れるべきか計算するものなので、3つともHash関数の数式で違いを表す。

Linear probing

最も単純な実装で済ませるならこの戦略となる。

h(k, i) = (h_1(k) + i) mod m (i ∈ 0..(m − 1))

h_1というHash関数自体は、値域[0,m-1]の何らかの関数。
スロットが埋まってたら、その隣のスロットを調べ...というのを繰り返す。問題点は、uniform hashingを目指すなら、m!通りのprobing sequencesが必要なのだがこの実装では、m通りのprobing sequenceしか作れない。2つのkeyがあって、h(k1, 0) = h(k2, 0)であれば、そのprobing sequenceは同一である。またPrimary clusteringという問題も抱えている。

Quadratic probing

h_1というHash関数自体は、値域[0,m-1]の何らかの関数。c1とc2は実数で、c2は0ではないとする。

uniform hashingを目指すなら、m!通りのprobing sequencesが必要なのだが、この実装でも、m通りのprobing sequenceしか作れない。2つのkeyがあって、h(k1, 0) = h(k2, 0)であれば、そのprobing sequenceは同一である。こちらはSecondary clusteringという問題を抱えている。

Primary clusteringは、そのHash関数の仕組み上、隣接するスロットが埋まり続けてしまうというもの。Secondary clusteringでは、隣接するスロット同士が埋まってはないものの、i=0の場合のスロットの初期位置からprobing sequenceは分散されこそするけれども、埋まる場所自体は同じであるために起こる。

Secondary clustering occurs when the probing scheme spreads the keys away from the initial position, but is still the same for each key that hashed to the same bucket. It happens with quadratic probing or when the secondary hash function in double hashing is implemented poorly and only depends on the hashed position not on the whole key like it should. Keys that hash to adjacent positions are spread out, so that no primary clustering occurs. But all the keys that hash to the same position in the hash table stay in the same probing sequence, which makes them pile up a little. Secondary clustering, opposed to primary clustering, is very mild and scales with O(1/(1-a)-a-log(1-a)), which is not much worse than the O(1/(1-a)) of double hashing but a significant improvement over the O(1+1/(1-a)^2) of primary clustering.

Double hashing

Hash関数を2つ使う方法。


別の記事でかく。

load factor

α = Hash tableの要素数/スロット数

で計算する。20個のデータを10個のスロットをもつHash Tableに入れると、load factorは20/10 = 2となる。

この数値は、Hash Tableを電車とした場合の乗車率のようなもので、プログラミング言語でHashTableを使ってる時に計算されて、load factorが大きくなりすぎるとrehash（スロット数を内部で割り当て直したりする）が起こる。

参考

Discussion