Importance Rating *****
Level: Basic
Java collections is and always been a very popular topic among interviewers. There are many FAQs that are from java collections framework. It is no longer sufficient to just know basic collections such as HashMaps and ArrayLists in java 1.4. Numerous new collection interfaces and their implementations have been added in java 1.5 and java 1.6. To get the edge, in addition to having a good grasp of the basic java 1.4 collections, you also need to know at least the key features of the new collections added and why they were added.
This article gives an overview of the java collections framework in java 1.4. These are the base java collections and are a stepping stone to the new collections and features added in java 1.5 and java 1.6
Recommended Study Strategy
Briefly go through the 'Interview keywords' and 'Interview Key Concepts' below and make sure that you clearly understand each keyword and concept. Then go through the 'Interview FAQ' and the 'Get the Edge' sections.
Interview Keywords
- Collection Interfaces in Java 1.4 - Collection, List, Set, SortedSet, Map, SortedMap
- Collection Implementations in java 1.4 - Vector, ArrayList, LinkedList, TreeSet, HashSet, LinkedHashSet, Hashtable, HashMap, TreeMap, LinkedHashMap, IdenitityHashMap, WeakHashMap
- Collections, sort(), Comparator, Comparable, hashcode(), equals()
Interview Key Concepts
- Memorize the names of the basic collection interfaces in java 1.4
- Memorize the names of the basic collection implementations in java 1.4
- Understand the key features of collection interfaces.
- Understand the key features of collection concrete classes.
- Understand the main differences between the collection classes.
- Given a scenario, Identify which collection is most efficient to use.
- Understand the advantages and disadvantages of each collection.
- Understand the internal representation and working of HashMap.
- What do you understand by collections framework in java?
The java collections framework is a unified architecture for representing and manipulating collections, allowing them to be manipulated independently of the details of their representation. The java collections framework reduces programming effort while increasing performance. It allows for interoperability among unrelated APIs, reduces effort in designing and learning new APIs, and fosters software reuse.
Collection is the base interface in collections framework. List and Set interfaces extend from Collection interface. Map interface does not extend from Collection interface, but is a part of the collections framework. - What is the difference between List, Set and Map interfaces?
Set interface represents a collection that contains no duplicate elements.
Map interface represents a collection that maps keys to values. A map cannot contain duplicate keys and each key can map to at most one value.
List interface represents an ordered collection. This interface provides methods to efficiently insert and remove multiple elements at an arbitrary point in the list, access elements by their position in the list (index), and search for elements in the list. Unlike sets, lists typically allow duplicate elements. - What is the difference between Vector and ArrayList?
Vector is a legacy collection class introduced in Java 1.0. ArrayList was introduced in java 1.2, as part of java collections framework.
Vector is thread-safe as its methods are synchronized where as the methods in ArrayList are not synchronized. Since ArrayList is not synchronized its performance is better than Vector.
Internally both Vector and ArrayLisy use the Array to store the data. But by default vector doubles the size of its array when its size is dynamically increased, where as ArrayList increases the size of its array by half of its size. - What is the difference between ArrayList and LinkedList?
Unlike ArrayList a LinkedList is a doubly-linked list that provides methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).
Random lookup is fast with ArrayList, but slow with LinkedList since access to any index requires you to traverse multiple nodes.
Adding and removing elements using a random index with LinkedList is generally considered to be faster than an ArrayList, but this depends on the size of the collection and the index position. - What is the difference between TreeSet and Hashset?
Hashset implements the Set interface, backed by a HashMap instance. It makes no guarantees as to the iteration order of the set; in particular, it does not
guarantee that the order will remain constant over time.
TreeSet is a sorted set that guarantees that the elements will be in ascending order. The elements are sorted according to the natural order of the elements,
or by the comparator provided at set creation time. - What is the difference between HashSet and LinkedHashSet?
LinkedHashSet differs from HashSet in that it maintains a doubly-linked list containing the hashcode and the original order of the items. This linked list
defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). - What is the difference between Hashtable and HashMap?
Hashtable is a legacy collection class introduced in Java 1.0. in java 1.2, as part of java collections framework.
Hashtable is thread-safe as its methods are synchronized where as the methods in HashMap are not synchronized. Since HashMap is not synchronized its performance is better than Hashtable.
Hashtable does not allow null keys or values, HashMap allows null values and 1 null key. - What is the difference between HashMap and TreeMap?
TreeMap is a Red-Black tree based implementation of the SortedMap interface. TreeMap guarantees that the map will be in ascending key order, sorted according
to the natural order for the key's class, or by the comparator provided at creation time, depending on which constructor is used.
Searching for an item in TreeMap is slower than HashMap. - What is the difference between HashMap and LinkedHashMap?
The basic difference between HashMap and LinkedHashMap is that LinkedHashMap maintains the insertion order of elements. LinkedHashMap maintains a doubly-linked list containing the hashcode and the original order of items. This avoids the generally chaotic ordering provided by HashMap (and Hashtable), but without incurring the increased cost associated with TreeMap. The performance of LinkedHashMap is similar to HashMap. - How do you sort collections? What is the difference between comparator and comparable?
If the class whose objects are represented by the collection implements the interface 'Comparable', then the collection can be sorted by using Collections.sort() or Arrays.sort().
The second option is provide a Comparator for the collection to use. The advantage of the Comparator is that you can create multiple Comparators that can be used
to sort the collection in multiple ways. - What is IdentityHashMap?
The IdentityHashMap identical to HashMap with the exception that a key is considered equal to another key only if they are pointing to the exact same object. All other implementations of Map use the equals() method to determine if two keys are equal. The IdentityHashMap uses the == comparator. - What is weak HashMap?
The WeakHashMap is identical to the HashMap with the exception that entries in this class do not count as a reference against the key contained in this Map. So the garbage collector may remove keys from the WeakHashMap and garbage collect the object. - What methods do you have to override to use an object as a key in a HashMap ot Hashtable; or as an element in a HashSet?
Any Object that is used as a key in a HashMap or Hashtable, or as an element in a HashSet, must override the hashCode( ) and equals( ) methods from the Object class. It is also best practise to implement this class as immutable.
Get the Edge
- Understand the key features of each collection in java 1.4. If you know the key features of each collection, you can easily answer questions regarding the difference between any two collections, or questions on which collection to use based on a given use case or requirement.
- Understand how hashing works and how the data is represented internally in HashMap (or Hashtable or HashSet). Understand the importance of hashcode() and equals() methods. Understand clearly what happens when you try to retrieve a value or search for a value from HashMap or Hashtable based on the key.
- Understand how sorting works in collections. Understand the difference between comparable and comparator.
- Understand the key methods in the collections utility class and how you can make collections thread safe.
- Generally the interviewer will start off with a generic question such as 'what do you know about collections framework' or ' What is the difference between vector and ArrayList', which gives you the flexibility to move the questioning to topics that you are strong in. For example in most of my interviews I bring up 'hashcode' and invariably the questions move towards HashMap, Hashtable, hashcode(), equals() etc; topics that I enjoy talking about.
Posts
