Java InterView Questions - Collections

Difference between HashMap and HashTable? Can we make hashmap synchronized?

1. The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesn’t allow nulls).
2. HashMap does not guarantee that the order of the map will remain constant over time.
3. HashMap is non synchronized whereas Hashtable is synchronized.
4. Iterator in the HashMap is fail-safe while the enumerator for the Hashtable isn't.

Note on Some Important Terms
1)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.

2)Fail-safe is relevant from the context of iterators. If an iterator has been created on a collection object and some other thread tries to modify the collection object "structurally”, a concurrent modification exception will be thrown. It is possible for other threads though to invoke "set" method since it doesn’t modify the collection "structurally”. However, if prior to calling "set", the collection has been modified structurally, "IllegalArgumentException" will be thrown.

HashMap can be synchronized by

Map m = Collections.synchronizeMap(hashMap);

Why are wait(), notify(), and notifyAll() in the Object class?

Threads can use Objects to transmit messages from one thread to another, and these methods allow that to happen. A Thread calls wait() to say "I am waiting for a message to be sent to this object." Another thread can call notify() to say "I am sending a message to that object." The Object is therefore a conduit through which threads communicate without explicitly referencing each other. If the methods were in the Thread class, then two threads would need to have references to one another to communicate. Instead, all communicating threads just need to agree to use some specific shared resource.

how to retrives the values from Map

1. Set set=hMap.entrySet();

2. Iterator iii=set.iterator();

3. while (itr.hasNext()) {

4. Object object = (Object) itr.next();

5. System.out.println("**********");

6. System.out.println("Set values is "+object);

7. }

or

8. Iterator hashIterator = hashMapName.keySet().iterator();

9. while(hashIterator.hasNext()) {

10. Type variable = hashIterator.next();

11. Type2 variable2 = hashMapName.get(variable);

12. ...

13. }

Or

1. for (Object key: hMap.keySet()) {

2. System.out.println(hMap.get(key));

3. }

When providing a user defined key class for storing objects in the HashMaps or Hashtables, what methods do you

have to provide or override

HashTable, HashMap and HashSet are the Collection classes in java.util package that make use of hashing algorithm to store objects. In all these Collection classes except HashSet, objects are stored as key-value pairs. For the storage and the retrieval of any user-defined objects it is a good practice to override the following methods which is mentioned below,

hashCode() equals()

These methods are available in the Object class and hence available to all java classes.Using these two methods, an object can be stored or retrieved from a Hashtable, HashMap or HashSet.

hashCode() method This method returns a hashcode value as an int for the object. Default implementation for hashcode() should be overridden in order to make searching of data faster. The implementation of hashCode() method for an user-defined object should be calculated based on the properties of the class which we wish to consider.

equals() method This method returns a boolean which specifies whether two objects are equal or not. The default implementation of equals() method given by the Object Class uses the '==' operator to compare two object references, and returns true only if they refer to the same object. But, we can meaningfully re-define this equals() method to have en equality check based on our own criterias.

Consider the following code, which defines two user defined classes Employee and EmployeeId which are supposed to be stored in a Map.

Employee.java

public class Employee {

private String name;

public Employee(String name){

this.name = name;

}

public String toString(){

return name;

}

}

EmployeeId.java

public class EmployeeId {

private String id;

public EmployeeId(String id){

this.id = id;

}

public String toString(){

return id;

}

}

The following class makes use of the above classes by storing it in a Map for later retrieval. We are adding Employee objects into the Map keyed with Employee Id.

HashCodeTest.java

public class HashCodeTest {

public static void main(String[] args) {

Map employees = new HashMap();

employees.put(new EmployeeId("111"), new Employee("Johny"));

employees.put(new EmployeeId("222"), new Employee("Jeny")); // Line A

employees.put(new EmployeeId("333"), new Employee("Jessie"));

Employee emp = employees.get(new EmployeeId("222")); // Line B

System.out.println(emp); // Line C

}

}

