April 01, 2016

#Collections: Part 1- Java Collections Interview Questions and Answers


JDK 1.2 introduces a new framework for collections of objects, called the Java Collections Framework.

What are Collections?

A collection (sometimes called a container) is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data.

Why do we need Collections when we have Array?

  • Arrays are immutable, once defined you cannot increase the size of an Array.
  • Array is not really thread-safe.

What is the difference between a Collection and a Collections?

Both are part of the Java collection framework but serve a different purpose. The collection is the top-level interface of the Java collection framework whereas Collections is a utility class.

The collection interface is a member of java.util package and List, Set, and Queue are the main sub interfaces of this interface. JDK doesn’t provide any direct implementations of this interface. But, JDK provides direct implementations of its sub-interfaces. 

ArrayList, Vector, HashSet, LinkedHashSet, PriorityQueue are some indirect implementations of Collection interface. The map interface, which is also a part of the Java collection framework, doesn’t inherit from the Collection interface.

Collections is a utility class in java.util package. It consists of only static methods which are used to operate on objects of type Collection. e.g
  • Collections.max() : - This method returns the maximum element in the specified collection.
  • Collections.min() : - This method returns the minimum element in the given collection.
  • Collections.sort() : - This method sorts the specified collection.
  • Collections.shuffle() : - This method randomly shuffles the elements in the specified collection.
  • Collections.synchronizedCollection() : - This method returns synchronized collection backed by the specified collection.
  • Collections.binarySearch() : - This method searches the specified collection for the specified object using binary search algorithm.
  • Collections.disjoint() : - This method returns true if two specified collections have no elements in common.
  • Collections.copy() : - This method copies all elements from one collection to another collection.
  • Collections.reverse() : - This method reverses the order of elements in the specified collection.

What is the root interface in the collection hierarchy? 

The collection interface extends the Iterable interface(which is present in java.lang package not in java.util package). In Oracle doc, the iterable interface is not mentioned as a part of the Java Collections framework. So if the interviewer asks you this question, then you should answer that the root interface is as Collection interface (which is found in java.util package).


Why Collection doesn’t extend Cloneable and Serializable interfaces?

  • The Collection interface specifies groups of objects known as elements. Each concrete implementation of a Collection can choose its own way of how maintaining and ordering its elements. Some collections allow duplicate keys, while some other collections don’t. 
  • The semantics and the implications of either cloning or serialization come into play when dealing with actual implementations. That's why the concrete implementations of collections should decide how they can be cloned or serialized.

What is a Set in Java?

The java.util.Set is an interface, which is a subtype of the java.util.Collection interface with the following properties:
  • Duplicate elements are not allowed.
  • Elements are not stored in order. That means you cannot expect elements sorted in any order when iterating over elements of a Set.

What is the difference between a List and a Set?

Set contains only unique elements while List can contain duplicate elements. Set is unordered while List is ordered(maintains the order in which the objects are added).

What is the difference between a Map and a Set?

Map object has unique keys each containing some value, while Set contains only unique values.

What is a Java HashSet?

Java HashSet class is used to create a collection that uses a hash table for storage. It inherits the AbstractSet class and implements the Set interface. The important points about Java HashSet class are:
  • HashSet stores the elements by using a mechanism called hashing.
  • HashSet contains unique elements only.

HashSet class declaration:
public class HashSet < E > extends AbstractSet implements Set < E > , Cloneable, Serializable 

Constructors of HashSet:
  • HashSet() : Construct a new, empty HashSet whose backing HashMap has the default capacity (16) and loadFacor (0.75).
  • HashSet(Collection c) : It is used to initialize the hash set by using the elements of the collection c.
  • HashSet(int capacity): It is used to initialize the capacity of the hash set to the given integer value capacity. The capacity grows automatically as elements are added to the HashSet.
Methods of Java HashSet class:
  • void clear(): It is used to remove all of the elements from this set.
  • boolean contains(Object o): It is used to return true if this set contains the specified element.
  • boolean add(Object o): It is used to add the specified element to this set if it is not already present.
  • boolean isEmpty(): It is used to return true if this set contains no elements.
  • boolean remove(Object o): It is used to remove the specified element from this set if it is present.
  • Object clone(): It is used to return a shallow copy of this HashSet instance: the elements themselves are not cloned.
  • Iterator iterator(): It is used to return an iterator over the elements in this set.
  • int size(): It is used to return the number of elements in this set.

How does HashSet is implemented in Java?

HashSet is internally implemented using HashMap. Whenever we create a HashSet object, one HashMap object associated with it is also created. The elements we add into HashSet are stored as keys of this HashMap object, whereas the value associated with those keys will be a constant.

Every constructor of HashSet class internally creates one HashMap object.

