List的contains导致cpu飙高

BUG背景

订单客户生产令号去重汇总
在开发过程中用到了List，随着业务需求的变化，需要去重。当时直接就在代码中判断是否包含 list.contains("a") ，包含则不添加

      // 获取所有订单
      List<String> allOrder = getAllOrders();
// 生产令号去重后数据
      List<String> matchList = new ArrayList<>();
      for (String idno:allIdnos){
          // ...省略。isMatch 
          // 匹配列表不包含用户id，才添加进匹配列表中
          if ( !matchList.contains(idno)){
              matchList.add(idno);
          } 
      }

问题解析

由于getAllOrders获取到的订单数据量过于庞大，每添加一个都要做一便contains 操作的时候，其实他相当于做了一次遍历。时间复杂度是O（n）。那么要查找每个数据是否包含的话，就需要n*n次操作。最终导致CPU100%

改进

改用set，set查找某一个元素的复杂度为O(1)

// 获取所有订单
List<String> allOrder = getAllOrders();
// 生产令号去重后数据
Set<String> matchSet = new HashSet<>();
for (String idno:allIdnos){
    if ( !matchSet.contains(idno)){
        matchSet.add(idno);
    }
}