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

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

[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]

先排个序，在二分？