Collections Framework

Collection framework was not part of original Java release. Collections was added to J2SE 1.2. Prior to Java 2, Java provided  adhoc classes such as Dictionary, Vector, Stack and Properties to store and manipulates groups of objects. Collection framework provides many important classes and interfaces to collect and organize group of alike objects.

                  First introduced with the Java 2 platform, Standard Edition, version 1.2. The Collections Framework provides a well-designed set of interfaces and classes for storing and manipulating groups of data as a single unit, a collection. The framework provides a convenient API to many of the abstract data types familiar from computer science data structure curriculum: maps, sets, lists, trees, arrays, hash tables, and other collections. Because of their object-oriented design, the Java classes in the Collections Framework encapsulate both the data structures and the algorithms associated with these abstractions. The framework provides a standard programming interface to many of the most common abstractions, without burdening the programmer with too many procedures and interfaces. The operations supported by the collections framework nevertheless permit the programmer to easily define higher-level data abstractions, such as stacks, queues, and thread-safe collections.


Java Collections frameworks have following benefits:

  • Reduced Development Effort – It comes with almost all common types of collections and useful methods to iterate and manipulate the data. So we can concentrate more on business logic rather than designing our collection APIs.
  • Increased Quality – Using core collection classes that are well tested increases our program quality rather than using any home developed data structure.
  • Reusability and Interoperability
  • Reduce effort – to learn any new API if we use core collection API classes.

Why Collections were made Generic?

Generics added type safety to Collection framework. Earlier collections stored Object class references. Which means any collection could store any type of object. Hence there were chances of storing incompatible types in a collection, which could result in run time mismatch. Hence Generics was introduced, now you can explicitly state the type of object being stored.


What is Java Collections API?

Java Collections framework API is a unified architecture for representing and manipulating collections. The API contains Interfaces, Implementations & Algorithm to help java programmer in everyday programming. In nutshell, this API does 6 things at high level

  • Reduces programming efforts. – Increases program speed and quality.
  • Allows interoperability among unrelated APIs.
  • Reduces effort to learn and to use new APIs.
  • Reduces effort to design new APIs.
  • Encourages & Fosters software reuse.

To be specific, There are six collection java interfaces. The most basic interface is Collection. Three interfaces extend Collection: Set, List, and SortedSet. The other two collection interfaces, Map and SortedMap, do not extend Collection, as they represent mappings rather than true collections.


Why doesn’t Collection extend Cloneable and Serializable?

From Sun FAQ Page: Many Collection implementations (including all of the ones provided by the JDK) will have a public clone method, but it would be mistake to require it of all Collections.

For example, what does it mean to clone a Collection that’s backed by a terabyte SQL database? Should the method call cause the company to requisition a new disk farm? Similar arguments hold for serializable.

If the client doesn’t know the actual type of a Collection, it’s much more flexible and less error prone to have the client decide what type of Collection is desired, create an empty Collection of this type, and use the addAll method to copy the elements of the original collection into the new one.

Note on Some Important Terms 

Synchronized means only one thread can modify a hash table at one point of time. Basically, it means that any thread before performing an update on a hashtable will have to acquire a lock on the object while others will wait for lock to be released.

Fail-fast is relevant from the context of iterators. If an iterator has been created on a collection object and some other thread tries to modify the collection object “structurally”, a concurrent modification exception will be thrown. It is possible for other threads though to invoke “set” method since it doesn’t modify the collection “structurally”. However, if prior to calling “set”, the collection has been modified structurally, “IllegalArgumentException” will be thrown.


Collection’s hierarchy

cfh


Difference between Set and List?

The most noticeable differences are :

  • Set is unordered collection where List is ordered collection based on zero based index.
  • List allow duplicate elements but Set does not allow duplicates.
  • List does not prevent inserting null elements (as many you like), but Set will allow only one null element.

ArrayList Class

ArrayList class extends AbstractList class and implements the List interface.

