java - 在列表与集合中搜索元素的复杂性

Question

考虑一下，如果我必须在表中搜索特定行，根据 ORM，我相信每一行都是一个对象。我没有在 JDBC 上进行大量工作，所以通常作为更好的做法，这些 POJO 对象在哪里收集或保存？在集合或列表中？

我正在尝试找出在 List Vs 中搜索元素的复杂性。设置

我做了什么？

private void searchSet() {
        Set<String> names = new HashSet<>();
        names.add("srk");
        names.add("lastminute");
        names.add("monkey");
        for(String x:names){
            if(x.equals("monkey")){
                System.out.println("caught the name "+x);
            }
        }

}



private void searchList() {
    List<String> names = new ArrayList<>();
    names.add("srk");
    names.add("lastminute");
    names.add("monkey");
    for(String x:names){
        if(x.equals("monkey")){
            System.out.println("caught the name "+x);
        }
    }

}

我正在使用以下方法计算在集合和列表中搜索元素所花费的时间。

    long startTime,endTime,totalTime;
    startTime = System.nanoTime();
    endTime = System.nanoTime();
    totalTime = endTime - startTime;

现在，我有下面的统计数据

System.out.println("Time taken to search an element in list : "+totalTime);//for list - 614324 
System.out.println("Time taken to search an element in set : "+totalTime);//for set - 757359

根据这些统计数据可以得出结论，在 List 中搜索元素比在 set 中搜索元素更快？ 这是一个更好的集合来存储数据库记录对象，以供搜索。在列表与集合中搜索元素的复杂性是多少。在一般意义上？

Answer 1

数据结构没有复杂性，算法有。 (请注意，数据结构通常伴随着其基本操作的复杂性，这些操作本身就是微小的算法。)在您的情况下，您自己为两个容器实现了查找算法，并将其作为线性搜索进行，即 O(n ).您观察到的速度差异是 ArrayList 比 HashSet 更简单和更快遍历的结果，即算法具有相同的复杂性，但常数因子更小。

其次，您在想要计时的函数中有 I/O。这通常会完全控制您执行的任何实际操作，并使您的基准测试变得无用。

第三，您正在寻找复杂性并编写了基准。那是错误的。您可以通过基准测试并在图表中绘制不同输入大小的结果来获得复杂性的提示，但要真正了解复杂性，您必须分析算法，而不是运行算法。

第四，Java中的List和Set不是数据结构，而是接口(interface)。您选择的数据结构是 ArrayList(实现 List 接口(interface)的连续数组数据结构的一个版本)和 HashSet(实现 Set 接口(interface)的哈希表数据结构的一个版本)。所以你需要看看那些。

对于数组，除非它已排序，否则查找算法需要线性时间，因为除了遍历整个数组之外别无选择。

对于针对查找进行优化的哈希表，查找算法在技术上在最坏情况下仍然是 O(n)，但在常见情况下将是 O(1)。但是，您必须实际使用优化的查找算法(由 Set.contains 提供)才能利用这一点 - 对 HashSet 的线性搜索并不比对 ArrayList 的线性搜索更好(实际上更差)。