Java Collections

Collections

1. Map is not really a Collection interface. It is not derived from Collection.
2. You can created one collection to another as for every collection there is constructor which takes Collection as an argument. It is called conversion constructor.

3. Every collection can be converted to an array of objects or array of a given type of objects.

Object[] toArray();

T[] toArray(T[] a);

4. Collection interface extends Iterable.

5. if you want to remove the object from collection while traversing it , use iterator for the traversing and iterator.remove for removing the element.

6. Collections.singleton(e) is a static factory method that returns an immutable Set containing only the specified element.

7. When you add or remove, addAll, removeAll on the Collection, it returns true only if the Collection is modified as result of the operation.

8. HashSet is the best overall Set implementation.

9. Set : HashSet, LinkedHashSet, SortedSet
10. List ( ordered collection ) : ArrayList, LinkedList
11. Array.asList : static factory method. The list returned is not a copy so whatever you change in the list also reflect in array.
12. Collections, Arrays...
13. List also provide ListIterator which is richer than Iteraror. Allows you to traverse in any direction.  ListIterator : The set method overwrites the last element returned by next or previous with the specified element.The add method inserts a new element into the list immediately before the current cursor position

14. subList returns te view in the original list , so any change in view is reflected in original list.

15. Queues whose capacity is limited are called bounded.

15. For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.

16. HasMap somehow uses combination of equals and hashCode methods of the key object to determine the location where values are stored.

17. Stable sort : A sort which does not reorder equal elements.

18. Classes that implement comparable should have natural orderings that are consistent with equals. It is highly recommended.

19. SortedSet 's toString methods returns a String containing all elements in sorted order.

20. TreeSet(SortedSet s) takes the sorted set and converts into TreeSet using the sorted set's comparator, but TreeSet(Collection ) creates a treeset and orders the elements in their natural order.

21. range-views( the list returnd by subList opertaion) of list becomes undefined if the original is modified by adding or removing the element. But range-views of sets remain valid even if original set is modified. 


Some of the old bulk operations on collections ( addAll, removeAll, retainAll )  are mutative in nature, while new aggregate operations are designed to be non-mutative and one should write the code in such a way that it does not modify the underlying source. 

HashSet, HashMap both provide constant time  basic operations (add, remove, contains,size). 

HashSet - Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

More on  Collections 

instance size is something you have no control, so only thing you have control is the load factor. Make sure load factor is not too low and initial capacity is not too high , if iteration performance is important because for creating the iterator it has to still scan all the places in underlying(backing) hashmap.  You don't want backing hashmap to be too sparse.

Hashtable  -  old implementation, synchronized / thread-safe, does not allow null keys/values. To be able to retrieve and store objects in hashtable, the object used as keys must implement hashCode and equals methods. It was originally not part of the java collections. 

LinkedHashSet -  is great data structure, it provides all the benefits of HashMap ( constant time put,get ) , linear time iteration ( does not depend upon initial capacity or load factor )  in insertion order. The storage structure is same as HashMap, just that it also maintain a doubly linked list running through all the nodes . This double linked provides the linear time iteration and maintain insertion order.  Put and get are exactly same as HashMap.  The cost for all this benefits is some extra space and also little extra time for put. 

List-    sublist()  is backed by original list and just returns a view. 

Collections class has two set of methods to get synchronized and unmodifiable views(original collection still backs the returned collection)   of the various collection implementation.  Collections.synchronized<CollectionName>, Collections.unmodifiable<CollectionClassName>

Collections API  sort method uses merge sort algorithm. The reason is because it is stable(does not reorder equal elements).  So if there is already sorted list, sorted on key1 and you want to sort it based on another key key2, this will still keep the elements having same value of key2 , sorted by the key1. 

For primitive type Arrays.sort uses dual pivot quick sort as stability is not an issues for primitive types. 

Queue:  Have two types of operations , one that throws exception if an operation fails, another returns special value. Every queue implementation must specify ordering of elements.

The queues which restrict the number of elements are called bounded.  Incidentlally LinkedList also implements Queue interface.

BlockingQueue : This is the Queue which also supports blocking methods while inserting ( if space is not available ) or removing( if it is empty )  elements from queue.  The blocking methods come in two flavors , one blocks indefinitely and another blocks until a given time period.

Deque - Double ended Queue.  Deque interface allows it to behave both as Queue ( FIFO) and Stack ( LIFO). Incidentally LinkedList also implements Deque interface.   Whatever methods are in Queue interface, it provides two variants of those ...one for operating at beginning ( getFirst, offerFirst, removeFirst, pollFirst, peekFirst, removeFirst) and other for operating at the end of the queue.

TreeMap is implementation of SortedMap interface. SortedMap maintains the order of keys in ascending order or the order specified by comparator.  It has four constructors TreeMap(), TreeMap(Comparator<? super K> comparator), TreeMap(Map <? extends K ,? extends V>) , TreeMap(SortedMap<? extends K ,? extends V>)  . The constructor which takes Map , which sort the keys in natural ordering of the keys. The constructor which takes SortedMap keeps the same order as SortedMap.