Java Collections Framework

• A collection in java is framework that provides architecture to store and manipulate the group of Object.
• All the operation that you perform on a data such as searching, sorting, insertion .manipulation, deletion etc.
• Java collection provide many interface(Set,List,Queue,Deque,SortedSet,SortedMap) and
  class(ArrayList,Vector,LinkedList, PriorityQueue, HashSet, HashMap, LinkedHashSet, TreeSet,TreeMap).

 

The Set Interface

HashSet, LinkedHashSet, and TreeSet Classes

• HashSet class is the default implementation used in most cases. 
• LinkedHashSet is like a combination of HashSet and List in that it does not allow duplicate entries as with Sets, but traverses its elements in the order they were inserted, like a List would do. 
• TreeSet will constantly keep all its elements in some sorted order.

SortedSet and Navigable Set Interfaces

As the name implies, SortedSet is a Set with the property that it is always sorted. The NavigableSet interface, added with Java 6, allows us to navigate through the sorted list, providing methods for retrieving the next element greater or smaller than a given element of the Set.

The List Interface

ArrayList and LinkedList Classes

• ArrayList is the default implementation for List, it does allow duplicate elements and iteration in the order of insertion. As it is based on arrays, it is very fast to iterate and read from, but very slow to add or remove an element at random positions, as it has to rebuild the underlying array structure. 
• In contrast, LinkedList makes it easy to add or remove elements at any position in the list while being slower to read from at random positions.

The Queue Interface

Thing to mention about LinkedList is that while it implements List, it actually also implements Queue. It does so based on the fact that its actual implementation as a doubly-linked list makes it quite easy to also implement the Queue interface.

PriorityQueue class

Besides LinkedList, another common Queue implementation is PriorityQueue. It is an implementation that keeps its elements ordered automatically. It has functionality similar to TreeSet, except that it allows duplicate entries.

The Map Interface

No relation to the Collection interface. A Collection operates on one entity, while a Map operates on two: a unique key, e.g. a vehicle identification number, and an object related to the key, e.g. a car. To retrieve an object from a Map, you would normally use its key.

Hashtable, Hashmap, and LinkedHashMap Classes

The Hashtable class was the first Collection in Java 1 that was based on the hash-table data structure. Unfortunately, like Vector, the class is deprecated because of its suboptimal performance. We can forget about it and use the other Map implementations instead. HashMap is the default implementation that you will find yourself using in most cases.
A Map usually doesn’t make any guarantee as to how it internally stores elements. An exception to this rule, however, is LinkedHashMap, which allows us to iterate the map in the order of insertion.

Figure 2 The Map Hierarchy

SortedMap

Let’s look at the interfaces that extend Map. As the name implies, SortedMap extends Map and defines the contract of a constantly sorted map. NavigableMap takes it even further, adding methods to navigate sorted maps. This allows us to get all entries smaller or bigger than some entry, for example. There are actually many similarities between the Map and Set hierarchies. The reason is that Set implementations are actually internally backed by Map implementations.

Map Inteface

Now let’s look at the map interface. This interface has no relation to the Collection interface. A Collection operates on one entity, while a map operates on two entities – A unique key, for example a Vehicle Identification Number, and an object that is related to this key, for example a car object. With the help of the key you can retrieve the object it relates to. The interface map is the root of a lot of interfaces and classes, which we will look at now. The class Hashtable was the first collection in Java JDK1 that was based on the data structure hashtable, so the Java creators called it Hashtable. Unfortunately, this makes it hard to differentiate between the two. Like Vector, the class is deprecated because of its suboptimal performanceso let’s remove and forget about it. Instead, use one of the other classes that implement the map interface. HashMap is the default implementation that you should use in the majority of cases. A Map usually does not make any guarantees on how it internally stores its elements. An exception to this rule is LinkedHashMap, which allows to iterate the map in the order of insertion. Last but not least, TreeMap is a constantly sorted map.

Synchronized Wrappers

The synchronization wrappers add automatic synchronization (thread-safety) to an arbitrary collection. Each of the six core collection interfaces — Collection, Set, List, Map, SortedSet, and SortedMap — has one static factory method.

public static  Collection synchronizedCollection(Collection c);
public static  Set synchronizedSet(Set s);
public static  List synchronizedList(List list);
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m);
public static  SortedSet synchronizedSortedSet(SortedSet s);
public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m);

Each of these methods returns a synchronized (thread-safe) Collection backed up by the specified collection.

Unmodifiable wrappers

Unmodifiable wrappers take away the ability to modify the collection by intercepting all the operations that would modify the collection and throwing an UnsupportedOperationException. It’s main usage are;

• To make a collection immutable once it has been built. In this case, it’s good practice not to maintain a reference to the backing collection. This absolutely guarantees immutability.
• To allow certain clients read-only access to your data structures. You keep a reference to the backing collection but hand out a reference to the wrapper. In this way, clients can look but not modify, while you maintain full access.

These methods are;

public static  Collection unmodifiableCollection(Collection extends T> c);
public static  Set unmodifiableSet(Set extends T> s);
public static  List unmodifiableList(List extends T> list);
public static <K,V> Map<K, V> unmodifiableMap(Map extends K, ? extends V> m);
public static  SortedSet unmodifiableSortedSet(SortedSet extends T> s);
public static <K,V> SortedMap<K, V> unmodifiableSortedMap(SortedMap<K, ? extends V> m);

Thread Safe Collections

Java 1.5 Concurrent package (java.util.concurrent) contains thread-safe collection classes that allow collections to be modified while iterating. By design iterator is fail-fast and throws ConcurrentModificationException. Some of these classes are CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet.
Read these posts to learn about them in more detail.

• Avoid ConcurrentModificationException
• CopyOnWriteArrayList Example
• HashMap vs ConcurrentHashMap

Collections API Algorithms

Java Collections Framework provides algorithm implementations that are commonly used such as sorting and searching. Collections class contain these method implementations. Most of these algorithms work on List but some of them are applicable for all kinds of collections.

Sorting

The sort algorithm reorders a List so that its elements are in ascending order according to an ordering relationship. Two forms of the operation are provided. The simple form takes a List and sorts it according to its elements’ natural ordering. The second form of sort takes a Comparator in addition to a List and sorts the elements with the Comparator.

Shuffling

The shuffle algorithm destroys any trace of order that may have been present in a List. That is, this algorithm reorders the List based on input from a source of randomness such that all possible permutations occur with equal likelihood, assuming a fair source of randomness. This algorithm is useful in implementing games of chance.

Searching

The binarySearch algorithm searches for a specified element in a sorted List. This algorithm has two forms. The first takes a List and an element to search for (the “search key”). This form assumes that the List is sorted in ascending order according to the natural ordering of its elements. The second form takes a Comparator in addition to the List and the search key, and assumes that the List is sorted into ascending order according to the specified Comparator. The sort algorithm can be used to sort the List prior to calling binarySearch.

Composition

The frequency and disjoint algorithms test some aspect of the composition of one or more Collections.

• frequency: counts the number of times the specified element occurs in the specified collection
• disjoint: determines whether two Collections are disjoint; that is, whether they contain no elements in common

Min and Max values

The min and the max algorithms return, respectively, the minimum and maximum element contained in a specified Collection. Both of these operations come in two forms. The simple form takes only a Collection and returns the minimum (or maximum) element according to the elements’ natural ordering.
The second form takes a Comparator in addition to the Collection and returns the minimum (or maximum) element according to the specified Comparator.