private transient HashMap map;
public HashSet()
{
    map = new HashMap<>();
}
public HashSet(Collection c)
{
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
public HashSet(int initialCapacity, float loadFactor)
{
    map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity)
{
    map = new HashMap<>(initialCapacity);
}


Whenever we insert an element into HashSet using add() method, it actually creates an entry in the internally backing HashMap object with an element you have specified as its key and constant called “PRESENT” as its value. e.g:

private static final Object PRESENT = new Object();

add() method of HashSet class internally calls put() method of backing HashMap object by passing the element you have specified as a key and constant “PRESENT” as its value. e.g:

public boolean add(E e)
{
        return map.put(e, PRESENT)==null;
}

remove() method also works in the same manner.
public boolean remove(Object o)
{
        return map.remove(o)==PRESENT;
}

What is a Java LinkedHashSet?

Java LinkedHashSet class is a Linked list implementation of the Set interface. It inherits HashSet class and implements the Set interface. The important points about the Java LinkedHashSet class are:
  • Contains unique elements only like HashSet.
  • Provides all optional set operations, and permits null elements.
  • Maintains insertion order.
Declaration for java.util.LinkedHashSet class:
public class LinkedHashSet <  E > extends HashSet < E > implements Set < E > , Cloneable, Serializable 

Constructors of Java LinkedHashSet class
  • LinkedHashSet(): It is used to construct a default LinkedHashSet.
  • LinkedHashSet(Collection c): It is used to initialize the LinkedHashSet by using the elements of the collection c.
  • LinkedHashSet(int capacity): It is used initialize the capacity of the LinkedHashSet to the given integer value capacity.
  • LinkedHashSet(int capacity, float fillRatio): It is used to initialize both the capacity and the fill ratio (also called load capacity) of the hash set from its argument.  

What is a Java TreeSet?

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits AbstractSet class and implements NavigableSet interface. The objects of the TreeSet class are stored in ascending order. The important points about the Java TreeSet class are:
  • Contains unique elements only like HashSet.
  • Access and retrieval times are quite fast.
  • Maintains ascending order.
  • It doesn't preserve the insertion order of the elements.
  • It's not thread-safe.
  • TreeSet uses a self-balancing binary search tree, more specifically a Red-Black tree.
Declaration for java.util.TreeSet class.
public class TreeSet < E > extends AbstractSet < E > implements NavigableSet < E > , Cloneable, Serializable 
Constructors of Java TreeSet class
  • TreeSet(): It is used to construct an empty tree set that will be sorted in ascending order according to the natural order of the tree set.
  • TreeSet(Collection c): It is used to build a new tree set that contains the elements of the collection c.
  • TreeSet(Comparator comp): It is used to construct an empty tree set that will be sorted according to the given comparator.
  • TreeSet(SortedSet ss): It is used to build a TreeSet that contains the elements of the given SortedSet.
Methods of Java TreeSet class
  • boolean addAll(Collection c): It is used to add all of the elements in the specified collection to this set.
  • boolean contains(Object o): It is used to return true if this set contains the specified element.
  • boolean isEmpty(): It is used to return true if this set contains no elements.
  • boolean remove(Object o): It is used to remove the specified element from this set if it is present.
  • boolean add(Object o): It is used to add the specified element to this set if it is not already present.
  • void clear(): It is used to remove all of the elements from this set.
  • Object clone(): It is used to return a shallow copy of this TreeSet instance.
  • Object first(): It is used to return the first (lowest) element currently in this sorted set.
  • Object last(): It is used to return the last (highest) element currently in this sorted set.
  • int size(): It is used to return the number of elements in this set.

What is the difference between HashSet and TreeSet?

Main differences between HashSet and TreeSet are :
  • HashSet stores the object in random order, there is no guarantee that the element we inserted first in the HashSet will be printed first in the output. While elements are sorted according to the natural ordering of their elements in TreeSet. If the objects can not be sorted in the natural order then use compareTo() method to sort the elements of TreeSet object.
  • HashSet can store null objects while TreeSet can not store null objects. If one tries to store a null object in the TreeSet object, it will throw Null Pointer Exception.
  • HashSet takes constant time performance for the basic operations like add, remove contains, and size. While TreeSet guarantees log(n) time cost for the basic operations(add,remove,contains).
  • HashSet is much faster than TreeSet, as the performance time of HashSet is constant against the log time of TreeSet for most operations (add, remove,contains, and size). Iteration performance of HashSet mainly depends on the load factor and initial capacity parameters.
  • HashSet uses equals() method for comparison in java while TreeSet uses compareTo() method for maintaining ordering.

Can a null element add to a Treeset or HashSet?

A null element can not be added in Treeset, if you try to add it will throw NullPointerException. HashSet is based on hashMap and can contain null element.

Why can't we add BigDecimal to TreeSet?

Lets look at the below example:
BigDecimal b1= new BigDecimal("1.0");
BigDecimal b2= new BigDecimal("1.00");
System.out.println(b1.compareTo(b2)); //0
System.out.println(b1.equals(b2)); //false


equals() of BigDecimal will return false, because their precision is different, whereas compareTo() will return 0 because the "value" is the same.

Now lets do the same thing by using Double:
Double d1=new Double(1.0);
Double d2=new Double(1.00);
System.out.println(d1.compareTo(d2)); //0
System.out.println(d1.equals(d2)); //true

In above case, compareTo will return 0 and equals will return true.

So, if you store these two BigDecimal in HashSet you will end up with duplicates (violation of Set Contract), while if you store them in TreeSet you will end up with just 1 element because HashSet uses equals() to check duplicates while TreeSet uses compareTo() to check duplicates.

What is an ArrayList in Java?

Java ArrayList class uses a dynamic array for storing the elements. It inherits AbstractList class and implements the List interface. The important points about the Java ArrayList class are:
  • Java ArrayList class can contain duplicate elements.
  • Java ArrayList class maintains insertion order.
  • Java ArrayList class is nonsynchronized.
  • Java ArrayList allows random access because the array works on an index basis.
  • In the Java ArrayList class, manipulation is slow because a lot of shifting needs to occur if any element is removed from the array list.
  • ArrayList is a generic class, so we can parameterize it with any type we want.
  • It is good practice to use a generic interface List as a variable type because it decouples it from a particular implementation.
  • Random-access takes O(1) time
  • Adding element takes amortized constant time O(1)
  • Inserting/Deleting takes O(n) time
  • Searching takes O(n) time for an unsorted array and O(log n) for a sorted one
The declaration for java.util.ArrayList class.
public class ArrayList < E > extends AbstractList < E > implements List < E > , RandomAccess, Cloneable, Serializable 

Constructors of Java ArrayList
  • ArrayList(): It is used to build an empty array list.
  • ArrayList(Collection c): It is used to build an array list that is initialized with the elements of the collection c.
  • ArrayList(int capacity)  It is used to build an array list that has the specified initial capacity.
Methods of Java ArrayList
  • void add(int index, Object element): It is used to insert the specified element at the specified position index in a list.
  • boolean addAll(Collection c)  It is used to append all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
  • void clear() : It is used to remove all of the elements from this list.
  • int lastIndexOf(Object o)  It is used to return the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.
  • Object[] toArray(): It is used to return an array containing all of the elements in this list in the correct order.
  • Object[] toArray(Object[] a): It is used to return an array containing all of the elements in this list in the correct order.
  • boolean add(Object o) : It is used to append the specified element to the end of a list.
  • boolean addAll(int index, Collection c): It is used to insert all of the elements in the specified collection into this list, starting at the specified position.
  • Object clone(): It is used to return a shallow copy of an ArrayList.
  • int indexOf(Object o): It is used to return the index in this list of the first occurrence of the specified element, or -1 if the List does not contain this element.
  • void trimToSize(): It is used to trim the capacity of this ArrayList instance to be the list's current size.

What is the difference between Array and ArrayList in Java?

a. Array is static in size that is fixed length data structure, one can not change the length after creating the Array object. While ArrayList is dynamic in size. Each ArrayList object has instance variable capacity which indicates the size of the ArrayList. As elements are added to an ArrayList its capacity grows automatically.

b. ArrayList can not contain primitive data types (like int, float, double) it can only contain Objects, while Array can contain both primitive data types as well as objects. One gets a misconception that we can store primitives(int, float, double) in ArrayList, but it is not true. Let us take an example:

ArrayList  arraylistobject = new ArrayList();
arraylistobject.add(10); // try to add primitive 10

JVM through Autoboxing (converting primitives to equivalent objects internally) ensures that only objects are added to the ArrayList object. Thus, the above step internally works like this :

arraylistobject.add(new Integer(10)); //Converted int primitive to Integer object and added to arraylistobject

c. Length of the ArrayList is provided by the size() method while Each array object has the length variable which returns the length of the array.
e.g :
Integer arrayobject[] = new Integer[3];
arraylength= arrayobject.length;  //uses arrayobject length variable

ArrayList  arraylistobject = new ArrayList();
arraylistobject.add(10);
arraylistobject.size();//uses arraylistobject size method

d.  Array can be multi-dimensional, while ArrayList is always single-dimensional.

e. In Java, one can ensure Type Safety through Generics. while Array is a homogeneous data structure, thus it will contain objects of a specific class or primitives of a specific data type. In an array, if one tries to store the different data type other than the specified while creating the array object, ArrayStoreException is thrown. e.g :
String temp[] =  new String[2];  // creates a string array of size 2
temp[0] = new Integer(12); // throws ArrayStoreException, trying to add Integer object in String[]

f. We can insert elements into the ArrayList object using the add() method while in the array we insert elements using the assignment operator.
e.g :
Integer addarrayobject[] = new Integer[5];
addarrayobject[0]= new Integer(1);


Similarities Between Array and ArrayList

a. add and get method: Performance of Array and ArrayList are similar for the add and get operations. Both operations run in constant time.
b. Duplicate elements: Both array and ArrayList can contain duplicate elements.
c. Null Values: Both can store null values and uses the index to refer to their elements.
d. Unordered:  Both do not guarantee ordered elements.

How to convert the array of strings into the list?

Array class of java.util package contains the method asList() which accepts the array as a parameter.
e.g:
String[]  meArray =  {"I"  , "Me" , "Myself"};
List meList =  Arrays.asList(meArray);


What is the significance of ensureCapacity() method of Arraylist?

ArrayList internally implements a growable dynamic array which means it can increase and decrease its size automatically. If we try to add an element to an already full ArrayList then it automatically re-sized internally to accommodate the new element however sometimes it's not a good approach.

If you want to add a huge number of elements to an already full ArrayList, in such case ArrayList has to be resized several times, which would result in poor performance. For such scenarios, you can use, ensureCapacity() method of Java.util.ArrayList class.  This method increases the size of the ArrayList by a specified capacity.

ensureCapacity(int minCapacity), takes minimum capacity as input parameter and does not return any value, and does not throw any exception.

In the below code, what is the max acceptable value of n?

public static void main(String[] args) {
    ArrayList names=new ArrayList<>();
    names.add("Himaanshu Shuklaa");
    names.add("John Mathew");
    names.add("Emmy Watson");
    names.add(n, "Rita Anderson");
    System.out.println(names);
}

Ans: n should be less than or equal to the size of ArrayList while doing 'names.add(n, "Rita Anderson")'

Write a program to remove nulls from a List.

Lets say we have an arraylist of names with size =6, it has 3 null names,

List < String >  names=new ArrayList < String > ();
names.add(null);
names.add("Himanshu Shukla");
names.add("Sana Rafat");
names.add(null);
names.add("Brandon");
names.add(null);

a). We can remove null's by using while loop.
while (names.remove(null));