ArrayList supports dynamic array that can grow as needed. ArrayList has three constructors.

  • ArrayList()
  • ArrayList( Collection C )
  • ArrayList( int capacity )
  • ArrayLists are created with an initial size, when this size is exceeded, it gets enlarged automatically.
  • It can contain Duplicate elements and maintains the insertion order.
  • ArrayLists are not synchronized.

Example of ArrayList

Getting Array from an ArrayList

toArray() method is used to get an araay containing all the contents of the list. Following are the reasons why you must obtain array from your ArrayList whenever required.

To obtain faster processing.

To pass array to methods who do not accept Collectionn as arguments.

To integrate and use collections with legacy code.


LinkedList Class

  • LinkedList class extendsAbstractSequentialList and implements List,Deque and Queue
  • It can be used as List, stack or Queue as it implements all the related interfaces.
  • It can contain duplicate elements and is not synchronized.

Example of LinkedList class


What is the difference between ArrayList and LinkedList? (ArrayList vs LinkedList.)

Ø  java.util.ArrayList and java.util.LinkedList are two Collections classes used for storing lists of object references Here are some key differences:

Ø  ArrayList uses primitive object array for storing objects whereas LinkedList is made up of a chain of nodes. Each node stores an element and the pointer to the next node. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier.

Ø  ArrayList implements the RandomAccess interface, and LinkedList does not. The commonly used ArrayList implementation uses primitive Object array for internal storage. Therefore an ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method. Note that the get method is implemented for LinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. For a LinkedList, there’s no fast way to access the Nth element of the list.

Ø  Adding and deleting at the start and middle of the ArrayList is slow, because all the later elements have to be copied forward or backward. (Using System.arrayCopy()) Whereas Linked lists are faster for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node.

Ø  Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next and previous pointers.

Ø  ArrayList may also have a performance issue when the internal array fills up. The arrayList has to create a new array and copy all the elements there. The ArrayList has a growth algorithm of (n*3)/2+1, meaning that each time the buffer is too small it will create a new one of size (n*3)/2+1 where n is the number of elements of the current buffer. Hence if we can guess the number of elements that we are going to have, then it makes sense to create a arraylist with that capacity during object creation (using construtor new ArrayList(capacity)). Whereas LinkedLists should not have such capacity issues.


Vector Class

The Vector class implements a growable array of objects. Similar to array, elements of Vector can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

Vector is synchronized which means it is suitable for thread-safe operations but it gives poor performance when used in multi-thread environment. It is recommended to use ArrayList (it is non-synchronized, gives good performance)  in place of Vector when there is no need of thread-safe operations. Here is the list of tutorials published on Vector class.

Below given are the list of constructors provided by the vector class.

SR.NO Constructor and Description
1 Vector( )

This constructor creates a default vector, which has an initial size of 10

2 Vector(int size)

This constructor accepts an argument that equals to the required size, and creates a vector whose initial capacity is specified by size:

3 Vector(int size, int incr)

This constructor creates a vector whose initial capacity is specified by size and whose increment is specified by incr. The increment specifies the number of elements to allocate each time that a vector is resized upward

4 Vector(Collection c)

creates a vector that contains the elements of collection c

Apart from the methods inherited from its parent classes, Vector defines the following methods:

SN Methods with Description
1 void add(int index, Object element)

Inserts the specified element at the specified position in this Vector.

2 boolean add(Object o)

Appends the specified element to the end of this Vector.

3 boolean addAll(Collection c)

Appends all of the elements in the specified Collection to the end of this Vector, in the order that they are returned by the specified Collection’s Iterator.

4 boolean addAll(int index, Collection c)

Inserts all of the elements in in the specified Collection into this Vector at the specified position.

5 void addElement(Object obj)

Adds the specified component to the end of this vector, increasing its size by one.

6 int capacity()

Returns the current capacity of this vector.

7 void clear()

Removes all of the elements from this Vector.

8 Object clone()

Returns a clone of this vector.

9 boolean contains(Object elem)

