Doing the quickest search - which collection should I use?

Question

I know:

• If you need quick access to elements using an index, an ArrayList must be selected.
• If you need quick access to items using a key, use HashMap.
• If you need to quickly add and remove items, use LinkedList (but it has very poor search performance).

To perform the fastest search based on the data stored in the 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; } } 

Answer 1

The thing that is often skipped when comparing ArrayList and LinkedList is optimizing cache and memory management. ArrayList is just an array, which means it is stored in contiguous space in memory. This allows the operating system to use optimizations such as "when a byte in memory was accessed, most likely the next byte will be available in the near future." Because of this, ArrayList faster than LinkedList in all cases, except for one thing: when inserting / deleting an element at the beginning of the list (because all elements in the array must be shifted). Adding / removing at the end or in the middle, repeating, accessing an element is faster in the case of ArrayList .

If you need to look for a student with the given name and , it sounds to me like a map with a composite key - Map<Student, StudentData> . I would recommend using a HashMap implementation if you don't need to both look for the collection and retrieve all the items sorted by key, in which case TreeMap might be a better idea. Although remember that HashMap has O(1) access time, and TreeMap has O(logn) access time.

I'm not quite sure what you are trying to achieve - why bother looking for this collection? What do you want to find there?

Answer 2

Given the restrictions, you should use a HashMap. This will give you a quick search of your choice.

If you are interested in moving items in a specific order, you should choose TreeMap (natural order) or LinkedHashMap (insert order).

If your collection is guaranteed unchanged, you can use a sorted ArrayList with binary search, it will save you some memory. In this case, you can search for only one specific key, which is undesirable in many real-world applications.

In any case, you must have a really huge number of elements (millions / billions) in order to feel the difference between O (logN) solutions and O (1) solutions.

If you want to learn more about data structures, I recommend that you study the Algorythms course at Princeton University on coursera.com

Answer 3

There is nothing wrong with having multiple collections access your data faster.

In this situation, I would use 2 HashMap<String, Student> . One for each search key.

(PS: Or, if you don’t know which keyword is used to search, you can save them on one map).