Collections

Q1. Tell us the collections hierarchy.
Ans.
 

Q2. Talk about collections and Collections in Java.

Ans. collection(s) is a group of various Container classes in Java.

Collections is a class which consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.

The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.

The "destructive" algorithms contained in this class, that is, the algorithms that modify the collection on which they operate, are specified to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. These algorithms may, but are not required to, throw this exception if an invocation would have no effect on the collection. For example, invoking the sort method on an unmodifiable list which is already sorted may or may not throw UnsupportedOperationException.

This class is a member of the Java Collections Framework.

Q3. Talk about Collections.sort() method.

Ans.sort(List<T> list): Sorts the specified list into ascending order, according to the natural ordering of its elements.
sort(List<T> list, Comparator<? super T> c): Sorts the specified list according to the order induced by the specified comparator.

Q4. What are the differences between Comparator and Comparable?
Ans.Comparable: Comparing itself with another object i.e comparing own instances. This contains compareTo(Object o) method. 

Comparator: Comparing two different objects. The class is not comparing its instances, but some other class’s instances. This contains compare(Object o1, Object o2) method.

You might want to create a Comparator object for the following.

• Multiple comparisons: To provide several different ways to sort something.            Ex: You might want to sort a Person class by name, ID, age, height etc. You would define a Comparator for each of these to pass to the sort() method.
• System class: To provide comparison methods for classes that you have no control over. Ex: You could define a Comparator for Strings that compared them by length.
• Strategy pattern: To implement a Strategy pattern, which is a situation where you want to represent an algorithm as an object that you can pass as a parameter, save in a data structure, etc.

If your class objects have one natural sorting order, you may not need this.

Q5. Difference between instance and static addAll method of Collection.

Ans.

Instance method can take only one argument of another Collection object.

i.e c.addAll(c2) // where c and c2 are collection objects

Static method can accept variable argument list.
i.e Collections.addAll(c, c2, 1, 2, 3, 4)
c is the collection object to which elements are added
c2 is the collection object of which elements are added

We add other elements also to c, alongwith c2.

Q6. What happens if we don't specify a object type (in angled brackets) while initializing a array list.

ex: saying new ArrayList() instead of ArrayList<Integer>()

Ans. If I don't specify the object type, it automatically inherits from type Object. In short, program compiles and run properly though.

Q7. How can one prove that the array is not null but empty?

Ans. You can do it by printing array.length - it will print 0. That means it is empty. But if it would have been null, then it would have thrown a NullPointerException.

Q8. What is the difference between Array List and Array.

Ans

1. Array is a primitive data structure, which stores the values in indexed format.  ArrayList is a more like a vector (re-sizeable array). It is a collection and stores any value as an object. If you know the size, then use array, if not try array list. When you have a fixed array, there is no difference in use. 

2. There are several differences, but the biggest, is that an arraylist grows as you add items to it and does not have to be redimmed to allow additional elements. Arrays cannot be changed in size at runtime (except using 'ReDim' which will create a new array, copy the old array in the new array and destroy the old array).

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.

It's said that (not sure if it's true), a Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent.

3. Arraylists are sortable, searchable, etc – they are far superior to arrays.

Q9. What are the limitations of Arrays.asList?

Ans. A limitation of Arrays.asList( ) is that it takes a best guess about the resulting type of the List, and doesn’t pay attention to what you’re assigning it to. Sometimes this can cause a problem:

// holding   AsListInference.java

// Arrays.asList() makes its best guess about type.

import java.util.*;

class Snow {}

class Powder extends Snow {}

class Light extends Powder {}

class Heavy extends Powder {}

class Crusty extends Snow {}

class Slush extends Snow {}

