两个集合赋值，有没有时间复杂度较简单的解决方案

Question

大概代码如下，将一个集合值的某一属性赋值给另一个集合，大量数据情况下有没有好的解决办法。

public static void main(String[] args) {
        List<User> userList = new ArrayList<>();
        List<Order> orderList = new ArrayList<>();

        for (Order order : orderList) {
            for (User user : userList) {
                if (order.getUserId().equals(user.getId())) {
                    order.setUserPhone(user.getPhone());
                }
            }
        }
    }

    static class User {
        private String id;

        private String phone;

        public String getId() {
            return id;
        }

        public void setId(String id) {
            this.id = id;
        }

        public String getPhone() {
            return phone;
        }

        public void setPhone(String phone) {
            this.phone = phone;
        }
    }

    static class Order {
        private String userId;

        private String userPhone;

        public String getUserId() {
            return userId;
        }

        public void setUserId(String userId) {
            this.userId = userId;
        }

        public String getUserPhone() {
            return userPhone;
        }

        public void setUserPhone(String userPhone) {
            this.userPhone = userPhone;
        }
    }

Answer 1

耗时长是因为对userList执行顺序查找算法，时间复杂度是O(n)，总体时间复杂度是O(n*m)，如果数据量太大，可以把顺序查找换成hash查找，时间复杂度降低到O(1)，总体时间复杂度是O(m)。

用HashMap为userList建立索引即可。

    List<User> userList = new ArrayList<>();
    List<Order> orderList = new ArrayList<>();
    HashMap<String,User> index=new HashMap<>();

        for (User user : userList) {
            index.put(user.getId(),user);
        }
        
    for (Order order : orderList) {
        User user=index.getOrDefault(order.getUserId(),null);
        if (user!=null){
            order.setUserPhone(user.getPhone());
        }
    }
    
    

Answer 2

谢，楼上的解答。

// 1、暂不清楚filter的效率，如果有人了解，欢迎留言
userList.forEach(user -> {
    orderList.stream().filter(order -> order.getUserId().equals(user.getId())).findAny()
        .map(order -> {
            order.setUserPhone(user.getPhone());
            return order;
        });
});

// 2、Map
Map<String, User> index = userList.stream()
    .collect(Collectors.toMap(User::getId, Function.identity()));

orderList.forEach(order -> {
    User user = index.get(order.getUserId());
    if (user != null) {
        order.setUserPhone(user.getPhone());
    }
});

Answer 3

一般来说时间复杂度和空间复杂度是相违背的，如果想要时间复杂度低肯定要牺牲空间复杂度度。像楼上所说的将List转化为Map来减少查询的时间。
当然如果是多核机器，我们还可以考虑并行计算，例如利用Java8的ParallelStrean(基于ForkJoin模式)

public class Test {
    public static void main(String[] args) {
        List<User> userList = new ArrayList<>();
        List<Order> orderList = new ArrayList<>();
        Map<String, User> userMap = userList.parallelStream().collect(Collectors.toMap(User::getId, Function.identity()));
        orderList.parallelStream().forEach(it -> {
            if (userMap.containsKey(it.getUserId())){
                it.setUserPhone(userMap.get(it.getUserId()).getPhone());
            }
        });
    }

    static class User {
        private String id;

        private String phone;

        public String getId() {
            return id;
        }

        public void setId(String id) {
            this.id = id;
        }

        public String getPhone() {
            return phone;
        }

        public void setPhone(String phone) {
            this.phone = phone;
        }
    }

    static class Order {
        private String userId;

        private String userPhone;

        public String getUserId() {
            return userId;
        }

        public void setUserId(String userId) {
            this.userId = userId;
        }

        public String getUserPhone() {
            return userPhone;
        }

        public void setUserPhone(String userPhone) {
            this.userPhone = userPhone;
        }
    }
}

Answer 4

如果有重复user.id，map是否可以使用Map<String,List<User>>,或者有其他方案呢。ParallelStrean是否保证元素有序呢？

Answer 5

首先我们要清楚ArrayList底层是基于动态数组实现的，动态数组在添加元素的时候时间复杂度为O(N);
然后LinkedList底层是基于链表实现，链表在添加元素的时候时间复杂度为O(1)。
由上述问题可知一个集合值的某一属性赋值给另一个集合故涉及到集合元素的添加，有根据阿里规约可知集合添加元素的时候要使用迭代器迭代不能用增强for循环。所以上述问题要采用LinkedList合适，循环的时候要使用迭代器。