b). We can do the same thing by using removeAll method.
names.removeAll(Collections.singleton(null));

c). By using Java 8's Lambdas to filter the List. We can use either parallel or serial stream:
List < String >  namesWithoutNulls = names.parallelStream()
.filter(Objects::nonNull).collect(Collectors.toList());

Write a program to remove duplicates from a list.

Lets say we have an arraylist of employee id's.

List < Integer >  duplicateEmpIds=new ArrayList < Integer > ();
duplicateEmpIds.add(1);
duplicateEmpIds.add(2);
duplicateEmpIds.add(1);
duplicateEmpIds.add(3);
duplicateEmpIds.add(3);
duplicateEmpIds.add(3);

a). We can easily remove the duplicates using the set
List < Integer >  uniqueEmpIds = new ArrayList <  > (new HashSet(duplicateEmpIds));

b). We can also remove duplicates from a List using Java 8 Lambdas and distinct() method of Streams
List < Integer >  uniqueEmpIds = duplicateEmpIds.stream()
    .distinct().collect(Collectors.toList());

What will be the output of the below program?

String[] names = { "Himanshu", "Sana", "Brandon", "Arnold" }; 
List < String >  namesList = Arrays.asList(names); 
namesList.add("Margarita");

This will throw an UnsupportedOperationException. asList will return a fixed-size List as of the size of a given array. It's an ArrayList, from java.util.Arrays.

