The Java Collections Framework

The Java Collections Framework

Concept

Enum

Enum is the superclass of all enumerated types,  it is simply the same way that Object is the super class of everything.

Remember: Enum does not extends to Object class.

Enumeration is an interface which is hardly used any more. It is rather like Iterator.

Enumeration has been replaced by Iterator since Java 1.2.

Benefits:

1) Enum is type-safe you can’t assign anything else other than predefined Enum constants to an Enum variable.

Remeber: It will warn you at  compiler time if you try assign other type.

2) Enum defined its own name-space.

3) Enum can be used in switch statement like int or char primitive data type.

4) Adding new constants on Enum without breaking any existing code.

package com.easycasestudy.collection.enumtest;
public class EnumTest {
 public enum Product {
 WATCH, MOBILE, KINDLE, IPHONE, IPAD
 }

 Product productName;

 public EnumTest(Product productName) {
 this.productName = productName;
 }

 public void ProductDetails() {
 switch (productName) {
 case WATCH:
 System.out.println("Item display are watches.");
 break;
 case MOBILE:
 System.out.println("Item display are Mobiles.");
 break;
 case KINDLE:
 case IPHONE:
 System.out.println("Item display are iPhone");
 break;
 default:
 System.out.println("KINDLE - Item displayed.");
 break;
 }
 }

 public static void main(String[] args) {
 EnumTest watch = new EnumTest(Product.WATCH);
 watch.ProductDetails();
 EnumTest mobile = new EnumTest(Product.MOBILE);
 mobile.ProductDetails();
 EnumTest kindle = new EnumTest(Product.KINDLE);
 kindle.ProductDetails();
 EnumTest iPhone = new EnumTest(Product.IPHONE);
 iPhone.ProductDetails();
 EnumTest ipad = new EnumTest(Product.IPAD);
 ipad.ProductDetails();
 }
}

MAP

HashMap are key value pair collection framework.

DIFFERENCE:

HashMap HashTable
Thread Un Safe Synchronize/Thread Safe
Allows one null keys and any number of null values Not allowed
Can be Iterated through Iterator only class other than vector which uses enumerator to iterate the values of HashTable object
Fail Fast Fail Safe
Faster Slower than HashMap

Key Points:-

  1.       Doesn’t maintain any Insertion Order
  2.      Both implements Map Interface
  3.       Both works on the principle of Hashing

Remember: HashMap works on principle of hashing, HashMap has put(key, value) and get(key) method for storing and retrieving any Objects from HashMap. Whenever Key and Value object is passed to put() method on Java HashMap, HashMap implementation calls  first hashCode method on Key object and applies returned hashcode into its own hashing function to find a bucket location for storing Entry object, important point to mention is that HashMap in Java stores both key and value object as Map.Entry class in bucket which is essential to understand the retrieving logic. While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key.

Case Study 2

Problem Statement

What will happen if two different HashMap  key objects have same hashcode and how you will retrieve it?

Solutions

They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap . After finding bucket location , we will have to call keys.equals() method to identify correct node in LinkedList and return associated value object for that key in Java HashMap.

For  Example:-

package com.easycasestudy.collection.map;

public class ProductVo {

 private String item;
 private int price;
 private int qty;

 public ProductVo(String item, int price, int quantity) {
 this.item = item;
 this.price = price;
 this.qty = quantity;
 }

 public String getItem() {
 return item;
 }

 public void setItem(String item) {
 this.item = item;
 }

 public int getPrice() {
 return price;
 }

 public void setPrice(int price) {
 this.price = price;
 }

 public int getQty() {
 return qty;
 }

 public void setQty(int qty) {
 this.qty = qty;
 }

 public int hashCode() {
 int hashcode = 0;
 hashcode = price * 20;
 hashcode = qty * 4;
 hashcode += item.hashCode();
 System.out.println("HashCode:::" + hashcode);
 return hashcode;
 }