In Line B, we try to retrieve the Employee object who has Employee Id with a value of 222. We expect the output to be 'Jeny', because the Employee with Employee Id (222) was already there in the Collection, but surprisingly, the output of the above code is null. The reason is that we did not override the equals() method for EmployeeId andEmployee classes because the default implementation of equals() in the Object class considers the new EmployeeId("222") in the put statement and new EmployeeId("222") in the get statement as two different instances, and hence the call to get() in Line B returns null.

Let us look at how the same code works when we provide our desired implementation for hashcode() and equals() methods. We basically override hashcode() here just to make the object to be searched fast.

Employee.java

public class Employee {

private String name;

public Employee(String name){

this.name = name;

}

public String toString(){

return name;

}

@Override

public boolean equals(Object obj){

if(obj == null) {

return false;

}

if(obj.getClass() != getClass()){

return false;

}

Employee emp = (Employee)obj;

if(this.name == emp.name){

return true;

}

return false;

}

@Override

public int hashCode(){

return name.hashCode();

}

}

EmployeeId.java

public class EmployeeId {

private String id;

public EmployeeId(String id){

this.id = id;

}

public String toString(){

return id;

}

public boolean equals(Object obj){

if(obj == null)

return false;

if(obj.getClass() != getClass()){

return false;

}

EmployeeId empId = (EmployeeId)obj;

if(this.id == empId.id){

return true;

}

return false;

}

@Override

public int hashCode(){

return id.hashCode();

}

}

Now, we get the desired output 'Jeny', because as per our implementation for the equals() method, the new EmployeeId("222") in the put statement and new EmployeeId("222") in the get statement are considered one and the same.

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

• If a class overrides equals(), it must override hashCode().

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

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

• If it is accessed often, hashCode() is a candidate for caching to enhance performance.

What is the difference between Sorting performance of Arrays.sort() vs Collections.sort() ? Which one is faster? Which one to use and when?

Many developers are concerned about the performance difference between java.util.Array.sort() java.util.Collections.sort() methods. Both methods have same algorithm the only difference is type of input to them. Collections.sort() has a input as List so it does a translation of List to array and vice versa which is an additional step while sorting. So this should be used when you are trying to sort a list. Arrays.sort is for arrays so the sorting is done directly on the array

What is java.util.concurrent BlockingQueue? How it can be used?

Java has implementation of BlockingQueue available since Java 1.5. Blocking Queue interface extends collection interface, which provides you power of collections inside a queue. Blocking Queue is a type of Queue that additionally supports 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.

A typical usage example would be based on a producer-consumer scenario. Note that a BlockingQueue can safely be used with multiple producers and multiple consumers. An ArrayBlockingQueue is a implementation of blocking queue with an array used to store the queued objects.

The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time.

New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue. ArrayBlockingQueue requires you to specify the capacity of queue at the object construction time itself. Once created, the capacity cannot be increased. This is a classic "bounded buffer" (fixed size buffer), in which a fixed-sized array holds elements inserted by producers and extracted by consumers. Attempts to put an element to a full queue will result in the put operation blocking; attempts to retrieve an element from an empty queue will be blocked.

Set & List interface extend Collection, so Why doesn't Map interface extend Collection?

This was by design.

mappings are not collections and collections are not mappings. Thus, it makes little sense for Map to extend the Collection interface.

If a Map is a Collection, what are the elements?

"Key-value pairs", - provides a very limited Map abstraction.

Maps can be viewed as Collections (of keys, values, or pairs), and this fact is reflected in the three "Collection view operations" on Maps (keySet, entrySet, and values).

Which implementation of the List interface provides for the fastest insertion of a new element into the middle of the list?

a. Vector b. ArrayList c. LinkedList

ArrayList and Vector both use an array to store the elements of the list. When an element is inserted into the middle of the list the elements that follow the insertion point must be shifted to make room for the new element.

LinkedList is implemented using a doubly linked list; an insertion requires only the updating of the links at the point of insertion. Therefore, the LinkedList allows for fast insertions and deletions.

Collections – sorting and searching

Sorting

In order to sort a Collection, one should use java.util.Collections class as follows (assuming ArrayList will be used):

