我应该使用存储 id 的 Map,还是遍历条目来查找对象?[已结束]

Should I use a Map storing the id, or iterate over entries to find an object? [closed]

提问人:Liam 提问时间:10/19/2023 更新时间:10/19/2023 访问量:55

问:


想改进这个问题吗?更新问题,以便可以通过编辑这篇文章来用事实和引文来回答。

上个月关闭。

我想知道在从集合中查找具有 id 的条目时,我应该使用以下哪种方法?

使用地图

Map<String, MyObject> map = new HashMap<>();

public MyObject getById(String id) {
  return map.get(id);
}

使用列表/集合

List<MyObject> list = new ArrayList<>();

public MyObject getObjectById(String id) {
    for (MyObject object : list) {
        if (object.getId().equals(id)) {
            return object;
        }
    }

    return null;
}

如果没有特定的用例,建议使用哪个?

Java 对象 集合

评论

1赞 Reilas 10/19/2023
好吧,在这种情况下,也是如此。
0赞 Basil Bourque 10/19/2023
“特定用例”正是本课题所需要的。没有目标和判断成功的标准,我们怎么能提供答案?
0赞 Liam 10/19/2023
@BasilBourque 也许就像@CalebKeller在一般情况下使用时完全能够为场景提供答案一样?或者也许你不同意他的回答..?

答:

3赞 Caleb Keller 10/19/2023 #1

如果你能使用HashMap,你绝对应该这样做。使用其键从 HashMap 中检索项目需要恒定的时间,但遍历数组所需的时间与数组中的元素数量成正比。用更专业的术语来说,使用 HashMap 的查找是 O(1),而使用 ArrayList 的查找是 O(n)。

这意味着使用 HashMap 的代码将始终很快,但使用 ArrayList 的代码将随着您向其添加更多元素而显着减慢。

评论

0赞 Liam 10/19/2023
啊,好的,非常好,谢谢!话虽如此,如果您知道集合将始终保持较小,您是否建议使用 ArrayList?这能打败地图吗?
1赞 David Conrad 10/19/2023
@Liam我相信是的。地图有一些开销,所以如果列表只有几个项目,它可能会更快。但在这种情况下,它们都会如此之快,这几乎无关紧要。不过,如果这真的很重要,那么要做的就是个人资料。查找 Java Microbenchmark Harness (JMH)。
0赞 WJS 10/19/2023
考虑到地图不是直接的一对一查找。get 方法将为密钥获取正确的“桶”。然后,需要在存储桶中搜索键以检索关联的值。但是,对于大量项目,它仍然比列表更有效。
0赞 Liam 10/19/2023
好的,谢谢你们:),我也会看看微基准