Since the returned List is a fixed-size list, we can’t add/remove elements. An attempt to add more elements would cause UnsupportedOperationException. This Exception occurred because the returned object doesn't implement the add() operation since it isn't the same as java.util.ArrayList.

How can we copy a List to another List in Java?

Let's say we have a list, which contains names:
List < String >  names=new ArrayList < String > ();
names.add("Himanshu Shukla");
names.add("Sana Rafat");
names.add("Andrew Hudson");

a). Copy by constructor: The simplest way to copy a List is by using the constructor that takes a collection as its argument:
List < String >  copiednames=new ArrayList < String > (names);

Let's say the names List contains the list of 'Names' class. In this came if we create a copied name, and someone makes changes in any element of the 'names' list it would affect the corresponding element of 'copiednames' list.  This is because of the fact that we're copying references here and not cloning the objects, any change made in one element will affect both lists. That's why using the constructor is good to copy only the immutable objects.

If a thread is modifying the list while another thread is trying to copy it, ConcurrentAccessException will be thrown. To fix this issue, either uses a designed concurrent access collection or lock the collection appropriately to iterate over it.

For concurrent access collection, CopyOnWhiteArrayList can be used, in which all mutative operations are implemented by making a fresh copy of the underlying array. To lock the Collection, it's possible to use a lock primitive to serialize read/write access, such as ReentrantReadWriteLock.

b). AddAll() method: 
List < String >  copiednames = new ArrayList <  > ();
copiednames.addAll(names);

c). Collections.copy: Collections class has a copy method which needs a source and a destination list, it will maintain the index of each copied element in the destination list such as the original.

In the below example all the previous elements in the destEmpIdList were overwritten because both lists have the same size. After copy destEmpIdList will contain 1,2,3:

