list.contains() 的性能问题

0 业务场景

• 公司有一个前人写的业务接口耗时非常严重，200w 的数据进行查询，浏览器等待 1h 都响应不出结果，因此测试给我提了一个 bug，需要对代码性能进行优化。我对代码逻辑进行排查后，排除 SQL 原因，发现是 list.contains() 出现了阻塞。由于不能贴公司源代码，我对相关业务进行了一个抽象，做了一个类似的 demo

• 现在有 3 个 list 集合，User 有两个字段：username、password

• List<User> all 存放的是所有人的数据

• List<User> friends 存放的是好友的数据

• List<User> contacts 存放的是相互联系的数据

• 需求：

1、从相互联系的数据过滤并收集好友的名称
2、从相互联系的数据过滤并收集非好友的名称

1 原始的代码逻辑

• 原始的，有性能问题的代码

 
// 好友
List<User> friend = contacts.stream()
    .filter(item -> friends.contains(item.getUsername()))
    .collect(Collectors.toList());

// 非好友
List<User> notFriend = contacts.stream()
    .filter(item -> !friends.contains(item.getUsername()))
    .collect(Collectors.toList());



以上代码逻辑在数据量较少时是没有问题的，但数据量在几十万的时候，代码出现了阻塞，一直出不来数据




2 原因分析


list.contains()方法的性能问题主要归因于其内部实现。在 Java 的 ArrayList 类中，contains() 方法通过遍历列表中的每个元素并使用 equals() 方法进行比较来检查元素是否存在。这种线性搜索的时间复杂度为 O(n)，其中 n 是列表中的元素数量。因此，当列表变得非常大时，性能会显著下降。


contains() 方法的源码如下：


 
int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}



3 解决方案


方案1：使用 HashSet 或 HashMap，如果需要频繁地检查元素是否存在，且不关心元素的顺序，可以使用 HashSet 的 contains() 方法具有近似 O(1) 的时间复杂度，因为它基于哈希表实现。如果还需要与每个元素相关联的额外数据，可以使用 HashMap


方案2：对列表进行排序并使用二分搜索，如果列表是有序的，可以使用Collections.binarySearch()方法进行二分搜索。这会将时间复杂度降低到O(logn)。注意要求列表始终保持排序状态，这可能会增加插入和删除操作的开销


方案3：使用并行处理，如果数据集非常大，并且有多个处理器核心可用，你可以考虑使用 stream 流进行并行处理。但是，并行处理并不总是能提高性能，特别是在 I/O 受限或数据集不适合内存的情况下


方案4：自定义数据结构，实现自己的数据结构来优化性能。例如，可以使用布隆过滤器来快速检查元素可能不存在，然后再使用更精确的数据结构进行确认


方案5：缓存结果，如果数据集在一段时间内不会改变，或者如果相同的查询被频繁地执行，可以考虑缓存查询结果来减少不必要的计算






现在我使用方案1中的 HashMap 进行演示，完整代码如下：


User 类：


 
import lombok.NoArgsConstructor;
import lombok.AllArgsConstructor;
import lombok.Data;
import java.util.Objects;

@Data
@NoArgsConstructor
@AllArgsConstructor
public class User {

    private String username;

    private String password;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(username, user.username) && Objects.equals(password, user.password);
    }

    @Override
    public int hashCode() {
        return Objects.hash(username, password);
    }
}





测试类


 
import cn.hutool.core.util.ObjectUtil;
import cn.hutool.core.util.RandomUtil;
import com.example.demo.entity.User;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 测试list.contains()性能问题
 */
public class ContainsDemo {

    public static void main(String[] args) {
        // 好友列表
        List<User> friendsData = friendsData();
        // 聊天记录列表
        List<User> contactsData = contactsData();
        // 所有人的数据
        List<User> allData = allData();

        // key-用户名 value-User
        Map<String, User> userMap = contactsData.stream().collect(Collectors.toMap(User::getUsername, o -> o, (v1, v2) -> v1));

        long t1 = System.currentTimeMillis();

        // 原逻辑-会产生性能问题
        // List<User> friend = allData.stream().filter(item -> friends.contains(item.getUsername())).collect(Collectors.toList());

        List<User> contactFriends = new ArrayList<>();
        friendsData.forEach(item -> {
            User user = userMap.get(item.getUsername());
            if (!ObjectUtil.isNull(user)) {
                contactFriends.add(new User(item.getUsername(), item.getPassword()));
            }
        });
        System.out.println("耗时：" + (System.currentTimeMillis() - t1) + " 毫秒");

        System.out.println("好友数：" + contactFriends.size());

        // 所有人的数据中，移出所有的friends，剩下的都是非friends
        allData.removeAll(contactFriends);
        List<User> notContactFriends = new ArrayList<>(allData);
        System.out.println("非好友数：" + notContactFriends.size());

    }


    /**
     * 模拟数据库查询结果 - 所有人列表数据
     */
    public static List<User> allData() {
        List<User> allData = new ArrayList<>();
        allData.addAll(initData());
        allData.addAll(initData());
        return allData;
    }

    /**
     * 模拟数据库查询结果 - 好友列表数据
     */
    public static List<User> friendsData() {
        return initData();
    }

    /**
     * 模拟数据库查询结果 - 聊天记录数据
     */
    public static List<User> contactsData() {
        return initData();
    }

    /**
     * 模拟80w数据
     */
    private static List<User> initData() {
        List<User> initList = new ArrayList<>();
        for (int i = 0; i < 800000; i++) {
            StringBuilder sb = new StringBuilder();
            char[] chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
            int length = 6;
            for (int j = 0; j < length; j++) {
                sb.append(chars[RandomUtil.randomInt(chars.length)]);
            }
            initList.add(new User(sb.toString(), sb.toString()));
        }
        return initList;
    }

}

/**
* 输出结果：
*   耗时：283 毫秒
*   好友数：39
*   非好友数：1600000
*/





list.contains() 的性能问题分析就到此为止啦，如有错误，欢迎指正。


创作不易，感谢阅读，若遇到问题，可以关注此微信公众号留言反馈，希望能够帮助到您。