Tests if the specified object is a component in this vector.

10 boolean containsAll(Collection c)

Returns true if this Vector contains all of the elements in the specified Collection.

11 void copyInto(Object[] anArray)

Copies the components of this vector into the specified array.

12 Object elementAt(int index)

Returns the component at the specified index.

13 Enumeration elements()

Returns an enumeration of the components of this vector.

14 void ensureCapacity(int minCapacity)

Increases the capacity of this vector, if necessary, to ensure that it can hold at least the number of components specified by the minimum capacity argument.

15 boolean equals(Object o)

Compares the specified Object with this Vector for equality.

16 Object firstElement()

Returns the first component (the item at index 0) of this vector.

17 Object get(int index)

Returns the element at the specified position in this Vector.

18 int hashCode()

Returns the hash code value for this Vector.

19 int indexOf(Object elem)

Searches for the first occurence of the given argument, testing for equality using the equals method.

20 int indexOf(Object elem, int index)

Searches for the first occurence of the given argument, beginning the search at index, and testing for equality using the equals method.

21 void insertElementAt(Object obj, int index)

Inserts the specified object as a component in this vector at the specified index.

22 boolean isEmpty()

Tests if this vector has no components.

23 Object lastElement()

Returns the last component of the vector.

24 int lastIndexOf(Object elem)

Returns the index of the last occurrence of the specified object in this vector.

25 int lastIndexOf(Object elem, int index)

Searches backwards for the specified object, starting from the specified index, and returns an index to it.

26 Object remove(int index)

Removes the element at the specified position in this Vector.

27 boolean remove(Object o)

Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.

28 boolean removeAll(Collection c)

Removes from this Vector all of its elements that are contained in the specified Collection.

29 void removeAllElements()

Removes all components from this vector and sets its size to zero.

30 boolean removeElement(Object obj)

Removes the first (lowest-indexed) occurrence of the argument from this vector.

31 void removeElementAt(int index)

removeElementAt(int index)

32 protected void removeRange(int fromIndex, int toIndex)

Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.

33 boolean retainAll(Collection c)

Retains only the elements in this Vector that are contained in the specified Collection.

34 Object set(int index, Object element)

Replaces the element at the specified position in this Vector with the specified element.

35 void setElementAt(Object obj, int index)

Sets the component at the specified index of this vector to be the specified object.

36 void setSize(int newSize)

Sets the size of this vector.

37 int size()

Returns the number of components in this vector.

38 List subList(int fromIndex, int toIndex)

Returns a view of the portion of this List between fromIndex, inclusive, and toIndex, exclusive.

39 Object[] toArray()

Returns an array containing all of the elements in this Vector in the correct order.

40 Object[] toArray(Object[] a)

Returns an array containing all of the elements in this Vector in the correct order; the runtime type of the returned array is that of the specified array.

41 String toString()

Returns a string representation of this Vector, containing the String representation of each element.

42 void trimToSize()

Trims the capacity of this vector to be the vector’s current size.

Example of Vector


Difference between Vector and ArrayList? What is the Vector class?

Ø  Vector and ArrayList both classes are implemented using dynamically resizable arrays, providing fast random access and fast traversal. ArrayList and Vector class both implement the List interface. Both the classes are member of Java collection framework, therefore from an API perspective, these two classes are very similar. However, there are still some major differences between the two. Below are some key differences

Ø  Vector is a legacy class which has been retrofitted to implement the List interface since Java 2 platform v1.2

Ø  Vector is synchronized whereas ArrayList is not. Even though Vector class is synchronized, still when you want programs to run in multithreading environment using ArrayList with Collections.synchronizedList() is recommended over Vector.

Ø  ArrayList has no default size while vector has a default size of 10.

Ø  The Enumerations returned by Vector’s elements method are not fail-fast. Whereas ArraayList does not have any method returning Enumerations.


Stack Class

Stack is a subclass of Vector that implements a standard last-in, first-out stack.

