Java Collections Framework

http://bharatonjava.wordpress.com/2012/07/29/collections/

Important Interfaces and classes in the Collections Framework

Interfaces:

1. Collections
2. Set
3. SortedSet
4. List
5. Map
6. SortedMap
7. Queue
8. NavigableSet
9. NavigableMap

 

Concrete core 13 Implementation Classes

1. Maps
   1. HashMap
   2. HashTable
   3. TreeMap
   4. LinkedHashMap
2. Sets
   1. HashSet
   2. LinkedHashSet
   3. TreeSet
3. Lists
   1. ArrayList
   2. Vector
   3. LinkedList
4. Queues
   1. PriorityQueue
5. Utilities
   1. Collections
   2. Arrays

Not all collections implement the Collection interface eg. none of the map related classes and interfaces extend from Collections. Hence they do not pass Is-A relationship test for collections.

so HashMap, HashTable, TreeMap and LinkedHashMap do not implement Collection Interface.

Note: Collection is an interface while Collections is a concrete Utility class with static methods.

Fig. below shows the inheritance hierarchy for the Collections Framework.

There are 4 basic types of collections:

• Lists – List of items
• Sets – Unique instances
• Maps – Key-Value pairs
• Queues – Maintain an order

Sorting and Ordering of Collections:
Sorting is a type of ordering.

Ordered:
When a Collection is ordered you may iterate through the collection in a specific order. An ArrayList is ordered by element’s index position however a HashTable collection is not ordered. You won’t find any specific order when you iterate over the HashTable.
A LinkedHashSet keeps the order established by insertion, so the the last element inserted is the last element in the LinkedHashSet as opposed to an ArrayList where you can insert an element at any index position.
There are some collection that keep a natural order of the elements. These collections are not only Ordered but sorted.

Sorted:
A sorted collection means that the order in the collection is determined by some rule based on the properties of the object themselves and has nothing to do with when an object was inserted or accessed last time or at what position it was inserted.
You put the object in collection and collection will determine what order to put them in based on the sort order. A collection like any List which maintains an order based on insertion is not called sorted unless it arranges it’s elements using some sort order. Mostly the sort order used is something called the natural order.

We know how to sort alphabetically; A comes before B and F comes before G and so on. So for a collection of String the natural order is alphabetical and for collections with integer values the natural order will be numeric ie. 1 comes before 2 and so on… But what if a collection contains an Employee object? there is no way a collection can determine the ordering of an Object unless we provide through an interface called Comparable that determines how instances of a class can be compared to one another.
The developer decides how an Object object should be compared to other using one or more instance variables.
Apart from the order as specified by the Comparable interface you can also define different sort orders using Comparator interface

List Interface
A List cares about index. One thing that Lists have and other collections don’t is a set of method related to index position. These key methods include

get(int index), indexOf(Object o), add(int index, Object obj)

All three List implementations are ordered by index positions. A position that you determine either by setting object at a specific index or by adding it without specifying index, in which case the object is added to the end.

ArrayList
ArrayList is a growable array. It provides fast iteration and fast random access. It is an ordered collection (by index) and not sorted. Choose this over a LinkedList when you need fast iteration but aren’t as likely to be doing a lot of insertion and deletion.

Vector
Vector is a legacy collection that comes from the earlier days of java not widely used today. It is similar to ArrayList but Vector methods are Synchronized for Thread safety. Prefer using ArrayList as Synchronized methods causes performance hit you might not need. If you need thread safety in your collection use utility methods from Collections. Vector is the only class other than ArrayList to implement random access.

LinkedList
A LinkedList is ordered by index position like Arrays, except the elements are doubly linked to each other. This linkage gives you new methods for adding and removing form beginning and end which makes it an easy choice for implementing a stack or queue.A LinkedList iterates more slowly than the ArrayList but is a good choice when you need faster insertion and deletion. LinkedList class has been enhanced to implement java.util.Queue Interface thereby implementing common queue methods peek(), poll() and offer()

Set Interface

A set doesn’t allow duplicates and the equals() method takes care of determining whether two objects are identical. Following are the three Set implementations.

HashSet
A HashSet is an unsorted, unordered Collection.It uses HashCode of object being inserted, so more efficient your hashcode implementation the better access performance you will get. Use this class when you want a collection with no duplicates and you don’t care about order when you iterate through it.

LinkedHashSet
A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.

TreeSet 
The TreeSet is is a sorted collection based on the Red-Black tree structure, and guarantees that the
elements will be in ascending order, according to natural order. Optionally, you can construct a TreeSet with a constructor that lets you give the collection your own rules for what the order should be (rather than relying on the ordering defined by the elements’ class) by using a Comparable or Comparator. As of Java 6, TreeSet implements NavigableSet.

Map Interface
A Map is based on unique identifiers. You map a unique key (the ID) to a specific value, where both the key and the value are objects. The Map implementations let you do things like search for a value based on the key, ask for a collection of just the values, or ask for a collection of just the keys. Like Sets, Maps rely on the equals() method to determine whether two keys are the same or different.

HashMap
The HashMap is an unsorted, unordered Map. When you need a Map and you don’t care about the order (when you iterate through it), then HashMap is the way to go; the other maps add a little more overhead. Where the keys land in the Map is based on the key’s hashcode, so, like HashSet, the more efficient
your hashCode() implementation, the better access performance you’ll get. HashMap allows one null key and multiple null values in a collection.

Hashtable
Like Vector, Hashtable has existed from prehistoric Java times. Anyway, just as Vector is a synchronized counterpart to the sleeker, more modern ArrayList, Hashtable is the synchronized counterpart to HashMap. Remember that you don’t synchronize a class, so when we say that Vector and Hashtable are synchronized, we just mean that the key methods of the class are synchronized. Another difference, though, is that while HashMap lets you have null values as well as one null key, a Hashtable doesn’t let you have anything that’s null.

LinkedHashMap 
Like its Set counterpart, LinkedHashSet, the LinkedHashMap collection maintains insertion order (or, optionally, access order). Although it will be somewhat slower than HashMap for adding and removing elements, you can expect faster iteration with a LinkedHashMap.

TreeMap 
TreeMap is a sorted Map “sorted by the natural order of the elements.” Like TreeSet, TreeMap lets you define a custom sort order (via a Comparable or Comparator) when you construct a TreeMap, that specifies how the elements should be compared to one another when they’re being ordered. As of Java 6, TreeMap implements NavigableMap.

Queue Interface
A Queue is designed to hold a list of things to be processed in some way. Although other orders are possible, queues are typically thought of as FIFO (first-in, first-out). Queues support all of the standard Collection methods and they also add methods to add and subtract elements and review queue elements.

PriorityQueue
This class is new with Java 5. Since the LinkedList class has been enhanced to implement the Queue interface, basic queues can be handled with a LinkedList. The purpose of a PriorityQueue is to create a “priority-in, priority out” queue as opposed to a typical FIFO queue. A PriorityQueue’s elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements’ ordering represents their relative priority.