Java Collections - Interview Questions

1. What is the difference between poll() and remove() method of Queue interface?

Though both poll() and remove() method from Queue is used to remove the object and returns the head of the queue, there is a subtle difference between them.

If Queue is empty() then a call to remove() method will throw Exception, while a call to poll() method returns null.

By the way, exactly which element is removed from the queue depends upon queue's ordering policy and varies between different implementation, for example, PriorityQueue keeps the lowest element as per Comparator or Comparable at head position.

2. What is the difference between fail-fast and fail-safe Iterators?

Iterators in java are used to iterate over the Collection objects. Fail-Fast iterators immediately throw ConcurrentModificationException if there is structural modification of the collection. Structural modification means adding, removing or updating any element from collection while a thread is iterating over that collection. Iterator on ArrayList, HashMap classes are some examples of fail-fast Iterator.

These iterators throw ConcurrentModificationException if a collection is modified while iterating over it. They use original collection to traverse over the elements of the collection. These iterators don’t require extra memory.

Ex : Iterators returned by ArrayList, Vector, HashMap.

Fail-Safe iterators don’t throw any exceptions if a collection is structurally modified while iterating over it. This is because, they operate on the clone of the collection, not on the original collection and that’s why they are called fail-safe iterators. Iterator on CopyOnWriteArrayList, ConcurrentHashMap classes are examples of fail-safe Iterator.

Fail-safe iterators allow modifications of a collection while iterating over it. These iterators don’t throw any Exception if a collection is modified while iterating over it. They use copy of original collection to traverse over the elements of the collection. These iterators require extra memory for cloning of collection.

Ex : ConcurrentHashMap, CopyOnWriteArrayList

3. How Fail Fast Iterator works ?

To know whether the collection is structurally modified or not, fail-fast iterators use an internal flag called modCount which is updated each time a collection is modified.Fail-fast iterators checks the modCount flag whenever it gets the next value (i.e. using next() method), and if it finds that the modCount has been modified after this iterator has been created, it throws ConcurrentModificationException.

4. How do you remove an entry from a Collection? and subsequently what is the difference between the remove() method of Collection and remove() method of Iterator, which one you will use while removing elements during iteration?

Collection interface defines remove(Object obj) method to remove objects from Collection. List interface adds another method remove(int index), which is used to remove object at specific index. You can use any of these method to remove an entry from Collection, while not iterating. Things change, when you iterate. Suppose you are traversing a List and removing only certain elements based on logic, then you need to use Iterator's remove() method. This method removes current element from Iterator's perspective. If you use Collection's or List's remove() method during iteration then your code will throw ConcurrentModificationException. That's why it's advised to use Iterator remove() method to remove objects from Collection.

5. What is the difference between Synchronized Collection and Concurrent Collection?

Java 5 has added several new Concurrent Collection classes e.g. ConcurrentHashMap, CopyOnWriteArrayList, BlockingQueue etc, which has made Interview questions on Java Collection even trickier. Java Also provided a way to get Synchronized copy of collection e.g. ArrayList, HashMap by using Collections.synchronizedMap() Utility function. -One Significant difference is that Concurrent Collections has better performance than synchronized Collection because they lock only a portion of Map to achieve concurrency and Synchronization. See the difference between Synchronized Collection and Concurrent Collection in Java for more details.

6. What is the difference between Iterator and Enumeration?

Iterator duplicate functionality of Enumeration with one addition of remove() method and both provide navigation functionally on objects of Collection.Another difference is that Iterator is more safe than Enumeration and doesn't allow another thread to modify collection object during iteration except remove() method and throws ConcurrentModificaitonException. See Iterator vs Enumeration in Java for more differences.

7. How does HashSet is implemented in Java, How does it use Hashing?

This is a tricky question in Java because for hashing you need both key and value and there is no key for the store it in a bucket, then how exactly HashSet store element internally. Well, HashSet is built on top of HashMap. If you look at source code of java.util.HashSet class, you will find that that it uses a HashMap with same values for all keys, as shown below:

private transient HashMap map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

When you call add() method of HashSet, it put entry in HashMap :

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

Since keys are unique in a HashMap, it provides uniqueness guarantee of Set interface.

8. What do you need to do to use a custom object as a key in Collection classes like Map or Set?

If you are using any custom object in Map as key, you need to override equals() and hashCode() method, and make sure they follow their contract. On the other hand if you are storing a custom object in Sorted Collection e.g. SortedSet or SortedMap, you also need to make sure that your equals() method is consistent to compareTo() method, otherwise that collection will not follow there contacts e.g. Set may allow duplicates.

