Zenn
💭

[Ruby] ハッシュの取得はなぜ配列より速い？

2024/08/25に公開
Ruby
ハッシュ
tech

プロを目指すためのRuby入門を読んで、ハッシュが配列に比べて値を高速に取り出せる理由が曖昧だったので調べました。

ハッシュとは？

ハッシュは、キーと値のペアを格納するデータ構造です。Rubyでは、以下のように使用します：

my_hash = { "名前" => "田中太郎", "年齢" => 30, "職業" => "エンジニア" }
puts my_hash["名前"]  # 出力: 田中太郎

なぜ高速に取り出せる？

ハッシュが高速である理由を、本棚を使って説明してみます。

本棚の例

あなたは図書館の司書で、100万冊の本を管理しているとします。

  1. 普通の本棚（配列のイメージ）:

    • 本がタイトル順に並んでいる
    • 「Ruby入門」という本を探すには、A from Zまで順に探す必要がある
    • 最悪の場合、100万冊すべてを確認することになる

  2. 魔法の本棚（ハッシュのイメージ）:

    • 本のタイトルを言うと、その本がある棚番号が即座に分かる魔法の装置がある
    • 「Ruby入門」と言えば、すぐに「42番の棚」と教えてくれる
    • 42番の棚に行けば、すぐに本が見つかる

ハッシュは、この「魔法の本棚」のような仕組みを使っています。

ハッシュの仕組み

  1. ハッシュ関数（魔法の装置）:

    • キー（本のタイトル）を入力すると、数値（棚番号）を出力する
    • 例: "Ruby入門" → 42

  2. ハッシュテーブル（本棚）:

    • ハッシュ関数が出力した数値（42）の位置に値を格納する
    • 例: 42番目の位置に "田中太郎" を格納

  3. 値の取り出し:

    • キーに対してハッシュ関数を適用し、格納位置を特定
    • その位置から直接値を取り出す

この方法により、データ量が増えても、基本的に同じ速度で値を取り出せます。

ハッシュ関数の例

ハッシュ関数は、キーを入力として受け取り、一定の範囲内の数値（ハッシュ値）を出力します。以下に、簡単なハッシュ関数の例を示します：

  1. 文字列の長さを利用する方法：

    def simple_hash(key, table_size)
  key.length % table_size
end

puts simple_hash("Ruby", 100)  # 出力: 4
puts simple_hash("Python", 100)  # 出力: 6

  2. 文字のASCIIコードを利用する方法：

    def ascii_hash(key, table_size)
  hash = 0
  key.each_char { |char| hash += char.ord }
  hash % table_size
end

puts ascii_hash("Ruby", 100)  # 出力: 50
puts ascii_hash("Python", 100)  # 出力: 34

  3. より複雑な例（FNV-1aハッシュ関数の簡略版）：

    def fnv1a_hash(key, table_size)
  hash = 2166136261
  key.each_char do |char|
    hash = hash ^ char.ord
    hash = hash * 16777619
  end
  hash % table_size
end

puts fnv1a_hash("Ruby", 100)  # 出力: 88
puts fnv1a_hash("Python", 100)  # 出力: 62

実際のハッシュ関数は、これらの例よりもさらに複雑で、衝突を最小限に抑えるように設計されています。Rubyの内部実装では、MurmurHashという高性能なハッシュ関数が使用されています。

衝突問題

ただし、異なるキーが同じ数値（棚番号）を生成することがあります。これを「衝突」と呼びます。

例:

  • "Ruby入門" → 42
  • "Python入門" → 42 （衝突！）

この問題を解決するために、主に二つの方法があります：

  1. チェイン法:

    • 同じ棚に複数の本を置く（リストをつなげる）
    • 42番の棚に "Ruby入門" と "Python入門" の両方を置く

  2. オープンアドレス法:

    • 衝突が起きたら、次の空いている棚を探す
    • 42番が埋まっていたら、43番、44番...と探していく

チェイン法のメリットとデメリット

