RubyのHashの秘密 その３ - ハッシュテーブルの理解

同姓同名のいない1億人の日本人の中から素早く「山田 太郎」を見つけ出して彼と話をしたい。各人の胸には名札が貼ってあるので、「山田 太郎」の名札の付いた人物を見つけ出せばいい。全国を行脚して片っ端に名札を確認していくという手もあるが、恐ろしく時間が掛かることは想像に難くない。最悪で1億人、平均で5000万人の名札の確認が必要となる。したがって事前に彼ら彼女らをなんらかのかたちに整列させるべきだと認識する。かと言って、こちらが持っている情報は彼ら彼女らの名前（姓と名）しかないから順位付けで整列というのは難しい。そこで姓（苗字）によるグループ化を思いつく。つまり各人の名札を「苗字関数」に通して苗字を得、その苗字のために割り当てられた区域に彼ら彼女らを住まわせるのだ。

def 苗字関数(name)
  name.split(/\s+/).first
end

name = "山田 太郎"

苗字関数(name) # => "山田"

日本人の苗字は30万種ほどらしいから1億人は30万個のグループに分けられ、各区域には平均330人が住むことになる。この場合「山田 太郎」に辿り着くには、まずは30万の区域の中から「山田」区を見つけ出し、次いで「山田」区の中から「山田 太郎」の名札を持った人物を総当りで探せばいい。「山田」区に辿り着くには平均15万回の区訪問が必要だが、区が見つかればあと平均165回で彼に出会える。

ところがよく調べてみると全国に「山田」姓の日本人は85万人もいることが分かった。これで彼に辿り着くには平均57万5000回(15万 + 42万5000)の照合が必要となった。一方で、「佐村河内」という姓は全国に40人しかいないそうで、その照合は平均15万回ほどだから姓によってそこに辿り着くまでの時間が相当異なることになる。これは安定的でない。ここに至って「苗字関数」の問題に気付く。この関数がグループを平均に分散しないのだ。

明日の予定を気にしながら良い方法がないか考えていたら、目の前にあるカレンダーが1年365日を7つの曜日で均等に分割していることに気付いた。年初からの経過日数を曜日の数で割った余り（剰余）を求めれば、すべての日にちは各曜日に紐付けられた0から6の数字の何れかになる。

def 剰余関数(day, base=7)
  day % base
end

剰余関数(5) # => 5
剰余関数(100) # => 2
剰余関数(224) # => 0

「剰余関数」により1年の365日は52個ずつの7つのグループに均等に分けられる。もし仮に人の名前をランダムなそれでいて一定である整数に置き換えられるなら、1億人の日本人も均等に分割できるかもしれない。つまり「山田 太郎」から作られる数字が常に一定であり、かつそれが「佐村河内 守」から作られる数字とは異なるようなランダムな数字、そんなものを生み出す関数があれば、どんな名前に対しても安定した結果を得られるに違いない。そんな関数を世間では「ハッシュ関数」と呼んでいる。

def ハッシュ関数(name)
  name.hash # String#hashを使う
end

ハッシュ関数("山田 太郎") # => 2948999586394291103
ハッシュ関数("山田 太郎") # => 2948999586394291103
ハッシュ関数("佐村河内 守") # => 3017522113704884285
ハッシュ関数("佐村河内 守") # => 3017522113704884285

苗字種数に倣って名前を30万のグループに分けるならこの値を30万で除した余を、求める「ハッシュ値」とすればいい。

def ハッシュ関数(name, base=30_0000)
  name.hash.abs % base
end

ハッシュ関数("山田 太郎") # => 270422
ハッシュ関数("山田 太郎") # => 270422
ハッシュ関数("佐村河内 守") # => 179742
ハッシュ関数("佐村河内 守") # => 179742

この「ハッシュ関数」から出力される数値は、0から30万の何れかだからこれを直線的に並べられた30万個の区域のインデックスとみなせばいい。つまり「山田 太郎」をこのデータ構造における先頭から270422番目の区域に住まわせ、「佐村河内 守」を179742番目の区域に住まわせる。こうすると「山田 太郎」に辿り着くには名前に「ハッシュ関数」を適用してハッシュ値を得、それが示すインデックスの区域に移動してそこに住んでいる330人の中から彼を見つけ出せばいい。これで彼を見つけるまでのコストは、「ハッシュ関数」を求めるコスト、対象区域のインデックスに移動するコスト、対象区域の330人にシーケンシャルにアクセスするコストとなる。このなかでは明らかに対象区域内でのシーケンシャルアクセスのコストが高い。対象インデックスへの移動コストは相対的に小さいからその数が増えても影響は小さいだろうから、この数つまり「ハッシュ関数」における剰余の基数を30万から300万に増やせば各区域内は33人になってその探索コストは改善する。言い換えれば各区域内の人数を最小に保てれば総コストは小さくなるということがわかる。

何れにしてもこれで探索対象が「山田 太郎」であろうが「佐村河内 守」であろうが「野田 江川富士一二三四五左衛門助太郎」であろうが一定のコストで目的に辿りつけるようになった。めでたしめでたし。

こんな理解であってる？

関連記事：

RubyのHashの秘密

RubyのHashの秘密 その２

参考記事：

ハッシュテーブル - Wikipedia ハッシュ関数 - Wikipedia

第3章 名前と名前表

Ruby Under a Microscope - Pat Shaughnessy

Rubyのハッシュテーブルの仕組みを徹底的に理解する - ザリガニが見ていた…。

ハッシュテーブル (アルゴリズムとデータ構造)

姓名分布&姓名ランキング 写録宝夢巣／名前・苗字・名字

名字検索No.1／名字由来net｜日本人の名字(苗字)98%以上を掲載!!