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();
}

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

非常感谢各位大佬的解答，怪我提问时没有详细说明我的场景，

12 楼我的回复能详细描述我的问题，其实将 List 转成 Map 是一种比较好的方案，

因为只需要转一次，后续的循环里面只需要根据 hash 来查询对应的值，远远比每一次都遍历快，

因为我提问的方式不正确（ X-Y Problem，从 23 、24 楼两位大佬学到的），

导致大家在错误的方向浪费时间，很抱歉。

[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 == "张三");

[loshine1992]

@Rwing

这不是一样的么，并没有提升效率。

[icyalala]

只就楼主目前写的问题来看，如果只需要查找一次，那就顺序遍历，无论如何都是 O(n) 的复杂度，无非就是在遍历或者比较这些地方稍微优化一些。如果需要多次查找，那就先转为 Map 再处理，但转 Map 这一步也还是 O(n) 复杂度。

我感觉这是个 XY problem 。。

[Ariver]

X/Y +1

[aoizz]

@icyalala #22
@Ariver #23 非常感谢，学习到了，今后提问题一定会描述清楚所有细节。转化为 Map 在处理这种方案我觉得是可行的，只需要转一次就可以，循环中根据 hash 查询，远比我循环比对查询来得快。

[gabon]

@aoizz 这样我感觉用 guava loading cache 之类的更合适

[pkwenda]

查了一下什么是楼上说的 xy 问题：
https://www.wikiwand.com/en/XY_problem

这个问题我也深有体会，我的组员有时会问一个很迷的问题，虽然他本质想解决 X 问题，但是他认为解决 Y 问题，X 问题可以迎刃而解。

查询肯定是 散列表最快，但是空间大

后续可能是否有范围查询？散列表没办法做 range，还是要有一定前瞻性

[zdt3476]

@pkwenda 可以考虑同时维护 list+map 。 或者是使用 B+树这类数据结构？ Java 好像有个 TreeMap 之类的东西吧。

[vindurriel]

标准的面试题 哈哈
内存能装下就建个 map 装不下就按 name 排序然后折半查找 至于如何排序 又是另一道面试题

[zhanggg]

二分或者多分并行遍历直接 equals 判断啊，转 map 还要额外的内存和 hash 计算开销

[vchroc]

@zdt3476 LinkedHashMap

[hyqCrystal]

map 正解

[Cola98]

先排个序，在二分？