メリット:

  • 実装が比較的簡単
  • ハッシュテーブルの拡張が容易（新しい本棚を追加するだけ）
  • 負荷率（使用されている棚の割合）が高くても性能が安定

デメリット:

  • 各棚にリストを保持するため、追加のメモリが必要
  • 最悪の場合、一つの棚に多くの本が集中すると検索が遅くなる

オープンアドレス法のメリットとデメリット

メリット:

  • メモリ効率が良い（追加のデータ構造が不要）
  • キャッシュの局所性が高い（近い棚を探すため）
  • 小規模なデータセットで特に効率的

デメリット:

  • 実装がやや複雑
  • 負荷率が高くなると性能が急激に低下する
  • 削除操作が難しい（削除跡を特別に扱う必要がある）

Rubyのハッシュ実装

Rubyは、これらの方法を組み合わせた実装を使用しています：

  1. 小規模なハッシュ（本が少ない場合）:

    • オープンアドレス法を使用
    • メモリ効率が良く、高速

  2. 大規模なハッシュ（本が多い場合）:

    • チェイン法に切り替え
    • 衝突が増えても性能が維持される

また、前述したようにハッシュ関数は独自のものを使用しています。これは、MurmurHash3という高性能なハッシュ関数を簡略化したものです。

これらに加えて、様々な最適化手法を用いてRubyのハッシュは実装されています。

※今回は割愛

まとめ

ハッシュが高速な理由は、「魔法の本棚」のような仕組みにあります：

  1. キー（本のタイトル）から直接格納場所（棚番号）が分かる
  2. その場所から一発で値（本）を取り出せる
  3. データ量が増えても、基本的に同じ速度で取り出せる

Rubyは、この仕組みを更に最適化し、チェイン法とオープンアドレス法のメリットを組み合わせることで、様々な状況で効率よく動作するハッシュを提供しています。

その他の最適化手法についても、今後勉強していきたいです。

参考文献

  1. プロを目指す人のためのRuby入門[改訂2版] 言語仕様からテスト駆動開発・デバッグ技法まで (Software Design plus), https://www.amazon.co.jp/dp/4297124378/ref=sspa_dk_detail_0?psc=1&pd_rd_i=4297124378&pd_rd_w=X35Eu&content-id=amzn1.sym.f293be60-50b7-49bc-95e8-931faf86ed1e&pf_rd_p=f293be60-50b7-49bc-95e8-931faf86ed1e&pf_rd_r=HMJ4BAFG7NSE2C3EN3R0&pd_rd_wg=3B8Ig&pd_rd_r=e64c0966-bc46-4fd1-8ad4-6d96ef569aaf&s=books&sp_csd=d2lkZ2V0TmFtZT1zcF9kZXRhaWw

  2. 問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書), https://www.amazon.co.jp/問題解決力を鍛える！アルゴリズムとデータ構造-ＫＳ情報科学専門書-大槻兼資-ebook/dp/B08PV83L3N/ref=sr_1_3?__mk_ja_JP=カタカナ&crid=1LHWGQ9ER46SV&dib=eyJ2IjoiMSJ9.vIHL5eHLjL6Agkp0skqmT2wt3eOur8Bu3C-PDagBqyLARgMtfT_MdR3wcukdZR5zCoa8IQw54Dh8GKfWb3xfXgDz6EY2EDcYihil3d93KPs3g49cybovqEuvbjYUNKHwsDQdKDArbVRMHgNm5DOlvbVqnI7WzoVGojzTWAQKMHUURK6WFMvtmMQtXaRXlSTYG9l_puIh7wtaF6uqr0fjblK6Tuil9wlxs0nYdn0ScBc.LhvoF5Ov32VRRfty2TVgsrrESgDCQbCMrzGNWrYq5sE&dib_tag=se&keywords=データ構造&qid=1724576094&s=books&sprefix=データ構造%2Cstripbooks%2C240&sr=1-3

  3. Rubyのソースコード, https://github.com/ruby/ruby/blob/master/hash.c

Discussion