Stack only defines the default constructor, which creates an empty stack. Stack includes all the methods defined by Vector, and adds several of its own.

Stack( )

Apart from the methods inherited from its parent class Vector, Stack defines following methods:

SN Methods with Description
1 boolean empty()

Tests if this stack is empty. Returns true if the stack is empty, and returns false if the stack contains elements.

2 Object peek( )

Returns the element on the top of the stack, but does not remove it.

3 Object pop( )

Returns the element on the top of the stack, removing it in the process.

4 Object push(Object element)

Pushes element onto the stack. element is also returned.

5 int search(Object element)

Searches for element in the stack. If found, its offset from the top of the stack is returned. Otherwise, .1 is returned.

Example:

The following program illustrates several of the methods supported by this collection:


 Accessing a Collection

To access, modify or remove any element from any collection we need to first find the element, for which we have to cycle throught the elements of the collection. There are three possible ways to cycle through the elements of any collection.

  1. Using Iterator interface
  2. Using ListIterator interface
  3. Using for-each loop

Accessing elements using Iterator

Iterator Interface is used to traverse a list in forward direction, enabling you to remove or modify the elements of the collection. Each collection classes provide iterator() method to return an iterator.

Accessing element using ListIterator

ListIterator Interface is used to traverse a list in both forward and backward direction. It is available to only those collections that implement the List Interface.

Using for-each loop

for-each version of for loop can also be used for traversing each element of a collection. But this can only be used if we don’t want to modify the contents of a collection and we don’t want any reverse access.for-each loop can cycle through any collection of object that implements Iterable interface.


What is the difference between java.util.Iterator and java.util.ListIterator?

Ø  Iterator : Enables you to traverse through a collection in the forward direction only, for obtaining or removing elements

Ø  ListIterator : extends Iterator, and allows bidirectional traversal of list and also allows the modification of elements.


HashSet Class

  1. HashSet extendsAbstractSet class and implements the Set
  2. It creates a collection that uses hash table for storage.
  3. HashSet does not maintain any order of elements.

Example of HashSet class


LinkedHashSet Class

  1. LinkedHashSet class extendsHashSet class
  2. LinkedHashSet maintains a linked list of entries in the set.
  3. LinkedHashSet stores elements in the order in which elements are inserted.

Example of LinkedHashSet class


TreeSet Class

  1. It extendsAbstractSet class and implements the NavigableSet
  2. It stores elements sorted ascending order.
  3. Uses a Tree structure to store elements.
  4. Access and retrieval times are quite fast.
  5. It has four Constructors.

ü  TreeSet()

ü  TreeSet( Collection C )

ü  TreeSet( Comparator comp )

ü  TreeSet( SortedSet ss )


Hashtable class

  1. Like HashMap, Hashtable also stores key/value pair in hashtable. However neitherkeys nor values can be null.
  2. There is one more difference betweenHashMap and Hashtable that is Hashtable is synchronized while HashMap is not.
  3. Hashtable has following four constructor

4.      Hashtable()

5.      Hashtable(int size)

6.      Hashtable(int size, float fillratio)

7.      Hashtable(Map< ? extends K, ? extends V> m)

 

Example of Hashtable

Difference between HashMap and Hashtable

Hashtable HashMap
Hashtable class is synchronized. HastMap is not synchronize.
Because of Thread-safe, Hashtable is slower than HashMap HashMap works faster.
Neither key nor values can be null Both key and values can be null
Order of table remain constant over time. does not guarantee that order of map remain constant over time.


Properties Class

  1. Propertiesclass extends Hashtable
  2. It is used to maintain list of value in which both key and value areString
  3. Propertiesclass define two constructor

4.      Properties()

5.      Properties(Properties default)

  1. One advantage ofProperties over Hashtable is that we can specify a default property that will be useful when no value is associated with a certain key.

Example of Properties class


The Queue Interface

It extends collection interface and defines behaviour of queue, that is first-in, first-out. It’s general declaration is,

interface Queue < E >