9. The difference between HashMap and Hashtable?

Both HashMap and Hashtable implements Map interface but there is some significant difference between them which is important to remember before deciding whether to use HashMap or Hashtable in Java. Some of them are thread-safety, synchronization, and speed. here are those differences :

1. The HashMap class is roughly equivalent to Hashtable, except that it is non-synchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesn't allow nulls).
2. One of the major differences between HashMap and Hashtable is that HashMap is non-synchronized whereas Hashtable is synchronized, which means Hashtable is thread-safe and can be shared between multiple threads but HashMap can not be shared between multiple threads without proper synchronization. Java 5 introduces ConcurrentHashMap which is an alternative of Hashtable and provides better scalability than Hashtable in Java.
3. Another significant difference between HashMap vs Hashtable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the Hashtable is not and throw ConcurrentModificationException if any other Thread modifies the map structurally by adding or removing any element except Iterator's own remove() method. But this is not a guaranteed behavior and will be done by JVM on best effort. This is also an important difference between Enumeration and Iterator in Java.
4. One more notable difference between Hashtable and HashMap is that because of thread-safety and synchronization Hashtable is much slower than HashMap if used in Single threaded environment. So if you don't need synchronization and HashMap are only used by one thread, it outperforms Hashtable in Java.
5. HashMap does not guarantee that the order of the map will remain constant over time.

10. When do you use ConcurrentHashMap in Java?

The synchronized collections classes, Hashtable, and Vector, and the synchronized wrapper classes, Collections.synchronizedMap() and Collections.synchronizedList(), provide a basic conditionally thread-safe implementation of Map and List. However, several factors make them unsuitable for use in highly concurrent applications, for example, their single collection-wide lock is an impediment to scalability and it often becomes necessary to lock a collection for a considerable time during iteration to prevent ConcurrentModificationException.

ConcurrentHashMap and CopyOnWriteArrayList implementations provide much higher concurrency while preserving thread safety, with some minor compromises in their promises to callers. ConcurrentHashMap and CopyOnWriteArrayList are not necessarily useful everywhere you might use HashMap or ArrayList, but are designed to optimize specific common situations. Many concurrent applications will benefit from their use.

Now lets do a comparison of Hashtable and ConcurrentHashMap, both can be used in the multithreaded environment but once the size of Hashtable becomes considerable large performance degrade because for iteration it has to be locked for a longer duration.

Since ConcurrentHashMap introduced the concept of segmentation, how large it becomes only certain part of it get locked to provide thread safety so many other readers can still access map without waiting for iteration to complete.

In Summary, ConcurrentHashMap only locked certain portion of Map while Hashtable locks full map while doing iteration. This will be clearer by looking at this diagram which explains the internal working of ConcurrentHashMap in Java.

11. What is the difference between Set and List in Java?

• Set doesn't allowed duplicate while List does and List maintains insertion order while Set doesn't.
• List maintains insertion order of elements while Set doesn't maintain any ordering.
• The list allows duplicate objects while Set doesn't allow any duplicates.
• List allow positional acces but set doesnt

How do you Sort objects on the collection?

Sorting is implemented using Comparable and Comparator in Java and when you call Collections.sort() it gets sorted based on the natural order specified in compareTo() method while Collections.sort(Comparator) will sort objects based on compare() method of Comparator.

12. What is the difference between Vector and ArrayList?

1. First and most common difference between Vector vs ArrayList is that Vector is synchronized and thread-safe while ArrayList is neither Synchronized nor thread-safe. Now, What does that mean? It means if multiple thread try to access Vector same time they can do that without compromising Vector's internal state. Same is not true in case of ArrayList as methods like add(), remove() or get() is not synchronized.
2. Second major difference on Vector vs ArrayList is Speed, which is directly related to previous difference. Since Vector is synchronized, its slow and ArrayList is not synchronized its faster than Vector.
3. Third difference on Vector vs ArrayList is that Vector is a legacy class and initially it was not part of Java Collection Framework. From Java 1.4 Vector was retrofitted to implement List interface and become part of Collection Framework.

13. Difference and similarities between HashSet and HashMap in Java?

Similarities

