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.
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.
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
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.
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.
List implementation 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
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
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,
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.
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 is brought in as a replacement for Enumeration in Java 1.2 release. Use
Iterator everywhere instead of
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.
IdentityHashMap is an implementation of
Map interface. Unlike
HashMap, this uses reference equality. That means,
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.
System.identityHashCode(object) instead of
hashCode() as done by HashMap.
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.