Java collections: what many people forget

From the experience of code-review and responses to StackOverflow, there were quite a few points about the Java Collections API, which seemed obvious to me, but other developers for some reason did not know or knew about them, but did not feel confident about using them. In this article I collect in a common pile everything that has accumulated.

Content:

1. List.subList
2. PriorityQueue
3. EnumSet and EnumMap
4. Set.add (E) and Set.remove (E) return a boolean value.
5. Map.put (K, V), Map.remove (K), List.set (idx, E), List.remove (idx) return the previous item
6. Map.keySet () and Map.values ​​()
7. Arrays.asList can be a key
8. Collections.max
9. LinkedList, Stack, Vector, Hashtable

List.subList

About this already written , but it is worth repeating. Probably the most underrated method from the Collections API. It happens that you need to somehow process a part of the list (for example, in the algorithms of the "divide and conquer" family or when the task is parallelized). Many create a method or class that is tied to three parameters: List, from and to:

void processListPart(List<Item> list, int from, int to) { for(int idx = from; idx < to; idx++) { Item item = list.get(idx); ... } } 

So no need to do. The implementation of the algorithm should not care that it processes part of the list. Write:
')

 void processList(List<Item> list) { for(Item item : list) { ... } } 

And call

 processList(list.subList(from, to)); 

Even if you have everything in one method, it is more convenient to use an extended for loop than to mess with indices:

 for(Item item : list.subList(from, to)) {...} 

In addition, subList is a full-featured list, it also works on writing, making the appropriate changes to the parent list. Need to remove a lot of items from the middle of the list? Nothing is simpler:

 list.subList(from, to).clear(); 

Popular implementations like ArrayList do this very quickly.

Need to find out if the list starts with certain elements? And then the subList in hand!

 List<String> prefix = Arrays.asList("a", "prefix", "values"); if(myList.size() >= prefix.size() && myList.subList(0, prefix.size()).equals(prefix)) {...} 

Do you need to add all the elements of another list to one list except the first one? And here subList will come to the rescue:

 list1.addAll(list2.subList(1, list2.size())); 

Don't forget that you can write Arrays.asList(array).subList(from, to) , so the above applies to non-primitive arrays. Structurally, you cannot change them, but transferring a piece of an array to a method that accepts a list for reading is easy.

PriorityQueue

If subList is the most undervalued method, then PriorityQueue is, in my opinion, the most undervalued class. Many are faced with the task of finding, say, 10 minimum values ​​of a large unsorted list. Most often the list is sorted and then the first 10 values ​​are taken. If the original list cannot be changed, you will have to copy it again for sorting. But the priority queue will easily cope with this task:

 public static <T extends Comparable<T>> List<T> leastN(Collection<T> input, int n) { assert n > 0; PriorityQueue<T> pq = new PriorityQueue<>(Collections.reverseOrder()); for (T t : input) { if (pq.size() < n) { pq.add(t); } else if (pq.peek().compareTo(t) > 0) { pq.poll(); pq.add(t); } } List<T> list = new ArrayList<>(pq); Collections.sort(list); return list; } 

Such code, depending on the data, can work much faster than sorting. For example, for n = 10 and a randomly filled list of a million items, the priority queue is almost a hundred times faster than the sorting approach. In this case, additional memory is required O (n) and input elements can be processed in streaming mode (for example, select the 10 smallest numbers from the input file).

In general, people tend to study a couple of data structures and use them everywhere. Do not be lazy, get acquainted with different structures.

EnumSet and EnumMap

Still there is a code where enum values ​​are used as keys in HashSet and HashMap. Although it works, it is unnecessarily wasteful. The existing special classes EnumSet and EnumMap are much more productive. So if the enum is not more than 64 different values, EnumSet stores everything in one long type field in a bitmask. EnumMap contains all values ​​in a regular array of the same length as the number of elements in the enum, and does not store keys at all. Since each value in enum has a ordinal () ordinal number, you can easily move from an enum key to an array element. Also never need to change the size of the array.

Set.add (E) and Set.remove (E) return a boolean value.