List < Integer >  sourceEmpIdList = Arrays.asList(1,2,3);
List < Integer >  destEmpIdList = Arrays.asList(4,5,6);
Collections.copy(destEmpIdList, sourceEmpIdList);

In the below example, the destination list size is larger than the source. In this case, three first items were overwritten while the rest of the elements in the list are conserved. After copy destEmpIdList will contain 1,2,3,7,8,9:

List < Integer >  sourceEmpIdList = Arrays.asList(1,2,3);
List < Integer >  destEmpIdList = Arrays.asList(4,5,6,7,8,9);
Collections.copy(destEmpIdList, sourceEmpIdList);

d). By using Java 8: We can use Streams to copy the list. We can even filter the source list while doing the copy operation.
List < Integer >  sourceEmpIdList = Arrays.asList(1,2,3);
List < Integer >  destEmpIdList = sourceEmpIdList.stream()
.collect(Collectors.toList());

What is a linked list?

  • LinkedList is a doubly-linked list implementation of the List and Deque interfaces.
  • LinkedList maintains insertion order.
  • Every element is a node, which keeps a reference to the next and previous ones.
  • It implements all optional list operations and permits all elements including nulls).
  • Iterator and ListIterator iterators of a LinkedList are fail-fast (if the list is modified after the iterator's creation a ConcurrentModificationException will be thrown).
  • LinkedList is not synchronized, we can retrieve a synchronized version of it by calling the Collections.synchronizedList method, e.g: List list = Collections.synchronizedList(new LinkedList(__));
  • To create a linkedlist, LinkedList < object > linkedList = new LinkedList < object > ()
  • LinkedList implements the List and Deque interface, that's why besides standard add() and addAll() methods we can find addFirst() and addLast() methods, which add an element in the beginning or at the end respectively.
  • It offers removeFirst() and removeLast() to remove an element from the beginning or from the end respectively. Also, removeFirstOccurence() and removeLastOccurence() methods are there which returns true if collection contained specified element.
  • Deque extends Queue interface, that's why it provides queue-like behaviors, e.g : linkedList.poll() and linkedList.pop(). These methods retrieve the first element and remove it from the list.
  • The difference between poll() and pop() is that pop will throw NoSuchElementException() on empty list, whereas poll returns null. 
  • Also, pollFirst() and pollLast() are also available.
  • push() method inserts the element as the head of the LinkedList, linkedList.push(Object o);

When should you use ArrayList and when should you use LinkedList?

  • If you need to support random access, without inserting or removing elements from anywhere other than the ends, then ArrayList is a better choice.
  • If you add and remove elements from the middle of the list frequently while accessing them sequentially, then LinkedList is better.
  • A LinkedList consumes more memory than an ArrayList because every node in a LinkedList stores two references, one for its previous element and one for its next element, whereas ArrayList holds only data and its index. Memory usage should be considered when choosing between an ArrayList and LinkedList.

What is CopyOnWriteArrayList?  How it is different from  ArrayList in Java?

  • It is introduced in JDK1.5 as a thread-safe variant of ArrayList.
  • When we are using any of the modified methods – such as add() or remove(), the whole content of the CopyOnWriteArrayList is copied into the new internal copy. i.e all mutative operations are implemented by creating a fresh copy of the underlying array. Because of this, we can iterate over the list in a safe way, even when concurrent modification is happening.
  • When we're calling the iterator() method on the CopyOnWriteArrayList, we get back an Iterator backed up by the immutable snapshot of the content of the CopyOnWriteArrayList. Its content is an exact copy of data that is inside an ArrayList from the time when the Iterator was created. If other threads add or remove an element from the list, that modification is making a fresh copy of the data that will be used in any further data lookup from that list. This guarantees that it will not throw ConcurrentModificationException and it permits all elements including null.
  • Due to the copying mechanism in CopyOnWriteArrayList, the remove() operation on the returned Iterator will throw an UnsupportedOperationException.

Difference between Arraylist and Vector in Java

This is a very common Core Java Interview question.
  • Both Vector and ArrayList are derived from AbstractList and implements List interface, which means both of them are ordered collection and allows duplicates.
  • Both Vector and ArrayList are index based Collection, which means we can use get(index) method to retrieve objects from Vector and ArrayList.
  • Vector is synchronized while ArrayList is not synchronized. Synchronization and thread safe means at a time only one thread can access the code. In Vector class all the methods are synchronized, that's why the Vector object is already synchronized when it is created.
  • Vector is slow as it is thread safe. In comparison ArrayList is fast as it is non synchronized. Thus in ArrayList two or more threads can access the code at the same time, while Vector is limited to one thread at a time.
  • A Vector defaults to doubling size of its array. By default ArrayList size is 10. While when you insert an element into the ArrayList, it checks whether it reaches the last element then it will create the new array with a size = (Array size + 50% of array size), copy the new data of last array to new array, then old array is garbage collected by the Java Virtual Machine (JVM).
  • Other than HashTable, Vector is the only other class which uses both Enumeration and Iterator. While ArrayList can only use Iterator for traversing an ArrayList.
  • java.util.Vector class was there in java since the very first version of the java development kit (jdk). java.util.ArrayList  was introduced in java version 1.2 as part of Java Collections framework. In java version 1.2, Vector class has been refactored to implement the List Interface.
Vector implements a dynamic array. Following is the list of constructors provided by the vector class.
  • Vector( ) : This constructor creates a default vector, which has an initial size of 10.
  • 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.
  • 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.
  • Vector(Collection c) : This constructor creates a vector that contains the elements of collection c.
Which collection classes are synchronized or thread-safe?
Stack, Properties, Vector and Hashtable.


What is the difference between Queue and Stack?
Queue is a data structure which is based on FIFO(first in first out) property. Stack is a data structure which is based on LIFO (last in first out) property.


Why is it preferred to declare: List < String >  list = new ArrayList  < String > (); instead of ArrayList <  String  > = new ArrayList < String > ();
  • If later on code needs to be changed from ArrayList to Vector then only at the declaration place we can do that.
  • The most important one – If a function is declared such that it takes list. E.g void showDetails(List list);
  • When the parameter is declared as List to the function it can be called by passing any subclass of List like ArrayList,Vector,LinkedList making the function more flexible.
How to sort list of strings - case insensitive?
using Collections.sort(list, String.CASE_INSENSITIVE_ORDER);

How to make a List (ArrayList,Vector,LinkedList) read only or Immutable?
  • A list implementation can be made read only or Immutable using Collections.unmodifiableList(list). 
  • This method returns a new list. If a user tries to perform add operation on the new list; UnSupportedOperationException is thrown.

How to reverse the List in Collections?
Collections.reverse(listobject);

What is the difference between the peek(), poll() and remove() methods of the Queue interface?
 
Both poll() and remove() method is used to remove the head object of the Queue. The main difference lies when the Queue is empty(), then the poll() method will return null while the remove() method will throw NoSuchElementException. peek() method retrieves but does not remove the head of the Queue. If the queue is empty then the peek() method also returns null.

What is the difference between Synchronized Collection and Concurrent Collection?
In Java, both synchronized collections and concurrent collections are mechanisms used to handle thread safety in multi-threaded environments, but they differ in their implementation and characteristics.

Synchronized collections are regular collections (like ArrayList, HashMap, etc.) wrapped with synchronization. This means that every method call (add, remove, etc.) on the collection is synchronized externally to ensure thread safety. They achieve thread safety by using synchronized blocks or methods to ensure that only one thread can modify the collection at a time. e.g: Collections.synchronizedList(new ArrayList<>())

Concurrent collections are specially designed data structures that are inherently thread-safe without the need for external synchronization.
They use advanced concurrency mechanisms such as lock striping, non-blocking algorithms, or efficient locking strategies (like ReadWriteLock) to allow multiple threads to access and modify them concurrently. e.g ConcurrentHashMap, CopyOnWriteArrayList, etc.

FYI, ConcurrentHashMap is scalable as it uses a stripped locking technique and is specially designed for concurrent use i.e. more than one thread. By default it simultaneously allows 16 threads to read and write from Map without any external synchronization. Unlike Hashtable and Synchronized Map, it never locks whole Map, instead, it divides the map into segments and locking is done on those. However it performs better if a number of reader threads is greater than the number of writer threads.

Key Difference:
  • Implementation: Synchronized collections use external synchronization (through synchronized blocks or methods) to achieve thread safety, while concurrent collections use internal mechanisms (like lock striping, non-blocking algorithms) for thread safety.
  • Performance: Concurrent collections generally offer better performance under high contention compared to synchronized collections because they are optimized for concurrent access.
  • Usage: Choose synchronized collections when the concurrency requirements are low or when ease of use and simplicity are prioritized. Use concurrent collections when high concurrency, scalability, and performance are critical.
In short, synchronized collections are simpler but may suffer from performance drawbacks under heavy concurrency, whereas concurrent collections are more complex internally but offer superior performance in highly concurrent environments. The choice between them depends on the specific requirements of your multi-threaded application.


How to write a perfect hash function?
A hash function that maps each item into a unique slot is referred to as a perfect hash function. However, irrespective of how good a hash function is, collisions are bound to occur. Nevertheless, we do not need the hash function to be perfect to still gain performance efficiency.

One way to always have a perfect hash function is to increase the size of the hash table so that each possible value in the item range can be accommodated. This guarantees that each item will have a unique slot. Although this is practical for small numbers of items, it is not feasible when the number of possible items is large.

As writing a perfect hash function is not alays possible, our goal should be to create a hash function that minimizes the number of collisions, is easy to compute, and evenly distributes the items in the hash table. There are a number of common ways to extend the simple remainder method. Here a few ways, we can write hash function:
#folding method : In this method we divide the item (key) into equal-size pieces (the last piece may not be of equal size). These pieces are then added together to give the resulting hash value. For example, if our item was the phone number 9920600280, we would take the digits and divide them into groups of 2 (99, 20, 60, 02, 80). After the addition, 99+20+60+02+80=195. If we assume our hash table has 11 slots, then we need to perform the extra step of dividing by 11 and keeping the remainder. In this case 195 % 11 is 8, so the phone number 9920600280 hashes to slot 8.

#mid-square method: In this method, we first square the item, and then extract some portion of the resulting digits. For example, if the item were 44, we would first compute the square of 44=1936. By extracting the middle two digits, 93, and performing the remainder step, we get 5 (93 % 11). Table 5 shows items under both the remainder method and the mid-square method.



What is a LinkedHashMap? LinkedHashMap class is a Linked list implementation of the Map interface, with predictable iteration order. It inherits HashMap class and implements the Map interface. The important points about Java HashMap class are:
  • A LinkedHashMap contains values based on the key.
  • It contains only unique elements.
  • It may have one null key and multiple null values.
  • It is same as HashMap instead maintains insertion order.
Here is the declaration for java.util.LinkedHashMap class, where, K is the type of keys maintained by this map and V is the type of mapped values :

public class LinkedHashMap < K,V > extends HashMap < K,V > implements Map < K,V >

Constructors of Java LinkedHashMap class
  • LinkedHashMap()   : It is used to construct a default LinkedHashMap.
  • LinkedHashMap(int capacity) :   It is used to initialize a LinkedHashMap with the given capacity.
  • LinkedHashMap(int capacity, float loadfactor) : It is used to initialize both the capacity and the loadfactor.
  • LinkedHashMap(Map m) : It is used to initialize the LinkedHashMap with the elements from the given Map class m.

What is a TreeMap?

Java TreeMap class implements the Map interface by using a tree. It provides an efficient means of storing key/value pairs in sorted order. The important points about Java TreeMap class are:
  • A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
  • It contains only unique elements.
  • It cannot have the null key but can have multiple null values.
  • It is the same as HashMap instead maintains ascending order.

here is TreeMap class declaration, where, K is the type of keys maintained by this map and V is the type of mapped values :
public class TreeMap < K,V > extends AbstractMap < K,V > implements NavigableMap < K,V > , Cloneable, Serializable 
Constructors of Java TreeMap class
  • TreeMap() : It is used to construct an empty tree map that will be sorted using the natural order of its key.
  • TreeMap(Comparator comp) : It is used to construct an empty tree-based map that will be sorted using the comparator comp.
  • TreeMap(Map m) : It is used to initialize a tree map with the entries from m, which will be sorted using the natural order of the keys.
  • TreeMap(SortedMap sm) : It is used to initialize a tree map with the entries from the SortedMap sm, which will be sorted in the same order as sm.
Methods of TreeMap:
  • boolean containsKey(Object key) : It is used to return true if this map contains a mapping for the specified key.
  • boolean containsValue(Object value) : It is used to return true if this map maps one or more keys to the specified value.
  • Object firstKey() : It is used to return the first (lowest) key currently in this sorted map.
  • Object get(Object key) : It is used to return the value to which this map maps the specified key.
  • Object lastKey() : It is used to return the last (highest) key currently in this sorted map.
  • Object remove(Object key) : It is used to remove the mapping for this key from this TreeMap if present.
  • void putAll(Map map) : It is used to copy all of the mappings from the specified map to this map.
  • Set entrySet() : It is used to return a set view of the mappings contained in this map.
  • int size() : It is used to return the number of key-value mappings in this map.
  • Collection values() : It is used to return a collection view of the values contained in this map. 

What is difference between HashMap and TreeMap?

  • HashMap can contain one null key, where as TreeMap can not contain any null key.
  • HashMap maintains no order, whereas TreeMap maintains ascending order.

What is IdentityHashMap?

IdentityHashMap in Java was added in Java 1.4. The main difference between IdentityHashMap and HashMap in Java is that IdentityHashMap is a special implementation of the Map interface that doesn't use equals() and hashCode() method for comparing objects unlike other implementations of Map e.g. HashMap. 

Instead, IdentityHashMap uses the equality operator "=="  to compare keys and values in Java which makes it faster compared to HashMap and suitable where you need reference equality check instead of logical equality.

By the way, IdentityHashMap is a special implementation of Map interface much like EnumMap but it also violates the general contract of Map interface which mandates using equals method for comparing Object.

Declaration for java.util.IdentityHashMap class:
public class IdentityHashMap < K,V >  extends AbstractMap < K,V > implements Map , Serializable, Cloneable

Constructors of IdentityHashMap:
  • IdentityHashMap() : This constructs a new, empty identity hash map with a default expected maximum size (21).
  • IdentityHashMap(int expectedMaxSize) : Tis constructs a new, empty map with the specified expected maximum size.
  • IdentityHashMap(Map < ? extends K,? extends V >  m) : This constructs a new identity hash map containing the keys-value mappings in the specified map.

Difference between IdentityHashMap and HashMap?

  • The main difference between HashMap vs IdentityHashMap is that IdentityHashMap uses the equality operator "==" for comparing keys and values inside Map while HashMap uses the equals() method for comparing keys and values.
  • Unlike HashMap, which uses hashcode to find bucket location, IdentityHashMap also doesn't use hashCode() instead it uses System.identityHashCode(object).
  • Since IdentityHashMap doesn't use equals() its comparatively faster than HashMap for object with expensive equals() and hashCode().
  • One more difference between HashMap and IdentityHashMap is the Immutability of the key. One of the basic requirement to safely store Objects in HashMap is keys need to be immutable, IdentityHashMap doesn't require keys to be immutable as it does not rely on equals and hashCode.

What is ConcurrentHashMap?

ConcurrentHashMap is introduced as an alternative to Hashtable and provided all functions supported by Hashtable with an additional feature called "concurrency level", which allows ConcurrentHashMap to partition Map.

ConcurrentHashMap allows multiple readers to read concurrently without any blocking. This is achieved by partitioning Map into different parts based on concurrency level and locking only a portion of Map during updates. 

The default concurrency level is 16, and accordingly, Map is divided into 16 parts and each part is governed by a different lock. This means, that 16 threads can operate on Map simultaneously until they are operating on a different part of Map. This makes ConcurrentHashMap high performance despite keeping thread safety intact.

Since update operations like put(), remove(), putAll() or clear() is not synchronized, concurrent retrieval may not reflect most recent change on Map.

Difference between HashMap and ConcurrentHashMap?

a. ConcurrentHashMap is thread-safe that is the code can be accessed by a single thread at a time. While HashMap is not thread-safe.
b. ConcurrentHashMap doesn’t throw a ConcurrentModificationException if one thread tries to modify it while another is iterating over it.
c. HashMap can be synchronized by synchronizedMap(HashMap) method, which will return a collection that is almost equivalent to Hashtable, where every modification operation on Map is locked on Map object while in the case of ConcurrentHashMap, thread-safety is achieved by dividing the whole Map into different partition based upon Concurrency level and only locking particular portion instead of locking the whole Map.
d. ConcurrentHashMap does not allow null values, so the key can not be null in ConcurrentHashMap. While In HashMap there can only be one null key.

What is WeakHashMap?

A hashtable-based Map implementation with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently than other Map implementations.

Can we replace Hashtable with ConcurrentHashMap?

  • Yes, we can replace Hashtable with ConcurrentHashMap and that's what is suggested in the Java documentation of ConcurrentHashMap. 
  • ConcurrentHashMap performs better than Hashtable ( or SynchronizedMap), because it only locks a portion of Map, instead of the whole Map.
  • But we need to be a bit careful before replacing Hashtable with ConcurrentHashMap. Since Hashtable locks the whole Map instead of a portion of Map, compound operations like if(Hashtable.get(key) == null) or put(key, value) work in Hashtable, but not in ConcurrentHashMap. Instead of this use putIfAbsent() method of ConcurrentHashMap.

How can you Iterate over HashMap, Hashtable, or any Map in Java

    public static void main(String[] args)
    {
        //create a map which contains Employee-Manager's mapping
        HashMap < String, String >  empManager = new HashMap < String, String > ();
        empManager.put("Martin", "Russhal");
        empManager.put("Andreas", "Mattrias");
        empManager.put("Elle", "Russhal");
  
        //using foreach loop on KeySet
        for (String key : empManager.keySet()) {
             System.out.println("Employee: " + key + ", Manager: " + empManager.get(key));
        }
  
        //using KeySet Iterator
        Set < String >  keySet = empManager.keySet();
        Iterator < String >  keySetIterator = keySet.iterator();
        String tempKey;
        while (keySetIterator.hasNext()) {
            tempKey = keySetIterator.next();
            System.out.println("Employee: " + tempKey + ", Manager: " + empManager.get(tempKey));
        }
  
        //using entrySet
        Set < Map.Entry < String, String >  >  entrySet = empManager.entrySet();
        for (Map.Entry < String, String >  entry : entrySet) {
           System.out.println("Employee: " + entry.getKey() + ", Manager: " + entry.getValue());
        }

        //print the values using map.values()
        Collection < String >  managerval=empManager.values();
        for (String manager: managerval)
        {
            System.out.println("Manager Name:"+manager);
        }
  
        //forEach and Lambda of Java 8
        //empManager.forEach((k,v)- > System.out.println("Employee : " + k + ", Manager : " + v));
    }

Write a function, which will take an ArrayList/HashSet and an element. It will return true if the element is present in the ArrayList/HashSet, else it will return false.

public boolean isPresent(ArrayList < String > list, String inputStr)
{
if(list.contains(inputStr))
  return true;
return false;
}


-K Himaanshu Shuklaa..

1 comment: