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

Question

我知道：

如果您需要使用索引快速访问元素，应选择 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;
    }
}

Answer 1

比较 ArrayList 和 LinkedList 时经常被忽略的是缓存和内存管理优化。 ArrayList 实际上只是一个数组，这意味着它存储在内存中的连续 space 中。这允许操作系统使用优化，例如“当访问内存中的一个字节时，很可能很快就会访问下一个字节”。因此，ArrayList 在除一种情况外的所有情况下都比 LinkedList 快：当 inserting/deleting 列表开头的元素时（因为数组中的所有元素都必须移动）。 Adding/deleting 在末尾或中间，遍历，访问元素在 ArrayList.

的情况下都更快

如果您需要搜索具有给定姓名和 id 的学生，在我看来这就像一张带有复合键的地图 - Map<Student, StudentData>。我建议使用 HashMap 实现，除非您需要能够搜索集合并检索按键排序的所有元素，在这种情况下 TreeMap 可能是更好的主意。尽管记住 HashMap 有 O(1) 访问时间，而 TreeMap 有 O(logn) 访问时间。

Answer 2

保留多个集合以更快地访问数据并没有错。

在这种情况下，我会使用 2 HashMap<String, Student>。每个搜索键一个。

(PS: 或者如果你不知道用哪种关键字来搜索，那么你可以将两者存储在同一个地图中)。

Answer 3

在给定的限制条件下，你应该使用HashMap。它会给你快速搜索，如你所愿。

如果你关心按特定顺序遍历元素，你应该选择TreeMap（自然顺序）或LinkedHashMap（插入顺序）。

如果你的集合保证不可变，你可以使用带二分查找的排序ArrayList，这样可以节省一些内存。在这种情况下，您只能通过一个特定的键进行搜索，这在许多实际应用程序中是不可取的。

无论如何，你应该有真正巨大个元素（millions/billions）来感受O(logN)解决方案和O(1)解决方案之间的区别。

如果你想了解更多关于数据结构的知识，我建议你在 coursera.com

上复习普林斯顿大学的 Algorythms 课程

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

Performing the fastest search - which collection should i use?

java

collections

search

time-complexity