 public boolean equals(Object obj) {
 if (obj instanceof ProductVo) {
 ProductVo pp = (ProductVo) obj;
 return (pp.item.equals(this.item) && pp.price == this.price && pp.qty == this.qty);
 } else {
 return false;
 }
 }

}

Test Class

package com.easycasestudy.collection.map;

import java.util.HashMap;

public class MapTest {

 public static void main(String[] args) {
 HashMap<ProductVo, String> hm = new HashMap<ProductVo, String>();

 hm.put(new ProductVo("Banana", 2,10),"Apple");
 hm.put(new ProductVo("Banana", 1,20),"Sun");
 hm.put(new ProductVo("Banana", 4, 0),"IBM");
 hm.put(new ProductVo("Banana", 3, 5),"Microsoft");
 
 ProductVo key = new ProductVo("Banana", 4,0);
 System.out.println("Does key available? " + hm.containsKey(key));
 System.out.println("Does key available? " + hm.get(key));

 }

}

Note: All the object has same hashcode but value is different.

Set

A Set is a collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. HashSet,SortedSet and TreeSet are the commnly used class which implements Set interface.

SortedSet – It is an interface which extends Set. A the name suggest , the interface allows the data to be iterated in the ascending order or sorted on the basis of Comparator or Comparable interface. All elements inserted into the interface must implement Comparable or Comparator interface.

TreeSet – It is the implementation of SortedSet interface.This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains). The class is not synchronized.

HashSet: This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets

keypoint:-

  1. 1.       A null element can be added only if the set contains one element because when a second element is added then as per set definition a check is made to check duplicate value and comparison with null element will throw NullPointerException.
  2.      HashSet is based on hashMap and can contain null element.
  3.       java.util.EnumSet is Set implementation to use with enum types. All of the elements in an enum set must come from a single enum type that is specified, explicitly or implicitly, when the set is created. EnumSet is not synchronized and null elements are not allowed. It also provides some useful methods like copyOf(Collection c), of(E first, E… rest) and complementOf(EnumSet s).

List

Elements can be inserted or accessed by their position in the list, using a zero-based index.

A list may contain duplicate elements.

In addition to the methods defined by Collection, List defines some of its own, which are summarized in the following below Table.

Several of the list methods will throw an UnsupportedOperationException if the collection cannot be modified, and a ClassCastException is generated when one object is incompatible with another.

Difference:-

Criteria ArrayList Vector
Synchronization No Yes
Resize ArrayList grow by half of its size when resize Double the size of itself
Performance Faster than Vector Slower than ArrayList
Fail Fast Iterator and listIterator returned by ArrayList are fail-fast. Enumeration returned by Vector is not fail-fast

 

Case Study

Problem Statement

Suppose Java doesn’t have Collection Framework and we have to define ArrayList like functionality. What will be the approach and how you will implement it.

Solutions

Just looked at the ArrayList API (https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html)  it contains following functionality which is being widely used:-

  1. Add Object
  2. Remove Object
  3. ArrayList is grow-able array.
  4. Size

Implementation:

package com.easycasestudy.collection.list;

import java.util.Arrays;

public class EasyCSArrayList {

 /**
 * Default initial capacity.
 */
 private static final int DEFAULT_CAPACITY = 10;

 /**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

 /**
 * The array buffer into which the elements of the ArrayList are stored. The
 * capacity of the ArrayList is the length of this array buffer. Any empty
 * ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be
 * expanded to DEFAULT_CAPACITY when the first element is added.
 */
 transient Object[] elementData; // non-private to simplify nested class
 // access

 protected transient int modCount = 0;
 /**
 * The maximum size of array to allocate. Some VMs reserve some header words
 * in an array. Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 /**
 * The size of the ArrayList (the number of elements it contains).
 */
 private int size;

 /**
 * Constructs an empty list with an initial capacity of ten.
 */
 public EasyCSArrayList() {
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

 /**
 * Appends the specified element to the end of this list.
 */
 public boolean add(Object e) {
 ensureCapacityInternal(size + 1); // Increments modCount!!
 elementData[size++] = e;
 return true;
 }

 private void ensureCapacityInternal(int minCapacity) {
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }

 ensureExplicitCapacity(minCapacity);
 }

