Java 执行最快的搜索 - 我应该使用哪个集合？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30321169/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Performing the fastest search - which collection should i use?
提问by
I know:
我知道：
- If you need fast access to elements using index, ArrayList should be choice.
- If you need fast access to elements using a key, use HashMap.
- If you need fast add and removal of elements, use LinkedList (but it has a very poor seeking performance).
- 如果您需要使用索引快速访问元素，则应该选择 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?
为了执行最快的搜索，基于存储在集合对象中的数据，我应该使用哪个集合？
Below is my code:
下面是我的代码：
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;
}
}
采纳答案by Jaroslaw Pawlak
The thing which is often skipped when comparing ArrayListand LinkedListis cache and memory management optimisations. ArrayListis 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, ArrayListis faster than LinkedListin 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.
比较时，这是经常发生的事情跳过ArrayList并且LinkedList是高速缓存和内存管理的优化。ArrayList实际上只是一个数组，这意味着它存储在内存中的连续空间中。这允许操作系统使用优化，例如“当访问内存中的一个字节时，很可能很快就会访问下一个字节”。正因为如此，ArrayList它比除LinkedList一种情况外的所有情况都快：在列表开头插入/删除元素时（因为必须移动数组中的所有元素）。在末尾或中间添加/删除、迭代、访问元素在ArrayList.
If you need to search for student with given name andid, it sounds to me like a map with composite key - Map<Student, StudentData>. I would recommend to use HashMapimplementation, unless you need to be able to both search the collection and retrieve all elements sorted by key in which case TreeMapmay be a better idea. Although remember that HashMaphas O(1)access time, while TreeMaphas O(logn)access time.
如果您需要搜索具有给定姓名和id 的学生，对我来说这听起来像是带有复合键 - 的地图Map<Student, StudentData>。我建议使用HashMap实现，除非您需要能够搜索集合并检索按键排序的所有元素，在这种情况下TreeMap可能是一个更好的主意。虽然记得HashMap有O(1)访问时间，而TreeMap有O(logn)访问时间。
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?
我不太确定你想要达到什么目标 - 为什么要搜索这个集合？你想在里面找到什么？
回答by bvdb
There is nothing wrong in keeping multiple collections to access your data faster.
保留多个集合以更快地访问数据并没有错。
In this situation I would use 2 HashMap<String, Student>'s. One for each search-key.
在这种情况下，我会使用 2 HashMap<String, Student>。每个搜索键一个。
(PS: Or if you don't know which kind of keyword is used to search for, then you can store both in the same map).
（PS：或者如果你不知道用哪种关键字搜索，那么你可以将两者存储在同一个地图中）。
回答by AdamSkywalker
With given restrictions, you should use HashMap. It will give you quick search, as you wished.
根据给定的限制，您应该使用 HashMap。它将为您提供快速搜索，如您所愿。
If you care about traversing elements in specific order, you should choose TreeMap (natural order) or LinkedHashMap (insertion order).
如果你关心按特定顺序遍历元素，你应该选择TreeMap（自然顺序）或LinkedHashMap（插入顺序）。
If your collection is guaranteed immutable, you can use sorted ArrayList with binary search, it will save you some memory. In this case, you can search only by one specific key, which is undesirable in many real world applications.
如果您的集合保证不可变，您可以使用带二分查找的排序 ArrayList，它会为您节省一些内存。在这种情况下，您只能通过一个特定的键进行搜索，这在许多实际应用程序中是不可取的。
Anyway, you should have really hugenumber of elements (millions/billions) to feel the difference between O(logN) solutions and O(1) solutions.
无论如何，您应该拥有大量元素（数百万/十亿）来感受 O(logN) 解决方案和 O(1) 解决方案之间的差异。
If you want to learn more about data structures, I recommend you to review Algorythms course by Princeton university on coursera.com
如果你想学习更多关于数据结构的知识，我建议你在 coursera.com 上查看普林斯顿大学的算法课程
