【Ruby入門】開発者が押さえておきたい主要データ構造の特徴と使い方

データ構造とは？

データ構造とは、データを整理し、効率よくアクセスするための具体的な方法のことです。

代表的な例としては以下のようなものがあります。

• 配列（Array）
• 二分木（Binary Tree）
• ハッシュ（Hash）

データ構造ごとに得意な処理は異なります。たとえば、ハッシュは辞書（単語と意味）や電話帳（名前と電話番号）のように「キーと値」のペアを扱うデータの保存に最適です。

どのようなデータ構造が存在するのか、そしてそれぞれの特性を理解することは、Ruby開発者としてのレベルアップに直結します。

本記事では、その知識をわかりやすく解説していきます！

配列（Array）を理解する

配列は、プログラミングを学び始めたときに最初に出会うデータ構造でしょう。

配列は連続したメモリ領域を使用し、オブジェクトを隙間なく順番に格納します。C言語のような低レベル言語と異なり、Rubyではメモリ管理、配列サイズの自動拡張、要素削除時の再配置といった面倒な処理はすべて言語側が担ってくれます。

主な用途：

• より高度なデータ構造の基盤として
• ループ処理の結果を集めるために
• アイテムのコレクションとして

文字列を1文字ずつの配列に分解する split や chars メソッドなど、配列はRubyコードのあらゆる場所で登場します。

使用例：

out = []

10.times { |i| out << i }

out
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

次の表は、配列サイズが大きくなるにつれて各操作の性能がどう変化するかを示したものです。計算量の記法に馴染みがない方は、まずビッグオー記法について学んでおくと理解が深まります。

配列の計算量：

操作	計算量
push（末尾に追加）	O(1)
pop（末尾から削除）	O(1)
access（アクセス）	O(1)
find（検索）	O(n)
delete（削除）	O(n)

なぜこの情報が役立つのでしょうか？

それは、配列のパフォーマンス特性を把握できるからです。巨大な配列に対して find を繰り返すと処理は遅くなりますが、インデックスがわかっていれば O(1) の計算量で高速にアクセスできます。

データ構造を選ぶ際の基準：

1. パフォーマンス特性 => データに対して何をするのか？データセットはどのくらい大きいのか？
2. データの形状 => どんな種類のデータを扱っているのか？より適したデータ構造に合わせてデータを再整理できないか？

ハッシュ（Hash）データ構造

国コードと国名のマッピングが必要なときはありませんか？あるいは、単純に項目の数を数えたいこともあるでしょう。

そんなときこそ、ハッシュが活躍します！

ハッシュはすべての値がキーに対応し、キーには文字列・整数・シンボルなど何でも使えるデータ構造です。

仕組みはどうなっているのか？

ハッシュは、キーを数値に変換し（Rubyでは hash メソッドが使われます）、その数値をインデックスとして利用します。ただし、Rubyでハッシュを使うためにこの内部実装を理解する必要はありません。

主な用途：

• 文字列内の各文字の出現回数を数える
• 単語と定義、名前と電話番号などのマッピング
• 配列内の重複の検出

使用例：

"aaabcd"
  .each_char
  .with_object(Hash.new(0)) { |ch, hash| hash[ch] += 1 }

# {"a"=>3, "b"=>1, "c"=>1, "d"=>1}

計算量：

操作	計算量
store（保存）	O(1)
access（アクセス）	O(1)
delete（削除）	O(1)
find（値の検索）	O(n)

保存・削除・アクセスが常に O(1) で行えるため、ハッシュはパフォーマンスの観点から最も有用なデータ構造のひとつです。なお、ハッシュにおける「find」とは、特定の「値」を探すことを意味します。

スタック（Stack）

スタックは皿の積み重ねのようなものです。皿を次々と上に重ねていき、取り出せるのは常に一番上の皿だけ、というイメージです。

一見地味に思えますが、実はとても便利な性質なんです！

主な用途：

• 再帰メソッドを通常のループに置き換える
• 残りの作業を管理する（最新の作業が常に先頭に来るように）
• 配列を逆順にする

使用例：

stack = [1,2,3,4,5]

(1..stack.size).map { stack.pop }

# [5, 4, 3, 2, 1]

もちろん、代わりに reverse メソッドを使うこともできます。ここではスタックの特性を示すためのサンプルとして紹介しました。

計算量：

操作	計算量
push	O(1)
pop	O(1)
find	---
access	---

スタック（およびキュー）には push と pop、つまり挿入と削除の2つの操作しかない点に注目してください。スタックの中を検索すること自体は可能ですが、実際に行われることはまれです。

二分木（Binary Tree）の使い方

ほとんどのRuby開発者は、二分木という言葉を聞いたことはあっても、実際に使ったことはないかもしれません。

なぜでしょうか？

第一に、Rubyには組み込みの二分木実装が存在しないためです。第二に、毎日使う配列やハッシュと違い、日常的なプログラミング課題において二分木が役立つ場面はそれほど多くありません。

しかし、二分木は非常に興味深いデータ構造です。

実際、Trie（次のセクションで解説）をはじめ、B木（データベースで使われる多分木）やヒープなど、多くの派生形が存在します。

主な用途：

• データ圧縮
• ルーティングテーブル
• 抽象構文木（AST）

使用例：

# https://github.com/jamesconant/bstree

require 'bstree'

root = Bstree::Node.new(5)

root.insert(2)
root.insert(7)

root.search(3)
# nil

計算量：

操作	計算量
insert（挿入）	O(log n)
delete（削除）	O(log n)
find（検索）	O(log n)
access（アクセス）	---

バランスの取れた二分木とは、すべてのノードが2つの子を持ち、すべての葉が同じレベルにある状態を指します。木のバランスが崩れると、パフォーマンスは O(n) まで低下してしまいます。

自己平衡二分木（赤黒木やAVL木など）では、すべての操作が木の高さ（レベル）に比例した時間で完了します。

また、アクセス時間が表中にないのは、ノードにアクセスするにはまず検索が必要だからです。その場合、アクセスも O(log n) となります。ただし、特定のノードへの参照を変数として保持しておけば、アクセスは O(1) で行えます。

Trie（トライ木）データ構造

Trieは、木構造の一種である特殊なデータ構造です。

単語を扱うのに非常に便利で、「特定の接頭辞（プレフィックス）で始まる単語の検索」や「完全一致の単語検索」を高速に行えます。

主な用途：

• ワードゲーム
• スペルチェッカー
• 自動補完候補の表示

使用例：

# https://github.com/gonzedge/rambling-trie

require 'rambling-trie'

trie = Rambling::Trie.create('words.txt')

trie.include?('chocolate')
# true
trie.include?('salmon')
# true

計算量：

操作	計算量
add（追加）	O(k)
include?	O(k)
words	O(k)

この表では、k は入力文字列のサイズを、n はデータ構造自体のサイズを表しています。たとえば apple という単語の場合、k は5です。

まとめ

今回は、代表的なデータ構造とそれぞれの主な用途・特性、そしてRubyでの使い方について学びました。

この新しい知識を実践に活かせば、問題をこれまで以上に速く解決できるようになるでしょう！