Collections Interview Questions - Part2

Arraylist can be synchronized using:

Collections.synchronizedList(List list)
Other collections can be synchronized:
Collections.synchronizedMap(Map map)
Collections.synchronizedCollection(Collection c)
• Synchronization - ArrayList is not thread-safe whereas Vector is thread-safe. In Vector class each method like add(), get(int i) is surrounded with a synchronized block, thus making Vector class thread-safe.

  • Data growth - Internally, both the ArrayList and Vector hold onto their contents using an Array. When an element is inserted into an ArrayList or a Vector, the object will need to expand its internal array if it runs out of room. A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.
  • Performance - Since vector is thread-safe, the performance is slower than ArrayList.
• Implement Comparable interface for the Employee class and override the compareTo(Object obj) method in which compare the employeeID
  • Now call Collections.sort() method and pass the list as an argument.
  • Now consider that Employee class is a jar file.
    1. Since Comparable interface cannot be implemented, create Comparator and override the compare(Object obj, Object obj1) method .
    2. Call Collections.sort() on the list and pass comparator as an argument.
1. List can contain duplicate values but Set doesn't allow.

2.List allows retrieval of data to be in same order in the way it is inserted but Set doesn't ensures the sequence in which data can be retrieved.(Except HashSet)
There are three implementation of List interface:

ArrayList :It is a resizable array implementation. The size of the ArrayList can be increased dynamically also operations like add,remove and get can be formed once the object is created. It also ensures that the data is retrieved in the manner it was stored. The ArrayList is not thread-safe.

Vector: It is thread-safe implementation of ArrayList. The methods are wrapped around a synchronized block.

LinkedList: the LinkedList implements Queue interface too and provide FIFO (First In First Out) operation for add operation. It is faster than ArrayList if its mainly used forinsertion and deletion of elements.
Both collections implements Map. Both collections store value as key-value pairs. The key differences between the two are:

1. Hashmap is not synchronized in nature but hashtable is.

2. Another difference is that iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't. Fail-safe -if the Hashtable is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException?

3. HashMap permits null values and only one null key, while Hashtable doesn't allow key or value as null.
A Set is a collection that contains no duplicate elements. More formally, a set contains no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. HashSet,SortedSet and TreeSet are the commonly used class which implements Set interface.

SortedSet - It is an interface which extends Set. A the name suggest, the interface allows the data to be iterated in the ascending order or sorted on the basis of Comparator or Comparable interface. All elements inserted into the interface must implement Comparable or Comparator interface.

TreeSet - It is the implementation of SortedSet interface. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains). The class is not synchronized. The class uses Red-Black tree data structure.