public class AsListInference {

public static void main(String[] args) {

List<Snow> snow1 = Arrays.asList(

new Crusty(), new Slush(), new Powder());

// Won’t compile:

// List<Snow> snow2 = Arrays.asList(

// new Light(), new Heavy());

// Compiler says:

// found : java.util.List<Powder>

// required: java.util.List<Snow>

// Collections.addAll() doesn’t get confused:

List<Snow> snow3 = new ArrayList<Snow>();

Collections.addAll(snow3, new Light(), new Heavy());

Q10. Define collections toArray() method.

Ans. You can convert any Collection to an array using toArray(). This is an overloaded method; the no-argument version returns an array of Object, but if you pass an array of the target type to the overloaded version, it will produce an array of the type specified (assuming it passes type checking). If the argument array is too small to hold all the objects in the List (as is the case here), to Array() will create a new array of the appropriate size.

Q11. What is sorting technique used by Arrays.sort().

Ans. In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.

The algorithm at present is a mergesort with an insertion sort once you get down to a certain size of sublists (N.B. this algorithm is very probably going to change in Java 7).

Java's sorting algorithm

The sorting algorithm used is a version of mergesort1. Mergesort is based on a "divide and conquer" strategy: we recursively divide the list into two halves and sort each half, then merge the two sorted halves back together. As we break the data down into smaller and smaller parts, we eventually reach a critical size where it's not worth dividing any more, and we sort in situ. Java uses an insertion sort for these 'atomic' sorts. Together, this gives Java's sort routine the following characteristics:
● stable: i.e. if two elements are equal, their order won't be swapped after sorting.

● Because of the requirement to merge lists together into a new list, the algorithm operates on a copy of the data: when you call Arrays.sort(), the first thing the method does is take a clone of the array. Taking a clone of the array means taking a copy of the list of references, not of the actual data. The cost is generally negligible for large-ish arrays, but relatively considerable for sorting very small sets of data.

● The underlying insertion sort has a worst case where the input data is in reverse order; thus in principle, it is possible to hit an unlucky case consisting of a series of sub-lists in reverse order.

● In terms of recursion, this hybrid algorithm improves on some "textbook" cases of recursing right down until the sublist size is 1 or 2 (but at the expense of a less constant sort time as mentioned in the previous point).

● In most practical cases, doubling the size of the list more or less doubles the time taken to sort.

Q12. What is the difference between List and set? How do you maintain ordering feature in set?

Ans. List allows duplicate elements and maintains the order of elements. However, set doesn't allow duplicates and doesn't maintain order of the elements. To maintain the order of elements in a set, use Linked Hashset.

Q13. Difference btw add(Object o) and addElement(Object o) in Vector?

Ans:
add(int indx, Object e): Inserts the specified element at the specified position in this Vector. Return type is void

add(Object e): Appends the specified element to the end of this Vector. Return type is boolean

addElement(Object obj): Adds the specified component to the end of this vector, increasing its size by one. Return type is void.This method is identical in functionality to the add(Object) method (which is part of the List interface). add(Object) is due the fact that Vector implements List Interface and it has appeared since Java 1.2, time when Vector was moved to Collections. The collection classes from earlier releases, Vector and Hashtable, have been retrofitted to implement the collection interfaces. addElement is "original" Vector's method.

Q14. Tell me something about capacity increment in Vector?

Ans. Capacity increment is the amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity.

Q15. What is the need for iterator?

Ans. The concept of an Iterator (another design pattern) can be used to achieve the abstraction. An iterator is an object whose job is to move through a sequence and select each object in that sequence without the client programmer knowing or caring about the underlying structure of that sequence i.e underlying structure can be Set, Array, Linked List or queue or anything else. Client need not know about the same, as he will make use of iterator() to traverse and iterator will take care of everything. In addition, an iterator is usually what’s called a lightweight object: one that’s cheap to create.

Q16. Explain List Iterator.

Ans. ListIterator is bidirectional. It can also produce the indexes of the next and previous elements relative to where the iterator is pointing in the list, and it can replace the last element that it visited using the set() method. You can produce a ListIterator that points to the beginning of the List by calling listIterator(), and you can also create a ListIterator that starts out pointing to an index n in the list by calling listIterator(n).

Also, regarding modification of collection, ListIterator has add(), remove() and set() methods, whereas Iterator has only remove method.

Q17. How does .remove() or .set() method work in iterator?

Ans. These operations work on last element being visited i.e. element returned by next() in case of iterators and next()/previous() in case of list iterators.

Q18. What do you mean by iterators are fail-safe or fail-fast?

Ans. If the map is "structurally" modified i.e. elements are added/removed (set operation is not structural modification) at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behaviour at an undetermined time in the future.

Q19. When do you get a ConcurrentModificationException while working with collections?

Ans. An iterator is considered fail-fast if it throws a ConcurrentModificationException under either of the following two conditions:

1. In multithreaded processing: If one thread is trying to modify a Collection while another thread is iterating over it.

2. In single-threaded or in multithreaded processing, if after the creation of the Iterator, the container is modified at any time by any method other than Iterator's own remove or add methods.

Q20. What happens to Iterator and Enumerator if collection is modified after obtaining iterator or enumerator?
Ans. If collection is modified after obtaining iterator or enumerator:

1. Enumeration keeps state information about the collection; if the collection is modified while the enumeration is active, the enumeration may become confused. The enumeration fails in some random way, possibly through an unexpected runtime exception (e.g., a NullPointerException).

2. Iterators behave somewhat differently. If the underlying collection of an iterator is modified while the iterator is active, the next access to the iterator throws a ConcurrentModificationException, which is also a runtime exception. Unlike enumerations, if the iterator fails, the underlying collection can still be used. The way in which iterators fail immediately after a modify operation is called "fail-fast."

Q21. Explain Iterable interface.

Ans. Java SE5 introduced a new interface called Iterable which contains an iterator() method to produce an Iterator, and the Iterable interface is what foreach uses to move through a sequence. So if you create any class that implements Iterable and implements iterator() method of the interface, you can use it in a foreach statement:

Ex: 

public class MyCollection<E> implements Iterable<E>{

     public Iterator<E> iterator() {

          return new MyIterator<E>();

                  // where MyIterator is implementation of Iterator interface.

          }

}

public class MyIterator <T> implements Iterator<T> {

          public boolean hasNext() { //implement... }

          public T next() { //implement...; }

          public void remove() { //implement... if supported. }

}

Usage:

public static void main(String[] args) {

          MyCollection<String> stringCollection = new MyCollection<String>();

          for (String string : stringCollection) {

              System.out.println(string);

          }

}

Q22. Do you any drawback in design of stack?

Ans. If you want only stack behavior, inheritance is inappropriate here because it would produce a class with all the rest of the LinkedList methods.

Q23. Is it true that Map implements collection?
Ans. False

Q24. What is the difference btw entrySet() and keySet() ( in Map).

Ans. entrySet() gives a set view of the mappings in the map whereas keySet() gives a set view of the keys in the map. entrySet() provides a view on the map and not a copy. Thus if you modify entrySet(), original set will be modified.

Q25. Difference b/w HashSet(HashMap) and TreeSet(TreeMap)

Ans. HashSet is unsorted and has access time of O(1). TreeSet is a sorted set. It’s implemented on Red Black Tree, thus providing O(log n) time for all operations. 

Biggest advantage of latter is that elements are always sorted at any point of time.

Q26. What is default implementation of hashcode method.

Ans. The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, hashCode method must consistently return the same integer. This integer need not remain consistent from one execution of an application to another execution of the same application.
• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
• It is not required that if two objects are unequal according to equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtable.

Hashcode is NOT address, it says that it is based on the address. Consider that hash codes are 32 bits, but there are 64-bit JVMs. Clearly, directly using the address wouldn't always work. Thus, the default hash code of an object will not change with change in address of object after garbage collector runs.

Q27. Is it necessary to override hashcode() method if you override equals() method.

Ans. The value returned by hashCode() by default is the object's hash code. By definition, if two objects are equal, their hash code must also be equal. If you override the equals() method, you change the way two objects are equated and Object's implementation of hashCode() is no longer valid. Therefore, if you override the equals() method, you must also override the hashCode() method as well.

Q28. What are the properties for equals() method?

Ans.

1. Reflexive

2. Symmetric

3. Transitive

4. Consistent

5. x.equals(null) is false

Q29. Do we need to implement or override both equals() and hashcode() method in Set and Map?

Ans. equals() -> Must be implemented for all forms of Set and Map.

hashcode() -> Necessary for HashSet(), LinkedHashSet() and HashMap(), LinkedHashMap() but *NOT* for TreeSet() and TreeMap()

NOTE: Value produced by hashcode() is not the index into the hashmap or hashset. Its computed further to calculate index. Mostly, it is modulo operation.

Q30. Data structure for accessing elements in least recently used way.

Ans. LinkedHashMap initialized as below

         new LinkedHashMap( capacity, load_factor, true);

Q31. Difference btw HashMap and HashTable?

Ans.

1. Both provide key-value access to data. The Hashtable is one of the original collection classes in Java. HashMap is part of the new Collections Framework, added with Java 2.

2. The key difference between the two is that access to the Hashtable is synchronized on the table while access to the HashMap isn't. You can add it, but it isn't there by default.

3. Another difference is that iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't. If you change the map while iterating, you'll know.

4. HashMap permits null values in it, while Hashtable doesn't.

Synchronized means only one thread can modify a hash table at one point of time. Basically, it means that any thread before performing an update on a hashtable will have to acquire a lock on the object while others will wait for lock to be released. 

Ex: HashMap usage example:
HashMap hm = new HashMap<Integer, Integer>();

Set set = hm.entrySet();

Iterator i = set.iterator();

while (i.hasNext()) {

      Map.Entry me = (Map.Entry) i.next();

      System.out.println(me.getKey());

}

Q32. What are the primary considerations when implementing a user defined key?

Ans. 

1. You should override the equals() and hashCode() methods from the Object class. If a class overrides equals(), it must override hashCode().

2. If two objects are equal, then their hashCode values must be equal as well.

3. If a field is not used in equals(), then it must not be used in hashCode().

4. It is a best practice to implement the user defined key class as an immutable object.

Q33. How to create an immutable class?

Ans. To create an immutable class following steps should be followed:

1.  Don't provide "setter" methods — methods that modify fields or objects referred to by fields.

2.  Make all fields final and private.

3.  Don't allow subclasses to override methods. The simplest way to do this is to declare the class as final. A more sophisticated approach is to make the constructor private and construct instances in factory methods.

4.  If the instance fields include references to mutable objects, don't allow those objects to be changed:

o Don’t provide methods that modify the mutable objects.

o Don’t share references to the mutable objects. Never store references to external, mutable objects passed to the constructor; if necessary, create copies, and store references to the copies. Similarly, create copies of your internal mutable objects when necessary to avoid returning the originals in your methods.

Q34. What are the advantages of immutable objects?

Ans. Maximum reliance on immutable objects is widely accepted as a sound strategy for creating simple, reliable code. The advantages are: 

1)    Immutable objects are automatically thread-safe; the overhead caused due to use of synchronisation is avoided.

2)    Once created the state of the immutable object cannot be changed, so there is no possibility of them getting into an inconsistent state.

3)    Freedom to cache, as they will never change and hence will reflect the correct data.

4)    Need not implement clone and copy constructors. 

5)    The best use of the immutable objects is as the keys of a map.