1. List≫ words = new ArrayList();

2. ... //populate list of words

3. Collections.sort(words);

It’s similar with arrays of objects

java.lang.Comparable

· used to sort:

o a List – java.util.Collections.sort(A_COLLECTION)

o an array of objects – java.util.Arrays.sort(AN_ARRAY)

· MyClass needs to implement public int compareTo(MyClass o) method, which returns:

o negative value – this object < another object

o 0 – this object == another object

o positive value – this object > another object

· the drawback: there’s only one way of sorting

1. class Book implements Comparable {

2. private String title;

3.

4. public String getTitle() {

5. return title;

6. }

7.

8. public void setTitle(String title_p) {

9. title = title_p;

10. }

11.

12. public int compareTo(Book o) {

13. return this.title.compareTo(o.getTitle());

14. }

15. }

Java.util.Comparator

· used to sort:

o a List – java.util.Collections.sort(A_COLLECTION, Comparator)

o an array of objects – java.util.Arrays.sort(AN_ARRAY, Comparator)

· a special class that implements java.util.Comparator interface needs to be created; this class defines public int compare(MyClass o1, MyClass o2)method (only one), which returns:

o negative value – this object < another object

o 0 – this object == another object

o positive value – this object > another object

· allows many one ways of sorting

· allows to sort even those class that can’t be modified

• class NameSort implements Comparator {
• public int compare(Book book1, Book book2) {
• return book1.getTitle().compareTo(book2.getTitle());
• }
• }

Searching

In order to search in a Collection or an array of objects, they must be sorted:

1. Arrays.sort(anArray);

2. Arrays.binarySearch(anArray, "string_to_search");

1. Arrays.sort(anArray, aComparator);

2. Arrays.binarySearch(anArray, "string_to_search", aComparator);

· when search succeeds, the index of the serched element is returned

· when search fails, insertionPoint is returned: -(insertion point) - 1 (if the element should be placed as a firston, so at 0 index, the returned value is -1)

Choosing the right Collection

best general purpose or 'primary' implementations are likely ArrayList, LinkedHashMap, and LinkedHashSet. They are marked below as " * ".

Interface	HasDuplicates?	Implementations					Historical
Set	no	HashSet	...	LinkedHashSet*	...	TreeSet	...
List	yes	...	ArrayList*	...	LinkedList	...	Vector, Stack
Map	no duplicate keys	HashMap	...	LinkedHashMap*	...	TreeMap	Hashtable, Properties

Principal features of non-primary implementations :

• HashMap has slightly better performance than LinkedHashMap, but its iteration order is undefined
• HashSet has slightly better performance than LinkedHashSet, but its iteration order is undefined
• TreeSet is ordered and sorted, but slow
• TreeMap is ordered and sorted, but slow
• LinkedList has fast adding to the start of the list, and fast deletion from the interior via iteration

Iteration order for above implementations :

• HashSet - undefined
• HashMap - undefined
• LinkedHashSet - insertion order
• LinkedHashMap - insertion order of keys (by default), or 'access order'
• ArrayList - insertion order
• LinkedList - insertion order
• TreeSet - ascending order, according to Comparable / Comparator
• TreeMap - ascending order of keys, according to Comparable / Comparator

Difference between java.util.Iterator and java.util.ListIterator?

Iterator : Enables you to traverse through a collection in the forward direction only, for obtaining or removing elements ListIterator : extends Iterator, and allows bidirectional traversal of list and also allows the modification of elements.

Difference between List, Set and Map

A Set is a collection that has no duplicate elements.
A List is a collection that has an order assoicated with its elements.
A Map is a way of storing key/value pairs.

Difference between HashMap and HashSet

1) HashMap implements Map interface. It stores unique keys.
HashSet implements Set interface. It stores unique elements.

2) A HashMap provides fast access to a mapping from a unique key to a value.

3) HashMap Keys are unordered which makes it faster than the TreeMap where the keys are ordered.

4) A HashSet is fast access to unique values only HashSet values are unordered which makes it faster than the TreeSet where the values are ordered. HashSet doesnot have Keys.

