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

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

直接 fori,找到第一个返回

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

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

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

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

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

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

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

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

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

@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();
//别的操作
}


})

空间换时间

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

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

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

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

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

我说一下 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，如果没有就可以快速跳过，而不用对比。

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

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

@Rwing

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

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

我感觉这是个 XY problem 。。

X/Y +1

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

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

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

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

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

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

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

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

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

@zdt3476 LinkedHashMap

map 正解

先排个序，在二分？