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
- How Java HashMap works?
- What are fail-fast and fail-safe Iterators?
- What is BlockingQueue in Java?
- When do you use ConcurrentHashMap?
- Which List implementation provides fastest insertion?
- Difference between Iterator and ListIterator
- What is CopyOnWriteArrayList, how it is different than ArrayList?
- Difference between Iterator and Enumeration
- How a Hashmap can be synchronized?
- Difference between IdentityHashMap and HashMap
Java Collections Interview Questions and Answers
HashMapis 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
equalsmethod to identify the matching pair.
What are fail-fast and fail-safe Iterators?
fail-fast Java iterators may throw
ConcurrentModifcationExceptionif 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
ArrayListand for fail safe iterator is
Java BlockingQueue is a concurrent collection that is part of the util package.
BlockingQueueis 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.
When do you use
In the above interview question number 2 we saw
ConcurrentHashMapas 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
Hashtablebut 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
ConcurrentHashMapshould be used.
Listimplementation provides fastest insertion?
This is between
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
In LinkedList the cost is always a constant factor, it is about allocating a node and linking with adjacent elements. In
ArrayListthe 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
Listthen ArrayList is faster than LinkedList. If the insertion is at the beginning and also if the list is longer then
Difference between Iterator and ListIterator
ListIteratoris used to traverse List type of collections exclusively where in
Iteratorcan 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.
What is CopyOnWriteArrayList, how it is different than ArrayList?
CopyOnWriteArrayListis 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
ArrayListas 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.
Difference between Iterator and Enumeration
If the interviewer asks this question in a Java interview any more, consider him to be legacy. Mainly
Iteratoris different from
Enumerationin two ways,
- Iterator allows the removal of elements from the underlying collection.
- Method names are standardized in Iterator.
Iteratoris brought in as a replacement for Enumeration in Java 1.2 release. Use
Iteratoreverywhere instead of
How a HashMap can be synchronized?
There are two options when we need a synchronized
Collections.synchronizedMap(..)to synchronize the
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.
Difference between IdentityHashMap and HashMap
IdentityHashMapis an implementation of
HashMap, this uses reference equality. That means,
- in HashMap, two elements are equal if
- 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
hashCode()as done by HashMap.
- IdentityHashMap is relatively faster than HashMap for operations.
- Keys are mutable in
IdentityHashMapbut in HashMap keys are mutable.
- in HashMap, two elements are equal if
This is second part of a series of Java collections interview questions and the third part will be posted soon.
This Java tutorial was added on 24/10/2014.