HashSet::there is no name and value pair.
HashMap:There is name and value pair.

HashSet:It belongs to Set interface.
HashMap:It belongs to Map interface.

Difference between HashMap and HashTable?

HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.

HashMap does not guarantee that the order of the map will remain constant over time. HashMap is unsynchronized and Hashtable is synchronized.

Iterator in the HashMap is fail-fast while the enumerator for the Hashtable isn't.

What is fail-fast property?

At high level - Fail-fast is a property of a system or software with respect to its response to failures. A fail-fast system is designed to immediately report any failure or condition that is likely to lead to failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly-flawed process.

When a problem occurs, a fail-fast system fails immediately and visibly. Failing fast is a non-intuitive technique: "failing immediately and visibly" sounds like it would make your software more fragile, but it actually makes it more robust. Bugs are easier to find and fix, so fewer go into production.

In Java, Fail-fast term can be related to context of iterators. If an iterator has been created on a collection object and some other thread tries to modify the collection object "structurally", a concurrent modification exception will be thrown. It is possible for other threads though to invoke "set" method since it doesn't modify the collection "structurally". However, if prior to calling "set", the collection has been modified structurally, "IllegalArgumentException" will be thrown.

How can we make Hashmap synchronized?

HashMap can be synchronized by Map m = Collections.synchronizedMap(hashMap);

Difference between Vector and ArrayList?

Vector is synchronized whereas arraylist is not.

Difference between set and list

1.List allows duplicate values
2.List maintains the order in wich you inserted elements in to the list
3.set does'nt allow duplicates
4.Set does'nt maintain order

5. ArrayList with Collections.synchronizedList() is recommended over Vector.

6. ArrayList has no default size while vector has a default size of 10.

7. The Enumerations returned by Vector's elements method are not fail-fast. Whereas ArraayList 8. does not have any method returning Enumerations.

What is the default capacity and load factor in Java Collection?

Default Capacity of any Collection say HashSet is 16. It means when you create a HashSet using its default constructor then first HashSet will be created to hold 16 elements or you can say that memory space is allocated to hold 16 elements.

load factor
By default load factor is 0.75. It means when the 75% of the capacity will be filled and you add new element then capacity will be increased (most probably doubled).

For example 16 default capacity and 0.75 load factor till 12th element addition the capacity will remain 16 but when you add 13th element then first capacity will be increased to 32 and element will be added.

You are planning to do an indexed search in a list of objects. Which of the two Java collections should you use:
ArrayList or LinkedList?

A. ArrayList

1. What is the Difference between Enumeration and Iterator interface?

Enumeration and Iterator are the interface available in java.util package. The functionality of Enumeration interface is duplicated by the Iterator interface. New implementations should consider using Iterator in preference to Enumeration. Iterators differ from enumerations in following ways:

1. Enumeration contains 2 methods namely hasMoreElements() & nextElement() whereas Iterator contains three methods namely hasNext(), next(),remove().
2. Iterator adds an optional remove operation, and has shorter method names. Using remove() we can delete the objects but Enumeration interface does not support this feature.
3. Enumeration interface is used by legacy classes. Vector.elements() & Hashtable.elements() method returns Enumeration. Iterator is returned by all Java Collections Framework classes. java.util.Collection.iterator() method returns an instance of Iterator.

Traversing Collections

two ways to traverse collections:

(1) for-each construct and

(2) Iterators.

for-each Construct

for (Object o : collection)

System.out.println(o);

Iterator

1)Iterator.remove is the only safe way to modify a collection during

iteration;

2) remove method may be called only once per call to next and throws a

exception if this rule is violated.

Collection Interface Bulk Operations

· containsAll — returns true if the target Collection contains all of the elements in the specified Collection.

· addAll — adds all of the elements in the specified Collection to the target Collection.

· removeAll — removes from the target Collection all of its elements that are also contained in the specified Collection.

· retainAll — removes from the target Collection all its elements that are not also contained in the specified Collection. That is, it retains only those elements in the target Collection that are also contained in the specified Collection.

· clear — removes all elements from the Collection.