効率的なデータ構造: Sets と Maps

Java におけるコードの最適化

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

空間/時間計算量を活用する

空間計算量と時間計算量について学びました。

この知識をどう活かせば、より効率的なコードを書けるのでしょうか？

適切なデータ構造を選ぶことです。

ユーザー管理システム

ユーザー管理システムを構築しています
特定のユーザー名について、ユーザーが存在するかを確認する必要があります
リストを使う場合の計算量: $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}

Sets

高速に検索できる、重複のない要素の集まりです
要素の追加、削除、存在確認は平均 $O(1)$ の計算量です

改善したユーザー管理システムの解決策:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}

Maps

辞書のように、単語（キー）-> 定義（値）という構造です
HashMap: 操作の平均計算量は $O(1)$ です

public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}

Hashcode メソッド

高速である理由 -> hashCode()
ArrayList の例では、検索するユーザー名のインデックスが分かりませんでした
hashcode() メソッドを使うと、オブジェクトを検索可能なインデックスに変換できます
例えば pavlos.2020 -> 35189

pavlos.2020 を hashcode で処理すると 35189 になる様子

要素のインデックス付け

HashMap と HashSet は内部的に配列を使っています
要素を追加する際:
- Java が要素に対して hashCode() を呼び出し、整数を取得します
- その整数に剰余演算を行い、バケット番号を求めます

例:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- that's our bucket!

衝突（コリジョン）

複数の要素が同じバケットに入ることがあります
- これを衝突（コリジョン）と呼びます
バケットには LinkedList を使います
そのため $O(1)$ は平均の計算量だと言えます

覚えておきたいポイント

データ構造の選択は、作業に適した道具を選ぶことに似ています。ハンマー（ArrayList）は釘には最適ですが、ネジには不向きです（Set の方が適している場合もあります）。

ハンマー、ドライバー、レンチ、ペンチが並んだ開いた工具箱

練習しましょう！

Java におけるコードの最適化