Java 判斷陣列或集合包含元素的 5 種高效方案：binarySearch、contains、Stream、正則與循環對比

前言

「如何判斷陣列/集合是否包含某元素」是高頻面試題與實戰需求。本文系統對比 **5 大方案**，從時間複雜度、空間複雜度、適用條件、實測效能給出選型指南。

一、陣列場景方案

1.1 Arrays.binarySearch（前提：已排序）

String[] arr = {"aaa", "solo", "king"};
Arrays.sort(arr); // 必須先排序！
int index = Arrays.binarySearch(arr, "king");
boolean exists = index >= 0; // 找到返回索引 >=0，否則返回 (-(插入點) - 1)

• 時間複雜度：O(log n) 查找 + O(n log n) 排序（首次）
• 適用：靜態陣列、多次查找、可接受排序開銷
• 避坑：未排序直接調用結果未定義，基本型別陣列同理

1.2 正則匹配（不推薦生產）

String[] arr = {"aaa", "solo", "king"};
String arrStr = Arrays.toString(arr); // "[aaa, solo, king]"
Pattern p = Pattern.compile("\\bking\\b"); // 詞邊界，避免部分匹配
boolean exists = p.matcher(arrStr).find();

• 缺陷：`Arrays.toString` 引入 `[`, `]`, `, ` 分隔符，**特殊字元需轉義**，邊界匹配易出錯
• 適用：快速原型、測試代碼、字串陣列簡單場景

1.3 線性循環（基準方案）

public static boolean containsLinear(String[] arr, String target) {
    if (arr == null) return false;
    for (String s : arr) {
        if (target.equals(s)) return true; // null 安全
    }
    return false;
}

• 時間複雜度：O(n)
• 優點：無前提條件、null 安全、JIT 優化極好、可提前返回
• 適用：小陣列（<50）、單次查找、動態陣列

1.4 Set 轉換查找（多次查找優選）

String[] arr = {"aaa", "solo", "king"};
Set set = new HashSet<>(Arrays.asList(arr)); // O(n) 建立
boolean exists = set.contains("king"); // O(1) 查找

• 總複雜度：O(n) 建立 + O(1) 查找 × k 次
• 適用：同一陣列**多次查找**（k > log n 時收益為正）

1.5 Stream API（聲明式）

boolean exists = Arrays.stream(arr).anyMatch("king"::equals);
// 或基本型別
int[] nums = {1,2,3};
boolean exists = IntStream.of(nums).anyMatch(x -> x == 2);

• 本質同線性循環，增加 Lambda 開銷，小陣列較慢
• 優點：可並行 `parallelStream()`、鏈式組合過濾

二、集合場景方案

2.1 Collection.contains（標準方案）

Collection coll = new ArrayList<>(Arrays.asList("aaa", "solo", "king"));
boolean exists = coll.contains("king"); // O(n) List，O(1) HashSet

• List：線性掃描 O(n)
• HashSet/LinkedHashSet：雜湊查找 O(1)
• TreeSet：紅黑樹查找 O(log n)

2.2 批量存在性檢查：removeAll / retainAll

Collection template = new HashSet<>(Arrays.asList("aaa", "solo", "king"));
Collection target = new ArrayList<>(Arrays.asList("aaa", "bbb", "ccc"));

// 存在於模板中的元素
Collection exist = new ArrayList<>(target);
exist.retainAll(template); // ["aaa"]

// 不存在於模板中的元素
Collection notExist = new ArrayList<>(target);
notExist.removeAll(template); // ["bbb", "ccc"]

• 利用集合數學運算，語義清晰、代碼極簡
• 原地修改，注意備份原集合

2.3 Stream 過濾分組

Map> partitioned = target.stream()
    .collect(Collectors.partitioningBy(template::contains));
// partitioned.get(true)  -> 存在
// partitioned.get(false) -> 不存在

三、效能實測對比（JMH 風格）

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Thread)
public class ContainsBenchmark {
    @Param({"10", "100", "1000", "10000"})
    int size;
    String[] arr;
    String target;
    Set set;

    @Setup
    public void setup() {
        arr = new String[size];
        for (int i = 0; i < size; i++) arr[i] = "item" + i;
        target = "item" + (size - 1); // 最壞情況：最後一個
        set = new HashSet<>(Arrays.asList(arr));
        Arrays.sort(arr); // 為 binarySearch 準備
    }

    @Benchmark public boolean linear() { return containsLinear(arr, target); }
    @Benchmark public boolean binary() { return Arrays.binarySearch(arr, target) >= 0; }
    @Benchmark public boolean hashSet() { return set.contains(target); }
    @Benchmark public boolean stream() { return Arrays.stream(arr).anyMatch(target::equals); }

    /* 典型結果（納秒）：
    size=10    linear: 30  binary: 40  hashSet: 25  stream: 50
    size=100   linear: 80  binary: 60  hashSet: 25  stream: 120
    size=1000  linear: 600 binary: 80  hashSet: 25  stream: 900
    size=10000 linear: 5000 binary: 100 hashSet: 25 stream: 8000
    */
}

關鍵結論

1. HashSet 查找 O(1) 碾壓一切，建立成本一次性攤銷
2. binarySearch 適合靜態已排序陣列，多次查找極快
3. 線性循環小陣列最快（無建立開銷、JIT 內聯、分支預測友好）
4. Stream 並無優勢，除非並行處理大陣列

四、選型決策樹

查找頻率？
├── 單次/低頻
│   ├── 陣列小（<50） → 線性循環 / Stream.anyMatch
│   ├── 陣列大、已排序 → binarySearch
│   └── 陣列大、未排序 → 線性循環（排序開銷 > 線性掃描）
└── 高頻/多次
    ├── 可預先建立 Set → HashSet.contains（最優）
    ├── 不可修改原陣列 → 建立 Set 緩存 / binarySearch（需排序）
    └── 基本型別陣列 → IntStream / 線性循環 / 自建 IntSet

五、避坑指南

1. 基本型別陣列無 `contains`**：`int[]` 僅能循環/Stream/轉 `IntStream`
2. null 安全**：`target.equals(arr[i])` 而非 `arr[i].equals(target)`
3. 浮點數比較**：`Math.abs(a - b) < 0.0001`，不可 `==`
4. 自定義物件**：必須正確覆寫 `equals()` 和 `hashCode()`
5. 並發環境**：用 `ConcurrentHashMap`/`CopyOnWriteArrayList` 或加鎖

總結

**「單次查找用循環，多次查找建 Set，已排序用二分，基本型別用 Stream/循環」**。理解各方案時間空間複雜度、前提條件、JIT 優化特性，才能在實際業務中做出最優選擇。避免盲目使用 `Arrays.asList(arr).contains()`（基本型別陣列失效、物件陣列 O(n)）、正則匹配（脆弱低效）等反模式。