6) Safe against bad code. If someone tries to change a property of immutable object by mistake, he will get an error. On the other hand, if it was mutable, property would have been changed though not required.

Disadvantages:

Cost of creating a new object as opposed to updating an object in place. The impact of object creation is often overestimated. However, it can be offset by some of the efficiencies associated with immutable objects. These include decreased overhead due to garbage collection, and the elimination of code needed to protect mutable objects from corruption.

           

Q35. Why String class is made immutable in Java?

Ans. Though, performance is also a reason since it maintains internal String pool to make sure the same String object is used more than once without having to create/re-claim it.  However, main reason is Security.

Ex: Suppose you need to open a secure file which requires the users to authenticate themselves. Let's say there are two users named 'user1' and 'user2' and they have their own password files 'password1' and 'password2', respectively. Obviously 'user2' should not have access to 'password1' file.  Now, since filenames in Java are specified by using Strings. Even if you create a 'File' object, you pass the name of the file as a String only and that String is maintained inside the File object as one of its members.

Had String been mutable, 'user1' could have logged into using his credentials and then somehow could have managed to change the name of his password filename (a String object) from 'password1' to 'password2' before JVM actually places the native OS system call to open the file. This would have allowed 'user1' to open user2's password file. Understandably it would have resulted into a big security flaw in Java.