1. Both HashMap and HashSet are a hash based collection in Java.
2. Both HashMap and HashSet are not synchronized and can not be shared between multiple threads.
3. Iterator returned by HashMap's keySet() and HashSet are fail-fast and they throw ConcurrentModificationException if they detect any structural change in Collection.
4. Both HashMap and HashSet provided constant time performance for basic operations like put(), get() etc.
5. Both HashSet and HashMap allows null values.

Differences

1. The first and most significant difference between HashMap and HashSet is that HashMap is an implementation of Map interface while HashSet is an implementation of Set interface, which means HashMap is a key value based data-structure and HashSet guarantees uniqueness by not allowing duplicates.In reality, HashSet is a wrapper around HashMap in Java, if you look at the code of add(E e) method of HashSet.java you will see following code :

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

   where it's putting Object into a map as key and value is a final object PRESENT which is a dummy.
2. The second difference between HashMap and HashSet is that we use add() method to put elements into Set but we use put() method to insert key and value into HashMap in Java.
3. HashSet allows only one null key, but HashMap can allow one null key + multiple null values.

14. What is NavigableMap in Java? What is a benefit over Map?

NavigableMap Map was added in Java 1.6, it adds navigation capability to Map data structure. It provides methods like lowerKey() to get keys which is less than specified key, floorKey() to return keys which is less than or equal to specified key, ceilingKey() to get keys which is greater than or equal to specified key and higherKey() to return keys which is greater specified key from a Map. It also provide similar methods to get entries e.g. lowerEntry(), floorEntry(), ceilingEntry() and higherEntry(). Apart from navigation methods, it also provides utilities to create sub-Map e.g. creating a Map from entries of an exsiting Map like tailMap, headMap and subMap. headMap() method returns a NavigableMap whose keys are less than specified, tailMap() returns a NavigableMap whose keys are greater than the specified and subMap() gives a NavigableMap between a range, specified by toKey to fromKey.

15. Can we replace Hashtable with ConcurrentHashMap?

Yes we can replace Hashtable with ConcurrentHashMap and that's what suggested in Java documentation of ConcurrentHashMap. but you need to be careful with code which relies on locking behavior of Hashtable. Since Hashtable locks whole Map instead of a portion of Map, compound operations like if(Hashtable.get(key) == null) put(key, value) works in Hashtable but not in concurrentHashMap. instead of this use putIfAbsent() method of ConcurrentHashMap

16. What is CopyOnWriteArrayList, how it is different than ArrayList and Vector?

CopyOnWriteArrayList is new List implementation introduced in Java 1.5 which provides better concurrent access than Synchronized List. better concurrency is achieved by Copying ArrayList over each write and replace with original instead of locking. Also CopyOnWriteArrayList doesn't throw any ConcurrentModification Exception. Its different than ArrayList because its thread-safe and ArrayList is not thread-safe and it's different than Vector in terms of Concurrency. CopyOnWriteArrayList provides better Concurrency by reducing contention among readers and writers. Here is a nice table which compares performance of three of popular List implementation ArrayList, LinkedList and CopyOnWriteArrayList in Java:

17. When does ConcurrentModificationException occur on iteration?

When you remove object using Collection's or List's remove method e.g. remove(Object element) or remove(int index), instead of Iterator's remove() method than ConcurrentModificationException occurs. As per Iterator's contract, if it detect any structural change in Collection e.g. adding or removing of the element, once Iterator begins, it can throw ConcurrentModificationException.

Please note the below points about concurrentModificationException

1. Can come if two threads trying to modify one list at same time eg: one thread is iterating over it and other thread is removing elements from it.
2. More commonly, it also comes when you use ArrayList's remove() method while iterating over list.
3. Always use iterators remove() method to delete elements when traversing.

Dont delete elements when looping over ArrayList using advanced loop, because it doesnt expose iterator's remove metho, but will throw ConcurrentModificationException if you delete ArrayList's remove() method

18. Difference between Set, List and Map Collection classes?

java.util.Set, java.util.List and java.util.Map defines three of most popular data structure support in Java. Set provides uniqueness guarantee i.e.g you can not store duplicate elements on it, but it's not ordered. On the other hand List is an ordered Collection and also allowes duplicates. Map is based on hashing and stores key and value in an Object called entry. It provides O(1) performance to get object, if you know keys, if there is no collision. Popular impelmentation of Set is HashSet, of List is ArrayList and LinkedList, and of Map are HashMap, Hashtable and ConcurrentHashMap. Another key difference between Set, List and Map are that Map doesn't implement Collection interface, while other two does. For a more detailed answer, see Set vs List vs Map in Java

