Java 中一个 size 为 10 万的 List<User>,怎么查找 name="张三"的 User 最快？
aoizz · 2021-06-15 10:27:57 +08:00 · 3977 次点击这是一个创建于 1256 天前的主题，其中的信息可能已经有所发展或是发生改变。
需求大概就是这样，我目前使用的是
Optional<User> first = userList.stream().filter(e->e.getName().equals("张三")).findFirst();
if (first.isPresent()){
User user = first.get();
}
但我觉得这种方式效率有点低，请问有别的更快的方式吗？
第 1 条附言 · 2021-06-15 12:50:38 +08:00
非常感谢各位大佬的解答，怪我提问时没有详细说明我的场景，
12 楼我的回复能详细描述我的问题，其实将 List 转成 Map 是一种比较好的方案，
因为只需要转一次，后续的循环里面只需要根据 hash 来查询对应的值，远远比每一次都遍历快，
因为我提问的方式不正确（ X-Y Problem，从 23 、24 楼两位大佬学到的），
导致大家在错误的方向浪费时间，很抱歉。
12 楼我的回复能详细描述我的问题，其实将 List 转成 Map 是一种比较好的方案，
因为只需要转一次，后续的循环里面只需要根据 hash 来查询对应的值，远远比每一次都遍历快，
因为我提问的方式不正确（ X-Y Problem，从 23 、24 楼两位大佬学到的），
导致大家在错误的方向浪费时间，很抱歉。
 |
1
justicelove 2021-06-15 10:33:52 +08:00  1
最好是插入的时候就通过一个固定算法来计算下标, 查找时同样 通过固定算法来获取对应下标, 这么做其实有点像自己实现一个类似 map 的快速查找结构
|
 |
2
vindac 2021-06-15 10:33:57 +08:00 1
直接 fori,找到第一个返回
|
 |
3
timethinker 2021-06-15 10:34:30 +08:00 2
在不进行预处理的情况下，你可以简单的改为并行流然后查找，users.stream().parallel().filter...，或者 users. parallelStream().filter...
|
 |
4
aoizz OP |
 |
5
amon 2021-06-15 10:41:02 +08:00 1
转成 Map，
userList.stream().collect(Collectors.groupingBy(User::getName)); |
 |
6
qiuhang 2021-06-15 10:43:05 +08:00 3
这种没啥好办法吧，要想查找快，那你在组织数据的时候就得多下功夫。比如按照字典顺序排列，然后用二分查找或者干脆存成查找树。你这无序的 list，就是天王老子来了它复杂度也得是 O(n)。
|
 |
7
InkAndBanner 2021-06-15 10:43:59 +08:00 1
改成并行流会快，但是如果数据很少 并行流会慢
|
 |
8
gabon 2021-06-15 10:46:50 +08:00 via Android 1
这数据总归不是内存里生成的吧，不能查的时候只查这一个吗
|
 |
9
yejinmo 2021-06-15 10:47:56 +08:00 1
|
 |
10
Edcwsyh 2021-06-15 10:52:39 +08:00 1
@justicelove 这好像就是哈希方法吧....但 Map 不是哈希啊, HashMap 才是
|
|
11
justicelove 2021-06-15 10:59:52 +08:00 1
@Edcwsyh #10 其实 Tree Map 也是类似的思路
|
|
12
aoizz OP @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(); //别的操作 } }) |
 |
13
aitaii 2021-06-15 11:57:24 +08:00
空间换时间
|
 |
14
Leviathann 2021-06-15 12:01:24 +08:00
单次查询就这样啊
多线程分段查也许能快点，但是 10w 这个量级也不好说 多次查就转 map |
 |
15
securityCoding 2021-06-15 12:04:56 +08:00
解决问题的思路明显是错的
|
|
16
timethinker 2021-06-15 12:07:30 +08:00 2
@aoizz 按照这个思路，很难想象你一次性要获取 10W 的用户（根据 getByIds，使用 SQL IN 语句？），优化的核心思路在于时间跟空间的平衡点，数据查找尽量使用 SQL 通过数据库来筛选数据，充分利用好数据库的索引功能，避免一次性获取大量数据，然后只使用里面的少量数据。
不过最重要的还是看数据量与看场景，是 OLTP 还是 OLAP，前者尽量保证短时间内完成操作，后者更多的是通过提前创建派生数据来提高查找速度（以空间换时间）。 |
 |
18
3dwelcome 2021-06-15 12:17:03 +08:00
我说一下 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，如果没有就可以快速跳过，而不用对比。 |
 |
20
Rwing 2021-06-15 12:21:09 +08:00
我来跑个题，各位不考虑一下 C# 吗，🙂
var first = userList.First(e=>e.Name == "张三"); |
 |
21
loshine1992 2021-06-15 12:23:24 +08:00
|
 |
22
icyalala 2021-06-15 12:27:42 +08:00 2
只就楼主目前写的问题来看，如果只需要查找一次，那就顺序遍历，无论如何都是 O(n) 的复杂度，无非就是在遍历或者比较这些地方稍微优化一些。如果需要多次查找，那就先转为 Map 再处理，但转 Map 这一步也还是 O(n) 复杂度。
我感觉这是个 XY problem 。。 |
 |
23
Ariver 2021-06-15 12:36:28 +08:00
X/Y +1
|
|
24
aoizz OP |
 |
26
pkwenda 2021-06-15 13:15:07 +08:00
查了一下什么是楼上说的 xy 问题：
https://www.wikiwand.com/en/XY_problem 这个问题我也深有体会，我的组员有时会问一个很迷的问题，虽然他本质想解决 X 问题，但是他认为解决 Y 问题，X 问题可以迎刃而解。 查询肯定是 散列表最快，但是空间大 后续可能是否有范围查询？散列表没办法做 range，还是要有一定前瞻性 |
 |
27
zdt3476 2021-06-15 14:09:45 +08:00
@pkwenda 可以考虑同时维护 list+map 。 或者是使用 B+树这类数据结构？ Java 好像有个 TreeMap 之类的东西吧。
|
 |
28
vindurriel 2021-06-15 16:37:25 +08:00 via iPhone
标准的面试题 哈哈
内存能装下就建个 map 装不下就按 name 排序然后折半查找 至于如何排序 又是另一道面试题 |
 |
29
zhanggg 2021-06-15 19:35:46 +08:00
二分或者多分并行遍历直接 equals 判断啊，转 map 还要额外的内存和 hash 计算开销
|
 |
31
hyqCrystal 2021-06-15 23:27:01 +08:00
map 正解
|
 |
32
Cola98 2021-06-16 08:34:26 +08:00
先排个序，在二分？
|
Select Language