 private void ensureExplicitCapacity(int minCapacity) {
 modCount++;

 // overflow-conscious code
 if (minCapacity - elementData.length > 0)
 grow(minCapacity);
 }

 private void grow(int minCapacity) {
 // overflow-conscious code
 int oldCapacity = elementData.length;
 int newCapacity = oldCapacity + (oldCapacity >> 1);
 if (newCapacity - minCapacity < 0)
 newCapacity = minCapacity;
 if (newCapacity - MAX_ARRAY_SIZE > 0)
 newCapacity = hugeCapacity(minCapacity);
 // minCapacity is usually close to size, so this is a win:
 elementData = Arrays.copyOf(elementData, newCapacity);
 }

 private static int hugeCapacity(int minCapacity) {
 if (minCapacity < 0) // overflow
 throw new OutOfMemoryError();
 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
 }

 public boolean remove(Object o) {
 for (int index = 0; index < size; index++)
 if (o.equals(elementData[index])) {
 fastRemove(index);
 return true;
 }
 return false;
 }

 /*
 * Private remove method that skips bounds checking and does not return the
 * value removed.
 */
 private void fastRemove(int index) {
 modCount++;
 int numMoved = size - index - 1;
 if (numMoved > 0)
 System.arraycopy(elementData, index + 1, elementData, index, numMoved);
 elementData[--size] = null; // clear to let GC do its work
 }

 /**
 * Returns the number of elements in this list.
 */
 public int size() {
 return size;
 }

 /**
 * Returns the element at the specified position in this list.
 *
 */
 public Object get(int index) {

 return elementData[index];
 }

}

 

Test Class

package com.easycasestudy.collection.list;

public class EasyCSArrayListTest {

 public static void main(String[] args) {
 EasyCSArrayList objArrayList = new EasyCSArrayList();
 
 objArrayList.add("String1");
 objArrayList.add("String12");
 objArrayList.add("String13");
 objArrayList.add("String14");
 objArrayList.add("String15");
 objArrayList.add("String16");
 objArrayList.add("String17");
 
 System.out.println(objArrayList.size());
 
 for(int i=0; i<objArrayList.size();i++)
 {
 System.out.println(objArrayList.get(i));
 }
 System.out.println(objArrayList.remove("String1"));
 System.out.println(objArrayList.size());

 }

}

Fail Fast

This is relatively new collection interview questions and can become trick if you hear the term fail-fast and fail-safe first time. Fail-fast Iterators throws ConcurrentModificationException when one Thread is iterating over collection object and other thread structurally modify Collection either by adding, removing or modifying objects on underlying collection. They are called fail-fast because they try to immediately throw Exception when they encounter failure.

Points to Remember:

  1. Although Map interface and it’s implementations are part of Collections Framework but Map are not collections and collections are not Map. Hence Map doesn’t extend Collection interface.
  2. The IdentityHashMap uses == for equality checking instead of equals(). This can be used for both performance reasons, if you know that two different elements will never be equals and for preventing spoofing, where an object tries to imitate another.
  3. ArrayList is an index based data structure backed by Array, so it provides random access to it’s elements with performance as O(1) but LinkedList stores data as list of nodes where every node is linked to it’s previous and next node. So even though there is a method to get the element using index, internally it traverse from start to reach at the index node and then return the element, so performance is O(n) that is slower than ArrayList.
  4. Insertion, addition or removal of an element is faster in LinkedList compared to ArrayList because there is no concept of resizing array or updating index when element is added in middle.LinkedList consumes more memory than ArrayList because every node in LinkedList stores reference of previous and next elements.
  5. Comparable and Comparator interfaces are used to sort collection or array of objects. Comparable interface is used to provide the natural sorting of objects and we can use it to provide sorting based on single logic. Comparator interface is used to provide different algorithms for sorting and we can chose the comparator we want to use to sort the given collection of objects.