Java Collection Framework

Java Collection Framework (java.util.* package) is a unified architecture for representing and manipulating collections. This post is a quick note of my knowledge about Java Collection Framework that covers frequently used java data structure to store a group of elements and/or key-value pairs. In the java.util framework, there are two major camps - Collections & Map.

To illustrate, I use solid lines to denote 'extends', and dash lines to denote 'implements'. The way to use my note is to first go to the diagram looking for the specific class or interface, then read the brief blurb that'll remind you what the class or interface is about for the right data structure.

Collections<E>

In a nutshell, Collections Interface is for holding a collection of elements. Under Collections Interface, there are 3 major interfaces - Set, List, and Queue Interfaces. 

The following is a brief description of each in Collections:

Collections Interfaces:

Set<E>
  A collection that contains no duplicate elements.

SortedSet<E>
A Set that provides ordering on its elements using their natural ordering, or by a Comparator  provided at set creation time. 

NavigableSet<E>
A SortedSet with extra navigation methods reporting closest matches for given search targets. For example, methods lower(), floor(), ceiling(), and higher() return elements respectively less than, less than or equal, greater than or equal, and greater than a given element, 

List<E>
An sequenced collection that allows duplicate elements. You can add an element anywhere in the list, change an element anywhere in the list, or remove an element from any position in the list.

Queue<E>
A queue is similar to a List which is ordered, but you'll only ever touch elements at one end. All elements get inserted at the "end" and removed from or inspected at the "beginning" (or head) of the queue. Queue is a collection designed for holding elements prior to processing - insertion, extraction, and inspection operations. These processing methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (e.g. null or false).

Deque<E>
Pronounced "deck", is a double ended Queue that supports element insertion and removal at both ends.


Collections Class Implementation:

Set:

HashSet<E>
  A Set implementation without guarantees as to the iteration order of the set.

LinkedHashSet<E> 
  A Set implementation that maintains a doubly-linked list running through all of its entries, thus iterable.

TreeSet<E> A NavigableSet implementation based on a TreeSet. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time. For example, TreeSet<Map.Entry<K,V>> can be used to sort Map.entrySet() by values.

List:

ArrayList<E>
  A resizable-array implementation of the List. Not synchronized thus not thread-safe.

Vector<E>
  A resizable-array implementation of the List. Synchronized thus thread-safe.

Stack<E> 
  A Vector with extra 5 operations that allow a vector to be treated as a stack. The Stack class represents a last-in-first-out (LIFO) stack of objects. For example, use Stack<String> to evaluate Reverse Polish Notation.

LinkedList<E>
A Doubly-linked list implementation of the List and Queue interfaces.


Queue:

LinkedList<E>
A Doubly-linked list implementation of the List and Queue interfaces.
​
PriorityQueue<E>
A Queue implementation based on a Binary Heap (Complete Tree + Min Heap). You can put one in, and you can take out the current highest priority. Priorities can be any Comparable value. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time. A priority queue does not permit null elements.

Map<K,V>

Map Interface is for holding a collection of key-value pairs. Although HashMap is a class implementation of a Map which does not inherit from a Collections interface, but Map interface is still part of the overall Java Collection Framework (java.util.*).

Map Interfaces:

Map<K,V>
Key-value pairs.

SortedMap<K,V>
A Map that provides ordering on its keys or by a Comparator typically provided at sorted map creation time.

NavigableMap<K,V>
A SortedMap with extra navigation methods reporting closest matches for given search targets. For example, methods lowerEntry(), floorEntry(), ceilingEntry(), and higherEntry() return Map.Entry objects associated with keys respectively less than, less than or equal, greater than or equal, and greater than a given key.

ConcurrentMap<K,V>
  A Map with 3 extra methods added to Map<K,V>.


Map Class Implementations:

HashMap<K,V>
An unsynchronized Map implementation that permits null key or null value.

LinkedHashMap<K,V>
A HashMap with predictable iteration order (insertion order or access order).

Dictionary<K,V>
An abstract class of HashTable, thus you do not work with it directly. In fact, it is obsoleted. Please implement Map<K,V> interface instead.

HashTable<K,V>
A synchronized Map implementation that doesn't permit null key or null value, without predictable iteration order.

Properties<K,V>
Represents a persistent set of properties. The Properties can be saved to a stream or loaded from a stream. It supports reading and writing its content to a well-defined plain-text format (using load()/store()). It supports reading and writing its content to a well-defined XML-based format (using loadFromXML()/storeToXML()). It supports a default mechanism by providing another Properties instance at construction time. It only supports String keys and values. While it is technically a Map<Object,Object> actually storing non-String keys or values is strongly discouraged and unsupported. Each key and its corresponding value in the property list should be a string.

TreeMap<K,V>
A NavigableMap implementation. The elements are ordered using their natural ordering of its key, or by a Comparator provided at set creation time.

ConcurrentHashMap<K,V>
A thread-safe Map supporting full concurrency via internally divided 'segments' being synchronized upon for updates. ConcurrentHashMap permits multiple simultaneous readers and writers.

WeakHashMap<K,V>
Similar to a a HashMap, however, if a WeakHashMap key becomes garbage, its entry will be removed silently even though not necessarily immediately.

references

• Java Programming Tutorial The Collection Framework
• Priority Queues
• How ConcurrentHashMap Works Internally in Java