Java 中一个 size 为 10 万的 List<User>,怎么查找 name="张三"的 User 最快？

[aoizz]

需求大概就是这样，我目前使用的是

Optional<User> first = userList.stream().filter(e->e.getName().equals("张三")).findFirst();
if (first.isPresent()){
   User user = first.get();
}

但我觉得这种方式效率有点低，请问有别的更快的方式吗？

[justicelove]

最好是插入的时候就通过一个固定算法来计算下标, 查找时同样 通过固定算法来获取对应下标, 这么做其实有点像自己实现一个类似 map 的快速查找结构

[vindac]

直接 fori,找到第一个返回

[timethinker]

在不进行预处理的情况下，你可以简单的改为并行流然后查找，users.stream().parallel().filter...，或者 users. parallelStream().filter...

[aoizz]

@justicelove #1 这个目前来看有点不现实，谢谢大佬
@vindac #2 直接 fori 是不是和我现在的做法差不多啊。
@qwe520liao #3 我研究一下，谢谢大佬

[amon]

转成 Map，
userList.stream().collect(Collectors.groupingBy(User::getName));

[qiuhang]

这种没啥好办法吧，要想查找快，那你在组织数据的时候就得多下功夫。比如按照字典顺序排列，然后用二分查找或者干脆存成查找树。你这无序的 list，就是天王老子来了它复杂度也得是 O(n)。

[InkAndBanner]

改成并行流会快，但是如果数据很少 并行流会慢

[gabon]

这数据总归不是内存里生成的吧，不能查的时候只查这一个吗

[yejinmo]

// 非预处理
userList.FirstOrDefault(q => q.Name == name);
// 预处理
var userMap = userList.ToDictionary(q => q.Name, q => q);
userMap.TryGetValue(name, out var user);

[Edcwsyh]

@justicelove 这好像就是哈希方法吧....但 Map 不是哈希啊, HashMap 才是

[justicelove]

@Edcwsyh #10 其实 Tree Map 也是类似的思路

[aoizz]

@gabon #8 这是从数据库根据 id 拿到的，因为外面还有一个循环，所以不能直接查数据库。这个需求我简化了。
真正的大概是这样的，为了避免总是查询数据库，我将 CustomerList 里面的 userId 都拿了出来，然后根据 userIdList，查找所有符合要求的 User,然后再有下面的操作
List<String> userIds = customerList.stream().map(Customer::getUserId).collect(Collectors.toList());

List<User> userList = userService.getByIds(userIds);

customerList.forEach(c->{

Optional<User> first = userList.stream().filter(e->e.getName().equals(c.getName)).findFirst();

if (first.isPresent()){
User user = first.get();
//别的操作
}


})

[aitaii]

空间换时间

[Leviathann]

单次查询就这样啊
多线程分段查也许能快点，但是 10w 这个量级也不好说
多次查就转 map

[securityCoding]

解决问题的思路明显是错的

[timethinker]

@aoizz 按照这个思路，很难想象你一次性要获取 10W 的用户（根据 getByIds，使用 SQL IN 语句？），优化的核心思路在于时间跟空间的平衡点，数据查找尽量使用 SQL 通过数据库来筛选数据，充分利用好数据库的索引功能，避免一次性获取大量数据，然后只使用里面的少量数据。

不过最重要的还是看数据量与看场景，是 OLTP 还是 OLAP，前者尽量保证短时间内完成操作，后者更多的是通过提前创建派生数据来提高查找速度（以空间换时间）。

[bxb100]

@aoizz #12 都放到 List 里面了, 为啥不直接生成 Map

[3dwelcome]

我说一下 C++优化，有两点。

1. 可以用 early skip，比如"张三"内存里 utf8 是 6 个字节，那么 List 里所有 Name 不是 6 个字节的，都可以快速跳过，而不用深度判断。

2. 给 List 里每一条记录打 tag, 比如"张三"的 UTF8 是 E5 BC A0 E4 B8 89，按照 ASCII 排序整理一下就是 045889ABBCEE，去掉重复后的 tag 就是[0][4][5][8][9][A][B][C][E]。然后对比别的记录有没有这几个 TAG，如果没有就可以快速跳过，而不用对比。

[3dwelcome]

@bxb100 都知道用 Map 可以解决，但楼主问的是 List 。

[Rwing]

我来跑个题，各位不考虑一下 C# 吗，🙂
var first = userList.First(e=>e.Name == "张三");