19. What is BlockingQueue, how it is different than other collection classes?

BlockingQueue is a Queue implementation available in java.util.concurrent package. It's one of the concurrent Collection class added on Java 1.5, main difference between BlockingQueue and other collection classes is that apart from storage, it also provides flow control. It can be used in inter-thread communication and also provides built-in thread-safety by using happens-before guarantee. You can use BlockingQueue to solve Producer Consumer problem, which is what is needed in most of concurrent applications.

Here are the important points about blocking queue

1. BlockingQueue in Java doesn't allow null elements, various implementation of BlockingQueue like ArrayBlockingQueue, LinkedBlockingQueue throws NullPointerException when you try to add null on queue

   BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(10);
   //bQueue.put(null); //NullPointerException - BlockingQueue in Java doesn't allow null
         
   bQueue = new LinkedBlockingQueue<String&rt;();
   bQueue.put(null);
   

   Exception in thread "main" java.lang.NullPointerException at java.util.concurrent.LinkedBlockingQueue.put(LinkedBlockingQueue.java:288)
2. BlockingQueue can be bounded or unbounded. A bounded BlockingQueue is one which is initialized with initial capacity and call to put() will be blocked if BlockingQueue is full and size is equal to capacity. This bounding nature makes it ideal to use a shared queue between multiple threads like in most common Producer consumer solutions in Java. An unbounded Queue is one which is initialized without capacity, actually by default it initialized with Integer.MAX_VALUE. most common example of BlockingQueue uses bounded BlockingQueue as shown in below example.

   BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);
   bQueue.put("Java");
   System.out.println("Item 1 inserted into BlockingQueue");
   bQueue.put("JDK");
   System.out.println("Item 2 is inserted on BlockingQueue");
   bQueue.put("J2SE");
   System.out.println("Done");
   
   Output:
   Item 1 inserted into BlockingQueue
   Item 2 is inserted on BlockingQueue
   
   

3. BlockingQueue implementations like ArrayBlockingQueue, LinkedBlockingQueue and PriorityBlockingQueue are thread-safe. All queuing method uses concurrency control and internal locks to perform operation atomically. Since BlockingQueue also extend Collection, bulk Collection operations like addAll(), containsAll() are not performed atomically until any BlockingQueue implementation specifically supports it. So call to addAll() may fail after inserting couple of elements.
4. Common methods of BlockingQueue is are put() and take() which are blocking methods in Java and used to insert and retrive elements from BlockingQueue in Java. put() will block if BlockingQueue is full and take() will block if BlockingQueue is empty, call to take() removes element from head of Queue as shown in following example:

   BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);
   bQueue.put("Java"); //insert object into BlockingQueue
   System.out.println("BlockingQueue after put: " + bQueue);
   bQueue.take(); //retrieve object from BlockingQueue in Java
   System.out.println("BlockingQueue after take: " + bQueue);
   
   Output:
   BlockingQueue after put: [Java]
   BlockingQueue after take: []
   

5. BlockingQueue interface extends Collection, Queue and Iterable interface which provides it all Collection and Queue related methods like poll(), and peak(), unlike take(), peek() method returns head of the queue without removing it, poll() also retrieves and removes elements from head but can wait till specified time if Queue is empty.

   BlockingQueue<String> linkedBQueue = new LinkedBlockingQueue<String>(2);
   linkedBQueue.put("Java"); //puts object into BlockingQueue
   System.out.println("size of BlockingQueue before peek : " + linkedBQueue.size());       
   System.out.println("example of peek() in BlockingQueue: " + linkedBQueue.peek());
   System.out.println("size of BlockingQueue after peek : " + linkedBQueue.size());
   System.out.println("calling poll() on BlockingQueue: " + linkedBQueue.poll());
   System.out.println("size of BlockingQueue after poll : " + linkedBQueue.size());
   
   Output:
   size of BlockingQueue before peek : 1
   example of peek() in BlockingQueue: Java
   size of BlockingQueue after peek : 1
   calling poll() on BlockingQueue: Java
   size of BlockingQueue after poll : 0
   

6. Other important methods from BlockingQueue in Java is remainingCapacity() and offer(), former returns number remaining space in BlockingQueue, which can be filled without blocking while later insert object into queue if possible and return true if success and false if fail unlike add() method which throws IllegalStateException if it fails to insert object into BlockingQueue. Use offer() over add() wherever possible.

20. How to convert the array of strings into the list ?