With Strings being immutable, JVM can be sure that the filename instance member of the corresponding File object would keep pointing to same unchanged "filename" String object. The 'filename' instance member being a 'final' in the File class can anyway not be modified to point to any other String object specifying any other file than the intended one (i.e., the one which was used to create the File object).

Q36. Default size/capacity of various collections.

Ans. 

Collection    capacity   size     Load factor(if applicable)
ArrayList        10           0         N/A
Vector           10           0         N/A
HashTable      11           0         0.75
PriorityQueue 11          0          N/A
HashSet          16          0         0.75
HashMap         16          0         0.75

Constructs a new, empty hashtable with a default initial capacity (11) and load factor, which is 0.75.

Q37. What is WeakHashMap?

Ans. WeakHashMap is a hashtable based Map implementation with weak keys. Both null values and the null key are supported. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use i.e. presence of a mapping for a given key will not prevent the key from being discarded by the GC. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently from other Map implementations. Each key object in a WeakHashMap is stored indirectly as the referent of a weak reference. Therefore a key will automatically be removed only after the weak references to it, both inside and outside of the map, have been cleared by the garbage collector.

This class is intended primarily for use with key objects whose equals methods test for object identity using the == operator. Once such a key is discarded it can never be recreated, so it is impossible to do a lookup of that key in a WeakHashMap at some later time and be surprised that its entry has been removed. However, this class will also work with key objects whose equals methods are not based upon object identity, such as String instances. With such re-creatable key objects, however, the automatic removal of WeakHashMap entries whose keys have been discarded may prove to be confusing.