There are couple of new and interestin methods added by this interface. Some of them are mentioned in below table.

Methods Description
poll() removes element at the head of the queue and returns null if queue is empty
remove() removes element at the head of the queue and throwsNoSuchElementException if queue is empty
peek() returns the element at the head of the queue without removing it. Returns null if queue is empty
element() same as peek(), but throws NoSuchElementException if queue is empty
offer( E obj ) Adds object to queue.

The Dequeue Interface

It extends Queue interface and declares behaviour of a double-ended queue. Its general declaration is,

interface Dequeue < E >

Double ended queues can function as simple queues as well as like standard Stacks.



MAP Interface

A Map stores data in key and value association. Both key and values are objects. The key must be unique but the values can be duplicate. Although Maps are a part of Collection Framework, they can not actually be called as collections because of some properties that they posses. However we can obtain a collection-view of maps.

Interface Description
Map Maps unique key to value.
Map.Entry Describe an element in key and value pair in a map. This is an inner class of map.
NavigableMap Extends SortedMap to handle the retrienal of entries based on closest match searches
SortedMap Extends Map so that key are maintained in an ascending order.

map

Commonly used Methods defined by Map

  • booleancontainsKey(Object k): returns true if map contain k as key. Otherwise false.
  • Objectget(Object k) : returns values associated with the key k.
  • Objectput(Object k, Object v) : stores an entry in map.
  • ObjectputAll(Map m) : put all entries from m in this map.
  • SetkeySet() : returns Set that contains the key in a map.
  • SetentrySet() : returns Set that contains the entries in a map.


HashMap class

  1. HashMap class extendsAbstractMap and implements Map
  2. It uses ahashtable to store the map. This allows the execution time of get() and put() to remain same.
  3. HashMap has four constructor.

4.      HashMap()

5.      HashMap(Map< ? extends k, ? extends V> m)

6.      HashMap(int capacity)

7.      HashMap(int capacity, float fillratio)

  1. HashMap does not maintain order of its element.


TreeMap class

  1. TreeMap class extendsAbstractMap and implements NavigableMap
  2. It creates Map, stored in a tree structure.
  3. ATreeMap provides an efficient means of storing key/value pair in efficient order.
  4. It provides key/value pairs in sorted order and allows rapid retrieval.

Example


LinkedHashMap class

  1. LinkedHashMapextends HashMap
  2. It maintains a linked list of entries in map in order in which they are inserted.
  3. LinkedHashMapdefines the following constructor

4.      LinkedHashMap()

5.      LinkedHashMap(Map< ? extends k, ? extends V> m)

6.      LinkedHashMap(int capacity)

7.      LinkedHashMap(int capacity, float fillratio)

8.      LinkedHashMap(int capacity, float fillratio, boolean order)

  1. It adds one new methodremoveEldestEntry(). This method is called by put() and putAll() By default this method does nothing. However we can override this method to remove oldest element in the map. Syntax

10.  protected boolean removeEldestEntry(Map.Entry e)

 


WeakHashMap Class

WeakHashMap is an implementation of the Map interface that stores only weak references to its keys. Storing only weak references allows a key-value pair to be garbagecollected when its key is no longer referenced outside of the WeakHashMap.

This class provides the easiest way to harness the power of weak references. It is useful for implementing “registry-like” data structures, where the utility of an entry vanishes when its key is no longer reachable by any thread.

The WeakHashMap functions identically to the HashMap with one very important exception: if the Java memory manager no longer has a strong reference to the object specified as a key, then the entry in the map will be removed.

Weak Reference: If the only references to an object are weak references, the garbage collector can reclaim the object’s memory at any time.it doesn’t have to wait until the system runs out of memory. Usually, it will be freed the next time the garbage collector runs.

Following is the list of constructors supported by the WeakHashMap class.

SN Constructors and Description
1 WeakHashMap()

This constructor constructs a new, empty WeakHashMap with the default initial capacity (16) and the default load factor (0.75).

