执行最快的搜索 - 我应该使用哪个集合?

2022-09-03 01:40:48

我知道:

  • 如果您需要使用索引快速访问元素,ArrayList应该是选择。
  • 如果需要使用键快速访问元素,请使用 HashMap。
  • 如果您需要快速添加和删除元素,请使用LinkedList(但它的搜索性能非常差)。

为了执行最快的搜索,根据存储在集合对象中的数据,我应该使用哪个集合?

以下是我的代码:

    public void fillAndSearch(Collection<Student> collection) {
      if(collection!=null){
        for (int i=0; i<=10; i++) {
            Student student = new Student("name" + i, "id" + i);
            collection.add(student);
        }
      }
        //here We have to perform searching for "name7" or "id5",
        //then which implementation of collection will be fastest?
    }

class Student {
    String name;
    String id;

    Student(String name, String id) {
        this.name = name;
        this.id = id;
    }
} 

答案 1

比较时经常跳过的事情是缓存和内存管理优化。 实际上只是一个数组,这意味着它存储在内存中的连续空间中。这允许操作系统使用优化,例如“当访问内存中的某个字节时,很可能很快就会访问下一个字节”。因此,比除一种情况外的所有情况都要快:在列表开头插入/删除元素时(因为数组中的所有元素都必须移动)。在末尾或中间添加/删除,迭代,访问元素都更快。ArrayListLinkedListArrayListArrayListLinkedListArrayList

如果您需要搜索具有名字ID的学生,那么对我来说,这听起来像是带有复合键的地图 - .我建议使用实现,除非您需要能够搜索集合并检索按键排序的所有元素,在这种情况下可能是一个更好的主意。虽然记住有访问时间,同时有访问时间。Map<Student, StudentData>HashMapTreeMapHashMapO(1)TreeMapO(logn)


答案 2

有给定的限制,你应该使用HashMap。它会像您所愿的那样为您提供快速搜索。

如果您关心以特定顺序遍历元素,则应选择 TreeMap(自然顺序)或 LinkedHashMap(插入顺序)。

如果你的集合是保证不可变的,你可以使用排序的 ArrayList 和二进制搜索,这将节省一些内存。在这种情况下,您只能按一个特定键进行搜索,这在许多实际应用程序中都是不希望的。

无论如何,你应该有大量的元素(数百万/数十亿)来感受O(logN)解决方案和O(1)解决方案之间的区别。

如果你想了解更多关于数据结构的知识,我建议你复习普林斯顿大学的算法课程,coursera.com