The behaviour of the WeakHashMap class depends in part upon the actions of the garbage collector. Because the garbage collector may discard keys at any time, a WeakHashMap may behave as though an unknown thread is silently removing entries. In particular, even if you synchronize on a WeakHashMap instance and invoke none of its mutator methods, it is possible for the size method to return smaller values over time, for the isEmpty method to return false and then true, for the containsKey method to return true and later false for a given key, for the get method to return a value for a given key but later return null, for the put method to return null and the remove method to return false for a key that previously appeared to be in the map, and for successive examinations of the key set, the value collection, and the entry set to yield successively smaller numbers of elements.

Note: The value objects in a WeakHashMap are held by ordinary strong references. Thus care should be taken to ensure that value objects do not strongly refer to their own keys, either directly or indirectly, since that will prevent the keys from being discarded. Note that a value object may refer indirectly to its key via the WeakHashMap itself. One way to deal with this is to wrap values themselves within WeakReferences before inserting, as in: m.put(key, new WeakReference(value)), and then unwrapping upon each get.

The iterators returned by the iterator method of the collections returned by all of this class's "collection view methods" are fail-fast.

Q38. Give me a WeakHashMap usage example.
Ans. A good example of WeakHashMap in action is the ThreadLocal class. ThreadLocal uses a WeakHashMap internally where the keys are Threads. When you call get(), the ThreadLocal class gets a reference to the current thread and looks up its value in the WeakHashMap. When the thread dies, it becomes unreachable and WeakHashMap automatically removes its mapping. If ThreadLocal used a regular HashMap, then the Threads stored in it would never become unreachable and they could hang around for a long, long time. This would essentially be a memory leak.