Arrays class of java.util package contains the method asList() which accepts the array as parameter. So,

String[]  wordArray =  {"Love Yourself"  , "Alive is Awesome" , "Be in present"};
List wordList =  Arrays.asList(wordArray);

21. Difference between HashSet and TreeSet?

1. Ordering : 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. Elements are sorted according to the natural ordering of its elements in TreeSet. If the objects can not be sorted in natural order than use compareTo() method to sort the elements of TreeSet object .
2. Null value : HashSet can store null object while TreeSet does not allow null object. If one try to store null object in TreeSet object , it will throw Null Pointer Exception.
3. Performance : HashSet take 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).
4. Speed : HashSet is much faster than TreeSet,as 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.
5. Internal implementation : As we have already discussed How hashset internally works in java thus, in one line HashSet are internally backed by hashmap. While TreeSet is backed by a Navigable TreeMap.
6. Functionality : TreeSet is rich in functionality as compare to HashSet. Functions like pollFirst(),pollLast(),first(),last(),ceiling(),lower() etc. makes TreeSet easier to use than HashSet.
7. Comparision : HashSet uses equals() method for comparison in java while TreeSet uses compareTo() method for maintaining ordering .

22. Similarities Between HashSet and TreeSet?

1. Unique Elements : Since HashSet and TreeSet both implements Set interface . Both are allowed to store only unique elements in their objects. Thus there can never be any duplicate elements inside the HashSet and TreeSet objects.
2. Not Thread Safe : HashSet and TreeSet both are not synchronized or not thread safe.HashSet and TreeSet, both implementations are not synchronized. If multiple threads access a hash set/ tree set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
3. Clone() method copy technique: Both HashSet and TreeSet uses shallow copy technique to create a clone of their objects .
4. Fail-fast Iterators : The iterators returned by this class's method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

23. Difference between ArrayList and LinkedList in Java?

1. Implementation : ArrayList is the resizable array implementation of list interface , while LinkedList is the Doubly-linked list implementation of the list interface.
2. Performance : Performance of ArrayList and LinkedList depends on the type of operation
   • get(int index) or search operation : ArrayList get(int index) operation runs in constant time i.e O(1) while LinkedList get(int index) operation run time is O(n) . The reason behind ArrayList being faster than LinkedList is that ArrayList uses index based system for its elements as it internally uses array data structure , on the other hand , LinkedList does not provide index based access for its elements as it iterates either from the beginning or end (whichever is closer) to retrieve the node at the specified element index.
   • insert() or add(Object) operation : Insertions in LinkedList are generally fast as compare to ArrayList. In LinkedList adding or insertion is O(1) operation . While in ArrayList, if array is full i.e worst case, there is extra cost of resizing array and copying elements to the new array , which makes runtime of add operation in ArrayList O(n) , otherwise it is O(1) .
   • remove(int) operation : Remove operation in LinkedList is generally same as ArrayList i.e. O(n). In LinkedList , there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1) . The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as parameter . This method traverses the LinkedList until it found the Object and unlink it from the original list . Hence this method run time is O(n). While in ArrayList remove(int) method involves copying elements from old array to new updated array , hence its run time is O(n).
3. Reverse Iterator : LinkedList can be iterated in reverse direction using descendingIterator() while there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.
4. Initial Capacity : If the constructor is not overloaded , then ArrayList creates an empty list of initial capacity 10 , while LinkedList only constructs the empty list without any initial capacity.
5. Memory Overhead : Memory overhead in LinkedList is more as compared to ArrayList as node in LinkedList needs to maintain the addresses of next and previous node. While in ArrayList each index only holds the actual object(data).

24. Differences between the Comparator and the Comparable interfaces?

1. Sort sequence : In comparable ,Only one sort sequence can be created while in comparator many sort sequences can be created .
2. Methods Used : Comparator interface in Java has method public int compare (Object o1, Object o2) which returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. While Comparable interface has method public int compareTo(Object o) which returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.
3. Objects needed for Comparision : If you see then logical difference between these two is Comparator in Java compare two objects provided to it , while Comparable interface compares "this" reference with the object specified. So only one object is provided which is then compared to "this" reference.
4. Modify Classes :One has to modify the class whose instances you want to sort while in comparator one build a class separate from the class whose instances one want to sort .
5. Package : Comparator in Java is defined in java.util package while Comparable interface in Java is defined in java.lang package, which very much says that Comparator should be used as an utility to sort objects which Comparable should be provided by default.