Java | ソートアルゴリズムを体系的に学ぶ

Java Java
スポンサーリンク

Javaで学ぶ「アルゴリズムとデータ構造」（後半）

前半では、配列・ArrayList・LinkedList・スタック・キューといった 「アルゴリズムの土台になる基本データ構造」を整理しました。 後半では、より本格的な 木構造（ツリー）・ハッシュテーブル・グラフ を扱い、 それらの上で動く 探索アルゴリズム（DFS/BFS）・計算量の深掘り・安全なデータ構造設計 を 初心者向けにかみ砕いて解説していきます。

アルゴリズムとデータ構造は、単なる知識ではなく「設計力」そのものです。 ここからが、読者が“本当に使えるアルゴリズム力”を身につけるための本番です。

木構造（ツリー）を理解する：階層を表す最強のデータ構造

ツリーは「親と子の関係を持つ階層構造」です。 フォルダ階層、組織図、メニュー構造、JSON、XML、DOMなど、 実務で階層を扱う場面はほぼすべてツリーで表現できます。

ツリーの基本構造

Javaで最もシンプルなツリーは次のように表現できます。

class Node {
    String name;
    Node parent;
    List<Node> children = new ArrayList<>();

    Node(String name) {
        this.name = name;
    }

    void addChild(Node child) {
        child.parent = this;
        children.add(child);
    }
}
Java

この構造を使うと、フォルダ階層のようなツリーを簡単に作れます。

Node root = new Node("root");
Node docs = new Node("docs");
Node images = new Node("images");
root.addChild(docs);
root.addChild(images);
Java

深掘り：ツリーが強力な理由

ツリーは「階層を持つデータ」を自然に表現できるだけでなく、 探索アルゴリズム（DFS/BFS）と組み合わせることで 検索・集計・フィルタリング・権限チェックなどを効率的に行えます。

ツリーを理解すると、 データ構造の世界が一気に立体的に見えるようになります。

ハッシュテーブル（HashMap）：高速検索の王様

ハッシュテーブルは「キーから値を高速に取り出す」ためのデータ構造です。 Javaでは HashMap が代表的です。

HashMap の基本

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 90);
scores.put("Bob", 80);

System.out.println(scores.get("Alice")); // 90
Java

ハッシュテーブルの強さは、 検索・追加・削除が平均 O(1) という圧倒的な速さにあります。

深掘り：なぜ O(1) で高速なのか

キーを「ハッシュ関数」で数値に変換し、 その数値を配列のインデックスとして使うことで 直接アクセスできるからです。

つまり、配列の速さと「キーで検索できる便利さ」を 両立した構造がハッシュテーブルです。

セキュリティの観点

ハッシュテーブルは高速ですが、 攻撃者が「ハッシュ衝突を大量に発生させるキー」を送ると 最悪 O(n) に劣化し、DoS攻撃の入口になります。

そのため、Javaではハッシュ関数が強化されており、 攻撃者が衝突を意図的に起こしにくい設計になっています。

グラフ構造：複雑な関係を表すデータ構造

グラフは「ノード同士が自由に繋がる」構造です。 SNSの友達関係、道路ネットワーク、依存関係、ルーティングなど、 複雑な関係を扱う場面で必ず登場します。

グラフの基本表現（隣接リスト）

Map<String, List<String>> graph = new HashMap<>();
graph.put("A", List.of("B", "C"));
graph.put("B", List.of("C"));
graph.put("C", List.of("A"));
Java

このように、 「ノード → つながっているノード一覧」 という形で表現します。

DFS（深さ優先探索）と BFS（幅優先探索）

ツリーやグラフを扱うときに必ず登場するのが DFS と BFS です。

DFS（深さ優先探索）

「深く潜っていく」探索。 再帰と相性が良い。

public static void dfs(Node node) {
    System.out.println(node.name);
    for (Node child : node.children) {
        dfs(child);
    }
}
Java

BFS（幅優先探索）

「横に広がっていく」探索。 キューを使う。

public static void bfs(Node root) {
    Queue<Node> queue = new ArrayDeque<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.name);
        for (Node child : node.children) {
            queue.add(child);
        }
    }
}
Java

深掘り：DFS と BFS の違い

DFS は「深さ」を重視し、 BFS は「階層」を重視します。

例えば、 最短経路を求めたいなら BFS、 すべてのパスを探索したいなら DFS、 というように使い分けます。

計算量（Big-O notation）を実務レベルで理解する

アルゴリズムを語るうえで欠かせないのが「計算量」です。 計算量は「データが増えたとき、処理時間がどう増えるか」を表します。

よく使う計算量

O(1) ハッシュテーブルの検索など。データ量に関係なく一定時間。

O(n) 配列の線形探索など。データ量に比例して増える。

O(n log n) 高速ソート（クイックソート・マージソート）など。実務で最も重要。

O(n²) バブルソートなど。データ量が増えると急激に遅くなる。

O(2ⁿ) フィボナッチの素朴な再帰など。実務では絶対に避けるべき。

深掘り：計算量は「増え方の感覚」

例えば、 データが 10 倍になったとき、処理時間がどう変わるかを想像できると アルゴリズム選択が一気に楽になります。

O(n) → 10倍 O(n log n) → 約12倍 O(n²) → 100倍 O(2ⁿ) → 爆発的に増える

この「増え方の感覚」が、 アルゴリズムを選ぶときの判断力になります。

セキュリティ・パフォーマンスの観点から見た危険なデータ構造の使い方

データ構造は便利ですが、 使い方を誤るとセキュリティリスクになります。

危険な例

外部入力をそのまま再帰 DFS に渡す 極端に深いツリーで StackOverflow ハッシュ衝突を大量に起こすキーで HashMap を攻撃 巨大リストをソートしてサーバーに負荷をかける LinkedList を大量のランダムアクセスで使い、性能が劣化する

深掘り：安全なデータ構造設計

深さ・サイズの上限を設ける 再帰ではなく非再帰 DFS を使う ハッシュテーブルのキーを検証する 計算量が悪化する可能性を常に監視する

アルゴリズムとデータ構造は、 「安全に使う」という視点が欠かせません。

後半のまとめ

後半では、アルゴリズムとデータ構造を実務レベルで使いこなすために

木構造（ツリー） ハッシュテーブル（HashMap） グラフ構造 DFS と BFS 計算量（O(1), O(n), O(n log n), O(n²), O(2ⁿ）） セキュリティ・パフォーマンスの観点

を体系的に整理しました。

アルゴリズムとデータ構造を理解すると、 「どの構造の上で、どの手順を使うべきか」を 自信を持って判断できるようになります。

前へ
12
スポンサーリンク
タイトルとURLをコピーしました