Q39. What is IdentityHashMap?
Ans. This class implements the Map interface with a hash table, using reference-equality in place of object-equality when comparing keys (and values). In an IdentityHashMap, two keys k1 and k2 are considered equal if and only if (k1==k2). In normal Map implementations (like HashMap) two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2)). Like WeakHashMap, it permits null keys and null values.

This class is NOT a general-purpose Map implementation! It intentionally violates Map's general contract, which mandates the use of the equals method when comparing objects. This class is designed for use only in the rare cases wherein reference-equality semantics are required.

A typical use of this class is topology-preserving object graph transformations, such as serialization or deep-copying. To perform such a transformation, a program must maintain a "node table" that keeps track of all the object references that have already been processed. The node table must not equate distinct objects even if they happen to be equal. Another typical use of this class is to maintain proxy objects. For example, a debugging facility might wish to maintain a proxy object for each object in the program being debugged.

This class has one tuning parameter (which affects performance but not semantics): expected maximum size. This parameter is the maximum number of key-value mappings that the map is expected to hold. Internally, this parameter is used to determine the number of buckets initially comprising the hash table. The precise relationship between the expected maximum size and the number of buckets is unspecified. For many JRE implementations and operation mixes, this class will yield better performance than HashMap (which uses chaining rather than linear-probing).

The iterators returned by all of this class's "collection view methods" are fail-fast.

Q40. What is DBI, i.e double brace initialization?
Ans. I had run into a use case of having to initialize a private static Map with a set of predefined values. Usually we define the variable and perform the setting of values via a static block. For some reason, this static block reminds me of the procedural way of doing things whereas we would like the initialization of the collection with its definition. While it is easy to do this for ArrayLists (by passing Arrays.asList to the constructor arg), I thought that there exists no such solution for Maps until now.

private static final Map<Integer, String> myConstantMap =
     new HashMap<Integer, String>() {

          {
               put(1, “abc”);               put(2, “def”);          }
     }

While this is not as straight-forward as the literal initialization done in Perl or Javascript, I was happy that something like this atleast existed. This is called the Double Brace Initialization (DBI) idiom. http://c2.com/cgi/wiki?DoubleBraceInitialization gives further details. In a nutshell, this piece of code creates an anonymous sub class which may be initialized in the inner brace. Since this is creating a subclass on the fly, it cannot be done for final classes (which are mostly not a problem with collections classes).

On further searching, I came across very different opinions. People either love it or loathe it. So it is important that we understand the reason behind their rationales and be mindful as to where we should use (and not use) them.

Cons:
1. Cannot be applied for final classes, except for Collections.
2. An additional anonymous class in your jar.
3. Objects created via DBI break the popular implementation of equals when compared against objects created without DBI (ones where class name comparisons are done -- not in most collections classes). Objects created by DBI will never be equal to objects created without it. However, collection classes should be fine.
4. Performance overhead of creating several anonymous classes.
5. This initializer is run before constructors, something that not everyone is readily aware of making it open for a newcomer to shoot themselves in the foot.
6. If the class in question is serializable, the new anonymous subclass thus created also needs to specify the serial version id -- pain to maintain. Also a problem if you wish to send it across the wire, where you always statically assume the class name of the object being resurrected.

Pros:
1. Elements are nested and inline making it more OO (than procedural).
2. Better readability
3. Performance overhead is minimal when usage is extremely sparse.
4. No worry about the order of execution of static block.

It would be nice if Java only created and initialized an instance, not create a new class for DBI and any anonymous "class" that does not add fields or override methods.