HashSet - This class implements the Set interface, backed by a hash table (actually 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. This class permits the null element. This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets
• Arrays are created of fix size whereas ArrayList is dynamic in nature and can vary its length. Also the size of array cannot be incremented or decremented. But with arrayList the size is variable.

  • Once the array is created elements cannot be added or deleted from it. But with ArrayList the elements can be added and deleted at runtime. List list = new ArrayList(); list.add(1); list.add(3); list.remove(0) // will remove the element from the 1st location.
  • ArrayList is one dimensional but array can be multidimensional. int[][][] intArray= new int[3][2][1]; // 3 dimensional array
  • Array can contain objects of a single data type or class. ArrayList if not used with generic can contain objects of different classes
  • Adding new elements is pretty fast for either type of list. Inserting element to nth location in arraylist and to first location in linkedlist takes O(1).
  • For the ArrayList, doing random lookup using "get" is faster O(1), but for LinkedList O(n), it's slow. It's slow because there's no efficient way to index into the middle of a linked list. Linkedlist lookup always start from 1st location.
  • When removing elements, using ArrayList is slow. This is because all remaining elements in the underlying array of Object instances must be shifted down for each remove operation. But LinkedList is fast, because deletion can be done simply by changing a couple of links. So an ArrayList works best for cases where you're doing random access on the list and a LinkedList works better if you're doing a lot of editing in the middle of the list.
For loop does not allow updating the collection(add or remove) whereas Iterator does. Also Iterator can be used where there is no clue what type of collections will be used because all collections implement Iterator interface.
It follows Iterator design pattern. Iterator Pattern is a type of behavioral pattern. The Iterator pattern is one, which allows you to navigate through a collection of data using a common interface without knowing about the underlying implementation. Iterator should be implemented as an interface. This allows the user to implement it anyway its easier for him/her to return data. The benefits of Iterator are about their strength to provide a common interface for iterating through collections without bothering about underlying implementation.

Example of Iteration design pattern - Enumeration The class java.util.Enumeration is an example of the Iterator pattern. It represents and abstract means of iterating over a collection of elements in some sequential order without the client having to know the representation of the collection being iterated over. It can be used to provide a uniform interface for traversing collections of all kinds.
It is preferred because:

  • If later on code needs to be changed from ArrayList to Vector then only at the declaration place we can do that.
  • The most important one – If a function is declared such that it takes list. E.g void showDetails(List list);
  • When the parameter is declared as List to the function it can be called by passing any subclass of List like ArrayList, Vector, LinkedList making the function more flexible.
HashSet implements hashTable internally to store the data. The data passed to hashset is stored as key in hashTable with null as value.
A concurrentHashMap is thread-safe implementation of Map interface. In this class put and remove method are synchronized but not get method. This class is different from Hashtable in terms of locking; it means that hashtable use object level lock but this class uses bucket level lock thus having better performance. The allowed concurrency among update operations is guided by the optional concurrencyLevel constructor argument (default 16), which is used as a hint for internal sizing. The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. Because placement in hash tables is essentially random, the actual concurrency will vary.

Ideally, you should choose a value to accommodate as many threads as will ever concurrently modify the table. Using a significantly higher value than you need can waste space and time, and a significantly lower value can lead to thread contention. But overestimates and underestimates within an order of magnitude do not usually have much noticeable impact. A value of one is appropriate when it is known that only one thread will modify and all others will only read. Also, resizing this or any other kind of hash table is a relatively slow operation, so, when possible, it is a good idea to provide estimates of expected table sizes in constructors.
Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the 'n' location and get the element. It does not traverse through n-1 elements.

In Iterator based access, the cursor has to traverse through each element to get the desired element.So to reach the 'n'th element it need to traverse through n-1 elements.

Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.

Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.

Traversal or search in index based datastructure is faster.

ArrayList is index access and LinkedList is iterator access.
A list implementation can be made read only using Collections.unmodifiableList(list). This method returns a new list.
If a user tries to perform add operation on the new list; UnSupportedOperationException is thrown.
To sort the elements in the reverse natural order of the strings, get a reverse Comparator from the Collections class with reverseOrder(). Then, pass the reverse Comparator to the sort() method.

List list = new ArrayList();
Comparator comp = Collections.reverseOrder();
Collections.sort(list, comp)
A null element can be added only if the set is of size 1 because when a second element is added then as per set defination a check is made to check duplicate value and comparison with null element will throw NullPointerException. HashSet is based on hashMap and can contain null element.
Using Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
A hashtable-based Map implementation with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently than other Map implementations.
HashMap is fastest, ConcurrentHashMap,Collections.synchronizedMap,HashTable.
The IdentityHashMap uses == for equality checking instead of equals(). This can be used for both performance reasons, if you know that two different elements will never be equals and for preventing spoofing, where an object tries to imitate another.
List < ? > is List of unknown type while List< Object > is essentially List of any Type.

You can assign List< String >, List< Integer > to List< ? > but you can not assign List< String > to List< Object >.

This is because List< Object > can store any any thing including String, Integer etc but List< String > can only store Strings.
Bounded wildcards are :

< ? extends T > which impose an upper bound by ensuring that type must be sub class of T.
< ? super T > where its imposing lower bound by ensuring Type must be super class of T.
< ? > represent and unbounded type because < ? > can be replace with any Type.
In first glance it looks like : String is Object so List can be used where List< Object > is required but this is not true. It will result in compilation error.

This is because List< Object > can store any any thing including String, Integer etc but List< String > can only store Strings !!.
HashMap stores key-value pair in Map & Map.Entry is static nested class implementation. HashMap works on hashing algorithm and uses hashCode() and equals() method in put and get methods.

When we call put method by passing key-value pair : HashMap uses Key hashCode() with hashing to find out the index to store the key-value pair. The Map.Entry is stored in the LinkedList, so if there are already existing entry, it uses equals() method to

check if the passed key already exists. If entry already exists then it overwrites the value else it creates a new entry and store this key-value Entry.

When we call get method by passing Key : Again it uses the hashCode() to find the index in the array and then use equals() method to find the correct Entry and return it’s value.

Remember : hashCode() is used to narrow down the results for fast searching. objects having same hashCode() doesn't mean that they're same, It only means that those objects are stored in same bucket.
Generics provides compile time type-safety and ensures that you only insert correct Type in collection and avoids ClassCastException during runtime.
Fail-fast Iterators fail as soon as they realized that structure of Collection has been changed since iteration has begun. ( Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection ). Fail-fast behaviour is implemented by keeping a modification count and if iteration thread realizes the change in modification count it throws ConcurrentModificationException
You should first try to find another alternative iterator which are fail-safe.
For example if you are using List and you can use ListIterator.