2 WeakHashMap(int initialCapacity)

This constructor constructs a new, empty WeakHashMap with the given initial capacity and the default load factor, which is 0.75.

3 WeakHashMap(int initialCapacity, float loadFactor) This constructor constructs a new, empty WeakHashMap with the given initial capacity and the given load factor.
4 WeakHashMap(Map t)

This constructor constructs a new WeakHashMap with the same mappings as the specified Map.

Apart from the methods inherited from its parent classes, TreeMap defines the following methods:

SN Methods with Description
1 void clear()

Removes all mappings from this map.

2 boolean containsKey(Object key)

Returns true if this map contains a mapping for the specified key.

3 boolean containsValue(Object value)

Returns true if this map maps one or more keys to the specified value.

4 Set entrySet()

Returns a collection view of the mappings contained in this map

5 Object get(Object key)

Returns the value to which the specified key is mapped in this weak hash map, or null if the map contains no mapping for this key.

6 boolean isEmpty()

Returns true if this map contains no key-value mappings.

7 Set keySet()

Returns a set view of the keys contained in this map.

8 Object put(Object key, Object value)

Associates the specified value with the specified key in this map.

9 void putAll(Map m)

Copies all of the mappings from the specified map to this map These mappings will replace any mappings that this map had for any of the keys currently in the specified map.

10 Object remove(Object key)

Removes the mapping for this key from this map if present.

11 int size()

Returns the number of key-value mappings in this map.

12 Collection values()

Returns a collection view of the values contained in this map.


IdentityHashMap Class

This class implements AbstractMap. It is similar to HashMap except that it uses reference equality when comparing elements.

This class is not a general-purpose Map implementation. While this class implements the Map interface, it intentionally violates Map’s general contract, which mandates the use of the equals method when comparing objects.

This class is designed for use only in the rare cases wherein reference-equality semantics are required.

This class provides constant-time performance for the basic operations (get and put), assuming the system identity hash function (System.identityHashCode(Object)) disperses elements properly among the buckets.

This class has one tuning parameter (which affects performance but not semantics): expected maximum size. This parameter is the maximum number of key-value mappings that the map is expected to hold.

Below given is the list of the constructors supported by the IdentityHashMap.

SN Constructors and Description
1 IdentityHashMap()

This constructor constructs a new, empty identity hash map with a default expected maximum size (21).

2 IdentityHashMap(int expectedMaxSize)

This constructor constructs a new, empty IdentityHashMap with the specified expected maximum size

3 IdentityHashMap(Map m)

This constructor constructs a new identity hash map containing the keys-value mappings in the specified map

Apart from the methods inherited from its parent classes, IdentityHashMap defines following methods:

SN Methods with Description
1 void clear()

Removes all mappings from this map.

2 Object clone()

Returns a shallow copy of this identity hash map: the keys and values themselves are not cloned.

3 boolean containsKey(Object key)

Tests whether the specified object reference is a key in this identity hash map.

4 boolean containsValue(Object value)

Tests whether the specified object reference is a value in this identity hash map.

5 Set entrySet()

Returns a set view of the mappings contained in this map.

6 boolean equals(Object o)

Compares the specified object with this map for equality.

7 Object get(Object key)

Returns the value to which the specified key is mapped in this identity hash map, or null if the map contains no mapping for this key.

8 int hashCode()

Returns the hash code value for this map.

9 boolean isEmpty()

Returns true if this identity hash map contains no key-value mappings.

10 Set keySet()

Returns an identity-based set view of the keys contained in this map.

11 Object put(Object key, Object value)

Associates the specified value with the specified key in this identity hash map.

12 void putAll(Map t)

Copies all of the mappings from the specified map to this map These mappings will replace any mappings that this map had for any of the keys currently in the specified map.

13 Object remove(Object key)

Removes the mapping for this key from this map if present.

14 int size()

Returns the number of key-value mappings in this identity hash map.

15 Collection values()

Returns a collection view of the values contained in this map.