Often I see a similar code:

 if(!set.contains(item)) { set.add(item); // do something } else { // do something else } 

Do not forget that the add operation to the Set returns true if the addition was successful (that is, there was no element) and false if such an element already existed. There is no need to complicate the code and punch the element twice through the hash table or binary tree, because you can write:

 if(set.add(item)) { // do something } else { // do something else } 

Similarly with the removal. Chain if(set.contains(item)) { set.remove(item); ... } if(set.contains(item)) { set.remove(item); ... } is replaced by if(set.remove(item)) { ... } .

Map.put (K, V), Map.remove (K), List.set (idx, E), List.remove (idx) return the previous item

From the same opera situation. Methods that change or delete an item in the collection return the previous value, and this should be used. Do not write, for example, like this:

 Item item = myMap.get(key); myMap.put(key, newItem); 

Write a simple Item item = myMap.put(key, newItem); . Do you want to swap two entries in the Map with the keys key1, key2? The temporary variable is not needed:

 myMap.put(key1, myMap.put(key2, myMap.get(key1))); 

Map.keySet () and Map.values ​​()

For some reason, many people forget that Map.keySet() and Map.values() return maps of the original Map that allow you to delete items (if Map is modifiable). It is necessary to leave in the Map only records with specific values ​​(and any keys)? You are welcome:

 myMap.values().retainAll(toRetain); 

removeIf also works, and with Java-8 removeIf :

 //      Map<String, List<Employee>> perDepartment = employees.stream().collect(groupingBy(Employee::getDepartmentName, HashMap::new, toList())); //         10 perDepartment.values().removeIf(list -> list.size() < 10); 

Arrays.asList can be a key

It happens that you need to create a Map or Set using a tuple of values. For example, you have Item PoJo objects that have name, type, version fields. They have already written equals and hashCode , they can be added to HashSet , everything is fine. But you want to select unique objects from the collection only by the name and type fields, ignoring version. You cannot change existing equals and hashCode . In such situations, people often create a separate class with only the name and type fields and use it as a key. However, for a one-time operation, it is easier to use Arrays.asList() :

 Map<List<Object>, Item> map = new HashMap<>(); for(Item item : items) { map.put(Arrays.asList(item.name, item.type), item); } Collection<Item> unique = map.values(); 

Arrays.asList() creates a list of the required number of elements and it has just the appropriate equals and hashCode : no boilerplate is needed. So you can create a key of any length, and null-values ​​and primitives will be processed correctly (after boxing). It will not work only if you want to have an array in the key.

Collections.min / max

It's amazing how often you can find hand-written code that finds the maximum or minimum element of something by some criterion. It would seem that such a trivial task should be solved long ago. In fact, it has been solved so long ago: there are methods Collections.min and Collections.max . It used to be not very convenient to write comparators, but in Java-8 everything became easier.

For example, you need to find the key in the Map corresponding to the maximum value. Write like this:

 maxKey = Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey(); 

It is possible through the Stream API, but Collections.max() somewhat faster. If you can't use Java-8 and comparators like Entry.comparingByValue() not available to you, they are not difficult to write.

Stack, Vector, Hashtable, LinkedList

Just do not use these classes. There is no benefit from them. Instead of Stack, use ArrayDeque, instead of Vector - ArrayList, instead of Hashtable - HashMap. If you need thread safety, they won't help you anyway. Perhaps in the nine they will still be marked @Deprecated (see JEP 277 ).

With LinkedList, the case is special. There seems to be no better analogue to the coherent list, and there are legends that it is actually useful. In reality, situations where LinkedList is better than ArrayList are extremely few in real life. Before Java-8, LinkedList could still be useful if you often remove items that are not going sequentially, according to some condition. In Java-8, List.removeIf appeared for this purpose, which in ArrayList, of course, is implemented more optimally (elements are moved only once). If you need to make a lot of inserts in different places (the task itself is exotic), most likely it will be faster to create a new ArrayList than to insert it into an existing LinkedList. Well, remember that LinkedList eats several times more memory, since each element is a separate object on the heap with links to the next and previous ones. LinkedList can only be used as a learning example.

That's all for today. Program with pleasure!