执行最快的搜索 - 我应该使用哪个集合？ [英] Performing the fastest search - which collection should i use?

问题描述

我知道：

• 如果您需要使用索引快速访问元素，则应选择ArrayList。


• 如果需要使用密钥快速访问元素，请使用HashMap。


• 如果需要快速添加和删除元素，请使用LinkedList（但它的搜索性能非常差） ）。

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

In order to perform the fastest search, on the basis of data stored in a collection object, which collection should I use?

以下是我的代码：

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

推荐答案

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

The thing which is often skipped when comparing ArrayList and LinkedList is cache and memory management optimisations. ArrayList is effectively just an array which means that it is stored in a continuous space in the memory. This allows the Operating System to use optimisations such as "when a byte in memory was accessed, most likely the next byte will be accessed soon". Because of this, ArrayList is faster than LinkedList in all but one case: when inserting/deleting the element at the beginning of the list (because all elements in the array have to be shifted). Adding/deleting at the end or in the middle, iterating over, accessing the element are all faster in case of ArrayList.

如果您需要搜索名称和 ID的学生，听起来像是带有复合键的地图 - 地图< Student，StudentData> 。我建议使用 HashMap 实现，除非您需要能够搜索集合并检索按键排序的所有元素，在这种情况下 TreeMap 可能是一个更好的主意。虽然记得 HashMap 有 O（1）访问时间，而 TreeMap 有 O（logn）访问时间。

If you need to search for student with given name and id, it sounds to me like a map with composite key - Map<Student, StudentData>. I would recommend to use HashMap implementation, unless you need to be able to both search the collection and retrieve all elements sorted by key in which case TreeMap may be a better idea. Although remember that HashMap has O(1) access time, while TreeMap has O(logn) access time.

我不太清楚你想要达到的目标 - 为什么要搜索这个系列呢？你想在那里找到什么？

I am not quite sure what you are trying to achieve - why to search this collection at all? What do you want to find in there?

这篇关于执行最快的搜索 - 我应该使用哪个集合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！