Java Collections Interview Questions – Part II

This is the second part of the Java collections interview questions and answers series. Answers are planned to be concise to help prepare and revise for an interview in quick time. I recommend you to go through the Java collections interview questions part I before reading this list.

Java Collections Interview Questions

1. How Java HashMap works?
2. What are fail-fast and fail-safe Iterators?
3. What is BlockingQueue in Java?
4. When do you use ConcurrentHashMap?
5. Which List implementation provides fastest insertion?
6. Difference between Iterator and ListIterator
7. What is CopyOnWriteArrayList, how it is different than ArrayList?
8. Difference between Iterator and Enumeration
9. How a Hashmap can be synchronized?
10. Difference between IdentityHashMap and HashMap

Java Collections Interview Questions and Answers

1. How Java HashMap works?

   HashMap is a key-value pair data structure. Each key will have a corresponding value and the key is the identifier for that value.

   Internally, these key-value pairs are stored in logical blocks (buckets). When a pair is put in a HashMap, its key is used to compute hash code and that hash code identifies a bucket. Imagine it as an array index or a logical address or a door number. The key-value pair is stored at the bucket where the hash code points to. A bucket can have more than one key-value pairs stored in it.

   When a value is looked upon using its key, first the hashcode is computed and the pointing bucket is reached. Then if that bucket has multiple pairs, then each of the ‘key’s are compared using the equals method to identify the matching pair.

   Refer this tutorial to know about what is hashcode and how it works? To know about buckets and hashing refer Java Hashtable tutorial.

2. What are fail-fast and fail-safe Iterators?

   fail-fast Java iterators may throw ConcurrentModifcationException if the underlying collection is modified during an iteration is in progress. fail-safe iterators will not throw any exception as the iteration happens on a clone of the instance. fail fast and fail safe are paradigms that define how a system react when it encounters failure condition. Example for fail fast iterator is ArrayList and for fail safe iterator is ConcurrentHashMap.

3. What is BlockingQueue in Java?

   Java BlockingQueue is a concurrent collection that is part of the util package. BlockingQueue is a type of queue which supports operations that wait for an element to become available when retrieving from it and similarly wait for a space to become available when storing elements in it. This collection is best used in a producer consumer scenario.

4. When do you use ConcurrentHashMap?

   In the above interview question number 2 we saw ConcurrentHashMap as an example for fail safe iterator. It allows complete concurrency for retrievals and updates. When there is a scenario where a high number of concurrent updates are expected then ConcurrentHashMap can be used. This is very similar to a Hashtable but does not lock the entire table to provide concurrency and so it is better performance point of view. When there are high number of updates and less number of read concurrently, then ConcurrentHashMap should be used.

5. Which List implementation provides fastest insertion?

   This is between LinkedList and ArrayList. These two are different variants of List implementations. LinkedList is a doubly linked list datastructure and ArrayList is dynamically resizing array. Performance of these two collections with respect to insert is O(n) for LinkedList and O(n-index) for ArrayList.

   In LinkedList the cost is always a constant factor, it is about allocating a node and linking with adjacent elements. In ArrayList the cost varies based on whether the insertion is at beginning or at the end of the list. Other elements already existing in the ArrayList should be adjusted for positions according to the insertion.

   If the insertion is at the end of the List then ArrayList is faster than LinkedList. If the insertion is at the beginning and also if the list is longer then LinkedList wins.

6. Difference between Iterator and ListIterator

   ListIterator is used to traverse List type of collections exclusively where in Iterator can be used traverse any type of collections. ListIterator has got additional features over an Iterator and they are,

   • ListIterator can traverse a List backwards where in Iterator cannot do.
   • Using ListIterator an element can be added at any given point.
   • Get the current index at any traversal moment.
   • Replace an element at the traversal point.

7. What is CopyOnWriteArrayList, how it is different than ArrayList?

   CopyOnWriteArrayList is a thread-safe counterpart of ArrayList. All mutable operations like add and set are implement by using a copy of the underlying array. Write operation is slower when compared the ArrayList as it takes a snapshot of the instance and does the write. This is useful when the traversal of the collection need not be synchronized during traversal with the original instance and the traversal is larger in count than the updates. This provides a fail safe iterator as it does not throw exception when the underlying collection is modified. At the same time the iterator will not reflect the modifications done to the collection, it just shows the snapshot of state taken at the moment when the iterator is created.

8. Difference between Iterator and Enumeration

   If the interviewer asks this question in a Java interview any more, consider him to be legacy. Mainly Iterator is different from Enumeration in two ways,

   • Iterator allows the removal of elements from the underlying collection.
   • Method names are standardized in Iterator.

   Iterator is brought in as a replacement for Enumeration in Java 1.2 release. Use Iterator everywhere instead of Enumeration

9. How a HashMap can be synchronized?

   There are two options when we need a synchronized HashMap.

   • Use Collections.synchronizedMap(..) to synchronize the HashMap.
   • Use ConcurrentHashMap.

   The preferred choice between these two options is to use the ConcurrentHashMap. That’s because we need not lock the whole object and ConcurrentHashMap partitions the map and obtains lock as necessary. Read the interview question number 4 above. Need not reinvent the wheel unless you are going to provide a different and greater implementation than the ConcurrentHashMap.

10. Difference between IdentityHashMap and HashMap

    IdentityHashMap is an implementation of Map interface. Unlike HashMap, this uses reference equality. That means,

    • in HashMap, two elements are equal if key1.equals(key2)
    • iin IdentityHashMap, two elements are equal if key1 == key2

    Map imposes a contract to honor, the implementations should use object equality. If equals of method returns same value for two keys, then the hash code value should be same.

    • IdentityHashMap intentionally violates the contract and does reference equality.
    • For hashing, the IdentityHashMap uses System.identityHashCode(object) instead of hashCode() as done by HashMap.
    • IdentityHashMap is relatively faster than HashMap for operations.
    • Keys are mutable in IdentityHashMap but in HashMap keys are mutable.

This is second part of a series of Java collections interview questions and the third part will be posted soon.