01: ♥♦ 17 Java Collections interview Q&As on differences between X & Y

Java Collection interview questions and answers and Java String class interview Q&As are must know as you can’t write any decent Java application without these 2 APIs. This post focuses on Java Collection interview Q&As on differences between X and Y. These Q&As are discussed in more detail in the other posts.

Q1. What are the differences between legacy and non-legacy collection classes in the java.util package?
A1. Early version of Java defined several classes and one interface to store objects. These old classes are known as legacy classes. The legacy classes like Vector, Hashtable, and Stack still exist in the API to provide forwards compatibility to code written during early days of Java.

These classes are now re-engineered with the “Java Collections Framework (JCF)” that looks as shown below with interfaces & classes.

List, Set, and Queue

Legacy classes & JCF

Map

Legacy Hashtable & JCF

All the methods of the legacy classes are synchronized (i.e. locks the whole collection), hence can lead to performance issues. The methods of the re-engineered Collections framework classes like ArrayList, HashSet, BlockingQueue, HashMap, etc are NOT synchronized (i.e. they don’t lock). If you need thread-safety you have two choices:

1) Using the java.util.Collections API methods provide a basic conditionally thread-safe implementation of Map and List.

2) Using the java.util.concurrent package classes like ConcurrentHashMap, CopyOnWriteArrayList, etc that use better concurrency techniques. For example, the ConcurrentHashMap uses a technique known as the “lock stripping“, which divides the whole map into several segments and locks only the relevant segments, which allows multiple threads to access other segments of same ConcurrentHashMap without locking. So, concurrent reads are possible.

Reference: http://www.javarticles.com/2012/06/concurrenthashmap.html

Similarly, CopyOnWriteArrayList & CopyOnWriteArraySet allow concurrent reads by multiple threads without requiring any locking and when a write happens it copies the whole ArrayList or HashSet and swap with a newer one.

Q2. What are differences between Enumeration and Iterator?
A2. Enumeration is old and it’s there from JDK1.0 whereas iterator is newer. The key difference between Enumeration and iterator is that “Iterator has a remove() method” whereas Enumeration doesn’t. Enumeration acts as Read-only interface, whilst an Iterator can manipulate the objects like adding and removing. Enumeration can only be used with legacy collection classes whereas an Iterator can be used with both legacy & non-legacy classes.

Q3. What is the difference between an Iterable & an Iterator?
A3. Java Iterable Vs Iterator differences and know how.

Q4. What are differences between fail-fast and fail-safe iterators?
A4. Iterators returned by most of pre JDK1.5 collection classes like Vector, ArrayList, HashSet, etc are fail-fast iterators. Iterators returned by JDK 1.5+ ConcurrentHashMap and CopyOnWriteArrayList classes are fail-safe iterators.

Use copy-on-write List/Set and concurrent maps from the java.util.concurrent package to prevent ConcurrentModificationException being thrown whilst preserving thread safety. These classes provide fail-safe iteration as opposed to non-concurrent classes like ArrayList, HashSet, etc use fail-fast iteration leading to ConcurrentModificationException if you try to remove an element while iterating over a collection.

[ Further readings: Beginner what is wrong with this Java code? | Top 5 Core Java Exceptions and best practices ]

You need to choose the right data structure based on its usage/access patterns: More reads Vs more writes, FIFO (First-In-First-Out) Vs LIFO (Last-In-First-Out), random reads, inserts in the middle vs end, does ordering matter?, duplicates allowed?, concurrent access possible? etc.

Q5. What are differences between ArrayList and LinkedList?
A5.

1. Insertions and deletions are faster in LinkedList compared to an ArrayList as LinkedList uses links (i.e. before and next reference) as opposed to an ArrayList, which uses an array under the covers, and may need to resize the array if the array gets full. Adding to an ArrayList has a worst case scenario of O(n) whilst LinkedList has O(1).

2. LinkedList has more memory footprint than ArrayList. An ArrayList only holds actual object whereas LinkedList holds both data and reference of next and previous node.

3. Random access has the worst case scenario of O(n) in LinkedList as to access 6th element in a LinkedList with 8 elements, you need to traverse through 1 to 5th element before you can get to the 6th element, whereas in an ArrayList, you can get the 6th element with O(1) with list.get(5).

4. Add or remove from the head of the list is in favor of LinkedList with O(1) whereas O(n) for ArrayList.

5. Iterating over either kind of List is the same. ArrayList is technically faster, but the difference is small unless you’re doing something really performance-sensitive.

What are these O(n), O(log n), O(1), etc? Learn more about understanding Big O notations through Java examples.

Q6. Does a HasMap internally use a LinkedList or an ArrayList?
A6. Until Java 8: LinkedList. Java 8 onwards: a “binary tree” because in case of high collision the lookup is reduced to O(log n) from O(n) by using binary trees. Learn more at HashMap & HashSet and how do they internally work?

Also when hash keys arrive from untrusted sources like HTTP headers, the resulting keys will have the same hashcode, which not only causes high collisions, but also when you perform lots of look-ups, you will experience the Denial of Service (i.e. DoS) attacks.

Q7. What is the difference between an “unmodifiable” & an “immutable” collection?
A7. An unmodifiable collection is often a wrapper around a modifiable collection. “unmodifiableList” will throw “java.lang.UnsupportedOperationException” if you try to add/remove an element from it, but other code may still have access to “modifiableList”, which is a back door. So, you can’t rely on the contents not changing.

An immutable collection ensures that the collection itself cannot be altered by deeply cloning or copying the collection. It does not let its reference escape via its constructors & getter methods as shown below:

Q8. What are the differences among HashSet, ArrayList, synchronized list/set, CopyOnWriteArraySet and CopyOnWriteArrayList?
A8. Compared to a list interface, a set interface does not allow duplicates. HashSet and ArrayList are not thread-safe and you need to provide your own synchronization with locks or use the java.util.Collections class that provides utility methods like

The above synchronizedXXX lock the whole collection like the legacy Vector whereas CopyOnWriteArraySet and CopyOnWriteArrayList are not only thread-safe, but also 1) more efficient as they allow concurrent multiple reads and single write. This concurrent read and write behavior is accomplished by making a brand new copy of the list every time it is altered.

The CopyOnWriteArrayList’s iterator 2) never throws ConcurrentModificationException while Collections.synchronizedList’s iterator may throw it.

It is also imperative to note that as per the Java API for the “Collections” class’s synchronizedXXX methods, the user must manually synchronize on the returned list when iterating over it as shown below.

When to favor a CopyOnWriteXXX structure? Write operations for a CopyOnWriteXXX can potentially be very slow as they involve copying the entire list. The CopyOnWriteXXX is favored when the number of reads & traversals via an iterator are significantly more than the number of writes. It also gives you fail safe iteration when you want to add/remove elements during iteration.

Q9. What are differences between a HasMap and a TreeMap?
A9. TreeMap is an implementation of a SortedMap, where the order of the keys can be sorted, and when iterating over the keys, you can expect that keys will be in order. HashMap on the other hand, makes no such guarantee on the order.

Q10. What are differences between a HashMap and a ConcurrentHashMap?
A10. HashMap is not thread-safe and you need to provide your own synchronization with Collections.synchornizedMap(hashMap), which will return a collection which is almost equivalent to the legacy Hashtable, where every modification operation on Map is locked.

What is wrong with this code? HashMap race condition example & how ConcurrentHashMap fixes it?

As the name implies, ConcurrentHashMap provides thread-safety by dividing the whole map into different segments based upon concurrency level and locking only particular segment instead of locking the whole map. In the ConcurrentHashMap API, you will find the following constants are used

and the constructor takes “concurrencyLevel” as an argument.

Instead of a map wide lock, ConcurrentHashMap maintains a list of 16 locks by default, which means each to lock on a single segment of the Map. Each segment can have multiple buckets. This indicates that 16 threads can modify the ConcurrentHashMap at the same time as long as each thread works on a different segment. The reads don’t block at all.

ConcurrentHashMap does not allow NULL key values, whereas HashMap can hold only one null key. This is because if map.get(key) returns a null, you can’t distinguish even with map.contains(key) call whether the value is null or the key itself is not present as the map might have changed between the map.get(key) and map.contains(key) calls due its concurrent read/write feature.

What is wrong with this code? ConcurrentHashMap atomic operations issue & how to fix?

Q11. What are differences between a HashMap and a LinkedHashMap?
A11. LinkedHashMap will iterate in the order in which the entries were put into the map. HashMap does not provide any guarantees about the iteration order.

Q12. What are differences between a Queue and a BlockingQueue?
A12. BlockingQueue is a Queue that supports additional operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element. The main advantage is that a BlockingQueue is that it provides a correct, thread-safe implementation with throttling.

  • The producers are throttled to add elements if the consumers get too far behind.
  • If the Queue capacity is limited, the memory consumption will be limited as well.

Q13. What are differences between an Array and a List?
A13.

  • Array is a fixed length data structure whilst a List is a variable length Collection class. List allows you to add and subtract elements even it is an O(n) operation in worst case scenario.
  • An array can use primitive data types or objects, but the List classes can only use objects.
  • Arrays are inflexible and do not have the expressive power of generic types.
  • List gives you the data abstraction as you can swap ArrayList, LinkedList, CopyOnWriteArrayList, etc depending on the requirements.

Q14. What is the difference between a Comparable and a Comparator?
A14. The Comparable interface provides a compareTo(..) method to be called while sorting naturally (i.e.by default). You can define your own ordering (i.e. custom) logic through the compare(…) method by implementing the Comparator interface.

[ Further readings: 4 Sorting objects in Java interview Q&As | Different ways to sort a collection of objects in pre and post Java 8 ]

Q15. What is the difference between ArrayList and Vector?
A15. Vector, Stack, and Hashtable are legacy data structures and must not to be used. All methods in these classes are synchronized (i.e. coarse grained lock), hence not efficient. Favor the concurrent data structures for concurrent reads and single write.

Java 8

Q16. What is the difference between “with and without lambdas” to the collections API?
A16. Lambdas introduced in Java 8 would be worthless if we didn’t have any means for applying lambdas to the JCF. So, “default methods” were introduced to Java interfaces, which has the benefit that default methods don’t break the implementations. In other words, interfaces in Java 8 onwards can now implement behavior via the default methods. So, default methods filter, map, reduce, forEach, etc are now added to the “java.util.stream.Stream” interface.

The Iterable interface with the Default method is shown below,

The same mechanism has been used to add Stream without breaking the implementing classes. Java 8 Streams, lambdas, intermediate vs terminal ops, and lazy loading with simple examples.

Q17. What is the difference between having the package java.util.stream and not having java.util.stream?
A17. The new java.util.stream package has been added to Java 8 to allow us to perform filter, map, and reduce operations with the help of lambda expressions on the collection classes. For example,

Questions to ponder

Q. If Java did not have a stack or map, how would you go about writing your own?
A. It is a best practice NOT to reinvent the wheel, and also writing your own API or framework is NOT a trivial task. The interviewer is trying to assess your depth of knowledge with the data structures with this question. Writing your own HashSet and HashMap example with code & diagrams.

Don’t worry, if these Q&As are not detailed

This post is for a quick brush-up on the differences. These Q&As are discussed in detail with code, examples & diagrams:

1. When to use which Java collection or data structure? and why?

2. Sorting objects in Java interview Q&A.

3. 60+ Java Collection API Interview Q&As.

Print Friendly
The following two tabs change content below.
Arulkumaran Kumaraswamipillai
Mechanical Engineering to Java freelancer since 2003. Published Java/JEE books via Amazon.com in 2005, and sold 35K+ copies. Books are outdated and replaced with this online Java training. join my LinkedIn group.
Arulkumaran Kumaraswamipillai

Mechanical Engineering to Java freelancer since 2003. Published Java/JEE books via Amazon.com in 2005, and sold 35K+ copies. Books are outdated and replaced with this online Java training. join my LinkedIn group.

Posted in Collection and Data structures, Differences Between X & Y, FAQs Core Java
Tags: , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*

800+ Interview Q&As ♥Free|♦FAQ (Mouse Hover for Full Text)

open all | close all

200+ Java FAQs – Memory Joggers

open all | close all

16 Java Key Areas to be a top-notch

open all | close all

80+ Java Tutorials – Step by step

open all | close all

100+ Java Coding Exercises

open all | close all

How good are your "Career Skills"?

open all | close all