Collections in Java and Data Strcutures - Seris I

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

HashMap vs Hashtable in Java
Difference between HashMap and Hashtable in Java question oftenly asked in core Java interviews to check whether candidate understand correct usage of collection classes and aware of alternative solutions available. Along with How HashMap internally works in Java and ArrayList vs Vector, this  is one of the oldest question from Collection framework in Java. Hashtable is a legacy Collection class and it's there in Java API from long time but it got refactored to implement Map interface in Java 4 and from there Hashtable became part of Java Collection framework. Hashtable vs HashMap in Java is so popular a question that it can top any list of Java Collection interview Question. You just can't afford not to prepare HashMap vs Hashtable before going to any Java programming interview. In this Java article we will not only see some important differences between HashMap and Hashtable but also some similarities between these two collection classes. Let's first see How different they are :

Difference between HashMap and Hashtable in Java

Both HashMap and Hashtable implements Map interface but there are some significant difference between them which is important to remember before deciding whether to use HashMap or Hashtable in Java. Some of them is thread-safety, synchronization and speed. here are those differences :

1.The HashMap class is roughly equivalent to Hashtable, except that it is non synchronized and permits nulls. (HashMap allows null values as key and value whereas Hashtable doesn't allow nulls).

2. One of the major differences between HashMap and Hashtable is that HashMap is non synchronized whereas Hashtable is synchronized, which means Hashtable is thread-safe and can be shared between multiple threads but HashMap can not be shared between multiple threads without proper synchronization. Java 5 introduces ConcurrentHashMap which is an alternative of Hashtable and provides better scalability than Hashtable in Java.

3. Another significant difference between HashMap vs Hashtable is that Iterator in the HashMap is  a fail-fast iterator  while the enumerator for the Hashtable is not and throw ConcurrentModificationException if any other Thread modifies the map structurally  by adding or removing any element except Iterator's own remove() method. But this is not a guaranteed behavior and will be done by JVM on best effort. This is also an important difference between Enumeration and Iterator in Java.

4. One more notable difference between Hashtable and HashMap is that because of thread-safety and synchronization Hashtable is much slower than HashMap if used in Single threaded environment. So if you don't need synchronization and HashMap is only used by one thread, it out perform Hashtable in Java.

5. HashMap does not guarantee that the order of the map will remain constant over time.

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 or ListIterator 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.

3)Structurally modification means deleting or inserting element which could effectively change the structure of map.

HashMap can be synchronized by

Map m = Collections.synchronizeMap(hashMap);

In Summary there are significant differences between Hashtable and HashMap in Java e.g. thread-safety and speed and based upon that only use Hashtable if you absolutely need thread-safety, if you are running Java 5 consider using ConcurrentHashMap in Java.

Read more: http://javarevisited.blogspot.com/2010/10/difference-between-hashmap-and.html#ixzz3DURsEqa6

What is the difference between Synchronized Collection classes and Concurrent Collection Classes ? When to use what ?

Collections classes are heart of java API though I feel using them judiuously is an art.its my personal experience where I have improved performance by using ArrayList where legacy codes are unnecesarily used Vector etc. JDK 1.5 introduce some good concurrent collections which is highly efficient for high volume , low latency system.


The synchronized collections classes, Hashtable and Vector, and the synchronized wrapper classes, Collections.synchronizedMap and Collections.synchronizedList, provide a basic conditionally thread-safe implementation of Map and List.
However, several factors make them unsuitable for use in highly concurrent applications -- their single collection-wide lock is an impediment to scalability and it often becomes necessary to lock a collection for a considerable time during iteration to prevent ConcurrentModificationException.

The ConcurrentHashMap and CopyOnWriteArrayList implementations provide much higher concurrency while preserving thread safety, with some minor compromises in their promises to callers. ConcurrentHashMap and CopyOnWriteArrayList are not necessarily useful everywhere you might use HashMap or ArrayList, but are designed to optimize specific common situations. Many concurrent applications will benefit from their use.

So what is the difference between hashtable and ConcurrentHashMap , both can be used in multithreaded environment but once the size of hashtable becomes considerable large performance degrade because for iteration it has to be locked for longer duration.

Since ConcurrentHashMap indroduced concept of segmentation , how large it becomes only certain part of it get locked to provide thread safety so many other readers can still access map without waiting for iteration to complete.

In Summary ConcurrentHashMap only locked certain portion of Map while Hashtable lock full map while doing iteration.

Read more: http://javarevisited.blogspot.com/2010/10/what-is-difference-between-synchronized.html#ixzz3DURnN9m9

Difference between ArrayList and Vector in Java

ArrayList and Vector are two of most used class on java collection package and difference between Vector and ArrayList is one of the most frequently asked java interview question on first round or phone interview. Though it’s quite a simple question in my opinion but knowledge of when to use Vector over ArrayList or does matter if you are working on a project. In this article we will some point based difference between Vector and ArrayList in Java and trying to understand the concept behind those differences. Ultimate goal is to familiarize yourself with distinguish property of ArrayList and Vector. By the way Java 5 adds another implementation of List interface which is similar to Vector and ArrayList but provides better concurrency access than Vector, its called CopyOnWriteArrayList. By the way this is the third article on discussing about Collection interview question,  Difference between LinkedList and ArrayList  and   List vs Set are other popular interview questions based upon collection framework in Java.

Before seeing differences between Vector and ArrayList, let's see some similarities between these two and why we can use ArrayList in place of Vector on certain scenario.

1) Vector and ArrayList are index based and backed up by an array internally.

2) Both ArrayList and Vector maintains the insertion order of element. Means you can assume that you will get the object in the order you have inserted if you iterate over ArrayList or Vector.

3) Both Iterator and ListIterator returned by ArrayList and Vector are fail-fast.

4) ArrayList and Vector also allows null and duplicates.

Vector vs ArrayList in Java

Now let's see some key difference between Vector and ArrayList in Java, this will decide when is the right time to use Vector over ArrayList and vice-versa. Differences are based upon properties like synchronization, thread safety, speed, performance , navigation and Iteration over List etc.

1) Synchronization and thread-safety

First and foremost difference between Vector and ArrayList is that Vector is synchronized and ArrayList is not, what it means is that all the method which structurally modifies Vector e.g. add () or remove () are synchronized which makes it thread-safe and allows it to be used safely in a multi-threaded and concurrent environment. On the other hand ArrayList methods are not synchronized thus not suitable for use in multi-threaded environment. This is also a popular interview question on thread, where people ask why ArrayList can not be shared between multiple threads.

2) Speed and Performance

ArrayList is way faster than Vector. Since Vector is synchronized and thread-safe it pays price of synchronization which makes it little slow. On the other hand ArrayList is not synchronized and fast which makes it obvious choice in a single-threaded access environment. You can also use ArrayList in a multi-threaded environment if multiple threads are only reading values from ArrayList or you can create read only ArrayList as well.

3) Capacity

Whenever Vector crossed the threshold specified it increases itself by value specified in capacityIncrement field while you can increase size of ArrayList by calling ensureCapacity () method.

4) Enumeration and Iterator

Vector can return enumeration of items it hold by calling elements () method which is not fail-fast as opposed to Iterator and ListIterator returned by ArrayList. I have discussed this point in detail on my post What is difference between Iterator and Enumeration, you can also look there.

5) Legacy

Another point worth to remember is Vector is one of those classes which comes with JDK 1.0 and initially not part of Collection framework but in later version it's been re-factored to  implement List interface so that it could become part of collection framework

After considering these points about both Vector and ArrayList , my conclusion is use ArrayList wherever possible and avoids use of Vector until you have no choice. Think for CopyOnWriteArrayList  over Vector, if you have multiple readers and few writers because it can provide thread-safety without impacting performance too much.

Read more: http://javarevisited.blogspot.com/2011/09/difference-vector-vs-arraylist-in-java.html#ixzz3DURQTMmG

Top 25 Java Collection Framework Interview Questions Answers for Freshers and Experienced Programmers

Interview questions from Collection package or framework is most common in any Core Java Interview yet a tricky one. Together Collection and multithreading makes any Java interview tough to crack and having a good understanding of Collection and threads will help you to excel in Java interview. I thought about writing interview questions on collection when I wrote 10 multi-threading Interview questions and Top 20 Core Java Interview questions answers but somehow it got delayed. In this article we will see mix of some beginners and advanced Java Collection interviews and there answers which has been asked in various Core Java interviews. These Collection interview questions have been collected from various friends and colleagues and Answers of these interview questions can also be found by Google.

     

Good Java Collection Interview Questions Answers

Now let's start with interview questions on collections. Since collection is made of various data structures e.g. Map, Set and List and there various implementation, mostly interviewer checks whether interviewee is familiar with basics of these collections or not and whether he knows when to use Map, Set or List. Based on Role for which interview is going on questions starts with beginner’s level or more advanced level. Normally 2 to 3 years experience counted as beginners while over 5 years comes under advanced category, we will see questions from both categories.

1. How HashMap works in Java?

This is Classical Java Collection interview questions which I have also discussed in How HashMap works in Java. This collection interview questions is mostly asked during AVP Role interviews on Investment-Banks and has lot of follow-up questions based on response of interviewee e.g. Why HashMap keys needs to be immutable, what is race conditions on HashMap and how HashMap resize in Java. For explanation and answers of these questions Please see earlier link.

2. What is difference between poll() and remove() method of Queue interface?
Though both poll() and remove() method from Queue is used to remove object and returns head of the queue, there is subtle difference between them. If Queue is empty() then a call to remove() method will throw Exception, while a call to poll() method returns null. By the way, exactly which element is removed from the queue depends upon queue's ordering policy and varies between different implementation, for example PriorityQueue keeps lowest element as per Comparator or Comparable at head position. 

3. What is difference between fail-fast and fail-safe Iterators?

This is relatively new collection interview questions and can become trick if you hear the term fail-fast and fail-safe first time. Fail-fast Iterators throws ConcurrentModificationException when one Thread is iterating over collection object and other thread structurally modify Collection either by adding, removing or modifying objects on underlying collection. They are called fail-fast because they try to immediately throw Exception when they encounter failure. On the other hand fail-safe Iterators works on copy of collection instead of original collection

4. How do you remove an entry from a Collection? and subsequently what is difference between remove() method of Collection and remove() method of Iterator, which one you will use, while removing elements during iteration?

Collection interface defines remove(Object obj) method to remove objects from Collection. List interface adds another method remove(int index), which is used to remove object at specific index. You can use any of these method to remove an entry from Collection, while not iterating. Things change, when you iterate. Suppose you are traversing a List and removing only certain elements based on logic, then you need to use Iterator's remove() method. This method removes current element from Iterator's perspective. If you use Collection's or List's remove() method during iteration then your code will throw ConcurrentModificationException. That's why it's advised to use Iterator remove() method to remove objects from Collection.

5. What is difference between Synchronized Collection and Concurrent Collection?

Java 5 has added several new Concurrent Collection classes e.g. ConcurrentHashMap, CopyOnWriteArrayList, BlockingQueue etc, which has made Interview questions on Java Collection even trickier. Java Also provided way to get Synchronized copy of collection e.g. ArrayList, HashMap by using Collections.synchronizedMap() Utility function.One Significant difference is that ConcurrentCollections has better performance than synchronized Collection because they lock only a portion of Map to achieve concurrency and Synchronization. See Difference between Synchronized Collection and Concurrent Collection in Java for more details.

6. What is difference between Iterator and Enumeration?

This is a beginner level collection interview questions and mostly asked during interviews of Junior Java developer up to experience of 2 to 3 years Iterator duplicate functionality of Enumeration with one addition of remove() method and both provide navigation functionally on objects of Collection.Another difference is that Iterator is more safe than Enumeration and doesn't allow another thread to modify collection object during iteration except remove() method and throws ConcurrentModificaitonException. See Iterator vs Enumeration in Java for more differences.

7. How does HashSet is implemented in Java, How does it uses Hashing ?
This is a tricky question in Java, because for hashing you need both key and value and there is no key for store it in a bucket, then how exactly HashSet store element internally. Well, HashSet is built on top of HashMap. If you look at source code of java.util.HashSet class, you will find that that it uses a HashMap with same values for all keys, as shown below :

private transient HashMap map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

When you call add() method of HashSet, it put entry in HashMap :

public boolean add(E e) {
  return map.put(e, PRESENT)==null;
}

Since keys are unique in a HashMap, it provides uniqueness guarantee of Set interface.


8. What do you need to do to use a custom object as key in Collection classes like Map or Set?
Answer is : If you are using any custom object in Map as key, you need to override equals() and hashCode() method, and make sure they follow there contract. On the other hand if you are storing a custom object in Sorted Collection e.g. SortedSet or SortedMap, you also need to make sure that your equals() method is consistent to compareTo() method, otherwise those collection will not follow there contacts e.g. Set may allow duplicates.

9. Difference between HashMap and Hashtable?

This is another Classical Java Collection interview asked on beginner’s level and most of Java developer has a predefined answer for this interview questions e.g. HashMap is not synchronized while Hashtable is not or hashmap is faster than hash table etc. What could go wrong is that if he placed another follow-up question like how hashMap works in Java or can you replace Hashtable with ConcurrentHashMap etc. See Hashtable vs HashMap in Java for detailed answer of this interview question.

10. When do you use ConcurrentHashMap in Java?

This is another advanced level collection interview questions in Java which normally asked to check whether interviewer is familiar with optimization done on ConcurrentHashMap or not. ConcurrentHashMap is better suited for situation where you have multiple readers and one

Writer or fewer writers since Map gets locked only during write operation. If you have equal number of reader and writer than ConcurrentHashMap will perform in line of Hashtable or synchronized HashMap.

11. What is difference between Set and List in Java?

Another classical Java Collection interview popular on telephonic round or first round of interview. Most of Java programmer knows that Set doesn't allowed duplicate while List does and List maintains insertion order while Set doesn't. What is key here is to show interviewer that you can decide which collection is more suited based on requirements.

12. How do you Sort objects on collection?

This Collection interview question serves two purpose it not only test an important programming concept Sorting but also utility class like Collections which provide several methods for creating synchronized collection and sorting. Sorting is implemented using Comparable and Comparator in Java and when you call Collections.sort() it gets sorted based on natural order specified in compareTo()method while Collections.sort(Comparator) will sort objects based on compare() method of Comparator. See Sorting in Java using Comparator and Comparable for more details.

13. What is difference between Vector and ArrayList?

One more beginner level collection interview questions, this is still very popular and mostly asked in telephonic round. ArrayList in Java is one of the most used Collection class and most interviewer asked questions on ArrayList. See Difference between Vector and ArrayList for answer of this interview question.

14. What is difference between HashMap and HashSet?

This collection interview questions is asked in conjunction with HashMap vs Hashtable. HashSet implements java.util.Set interface and that's why only contains unique elements, while HashMap allows duplicate values.  In fact, HashSet is actually implemented on top of java.util.HashMap. If you look internal implementation of java.util.HashSet, you will find that it adds element as key on internal map with same values. For a more detailed answer, see HashMap vs HashSet.



15) What is NavigableMap in Java ? What is benefit over Map?
NavigableMap Map was added in Java 1.6, it adds navigation capability to Map data structure. It provides methods like lowerKey() to get keys which is less than specified key, floorKey() to return keys which is less than or equal to specified key, ceilingKey() to get keys which is greater than or equal to specified key and higherKey() to return keys which is greater specified key from a Map. It also provide similar methods to get entries e.g. lowerEntry(), floorEntry(), ceilingEntry() and higherEntry(). Apart from navigation methods, it also provides utilities to create sub-Map e.g. creating a Map from entries of an exsiting Map like tailMap, headMap and subMap. headMap() method returns a NavigableMap whose keys are less than specified, tailMap() returns a NavigableMap whose keys are greater than the specified and subMap() gives a NavigableMap between a range, specified by toKey to fromKey.  



16) Which one you will prefer between Array and ArrayList for Storing object and why?Though ArrayList is also backed up by array, it offers some usability advantage over array in Java. Array is fixed length data structure, once created you can not change it's length. On the other hand, ArrayList is dynamic, it automatically allocate a new array and copies content of old array, when it resize. Another reason of using ArrayList over Array is support of Generics. Array doesn't support Generics, and if you store an Integer object on a String array, you will only going to know about it at runtime, when it throws ArrayStoreException. On the other hand, if you use ArrayList, compiler and IDE will catch those error on the spot. So if you know size in advance and you don't need re-sizing than use array, otherwise use ArrayList.

17) Can we replace Hashtable with ConcurrentHashMap?

Answer 3 : Yes we can replace Hashtable with ConcurrentHashMap and that's what suggested in Java documentation of ConcurrentHashMap. but you need to be careful with code which relies on locking behavior of Hashtable. Since Hashtable locks whole Map instead of portion of Map, compound operations like if(Hashtable.get(key) == null) put(key, value) works in Hashtable but not in concurrentHashMap. instead of this use putIfAbsent() method of ConcurrentHashMap

18) What is CopyOnWriteArrayList, how it is different than ArrayList and Vector?

Answer : CopyOnWriteArrayList is new List implementation introduced in Java 1.5 which provides better concurrent access than Synchronized List. better concurrency is achieved by Copying ArrayList over each write and replace with original instead of locking. Also CopyOnWriteArrayList doesn't throw any ConcurrentModification Exception. Its different than ArrayList because its thread-safe and ArrayList is not thread safe and its different than Vector in terms of Concurrency. CopyOnWriteArrayList provides better Concurrency by reducing contention among readers and writers.

19) Why ListIterator has add() method but Iterator doesn't or Why add() method is declared in ListIterator and not on Iterator.

Answer : ListIterator has add() method because of its ability to traverse or iterate in both direction of collection. it maintains two pointers in terms of previous and next call and in position to add new element without affecting current iteration.

20) When does ConcurrentModificationException occur on iteration?

When you remove object using Collection's or List's remove method e.g. remove(Object element) or remove(int index), instead of Iterator's remove() method than ConcurrentModificationException occur. As per Iterator's contract, if it detect any structural change in Collection e.g. adding or removing of element, once Iterator begins, it can throw ConcurrentModificationException. 

21) Difference between Set, List and Map Collection classes?

java.util.Set, java.util.List and java.util.Map defines three of most popular data structure support in Java. Set provides uniqueness guarantee i.e.g you can not store duplicate elements on it, but it's not ordered. On the other hand List is an ordered Collection and also allowes duplicates. Map is based on hashing and stores key and value in an Object called entry. It provides O(1) performance to get object, if you know keys, if there is no collision. Popular impelmentation of Set is HashSet, of List is ArrayList and LinkedList, and of Map are HashMap, Hashtable and ConcurrentHashMap. Another key difference between Set, List and Map are that Map doesn't implement Collection interface, while other two does. For a more detailed answer, see Set vs List vs Map in Java

22) What is BlockingQueue, how it is different than other collection classes?

BlockingQueue is a Queue implementation available in java.util.concurrent package. It's one of the concurrent Collection class added on Java 1.5, main difference between BlockingQueue and other collection classes is that apart from storage, it also provides flow control. It can be used in inter thread communication and also provides built-in thread-safety by using happens-before guarantee. You can use BlockingQueue to solve Producer Consumer problem, which is what is needed in most of concurrent applications.

Few more questions for practice, try to find answers of these question by yourself :

23) How does LinkedList is implemented in Java, is it a Singly or Doubly linked list?

hint : LinkedList in Java is a doubly linked list.

24) How do you iterator over Synchronized HashMap, do you need to lock iteration and why ?

25) What is Deque? when do you use it ?

Read more: http://javarevisited.blogspot.com/2011/11/collection-interview-questions-answers.html#ixzz3DURb2ggQ

Difference between LinkedList vs ArrayList in Java

LinkedList and ArrayList both implement List Interface but how they work internally is where the differences lies. Main difference between ArrayList and LinkedList is that ArrayList is implemented using re sizable array while LinkedList is implemented using doubly LinkedList. ArrayList is more popular among Java programmer than LinkedList as there are few scenarios on which LinkedList is a suitable collection than ArrayList. In this article we will see some differences between LinkedList and ArrayList and try to find out when and where to use LinkedList over ArrayList.

LinkedList vs ArrayList in Java

All the differences between LinkedList and ArrayList has there root on difference between Array and LinkedList data-structure. If you are familiar with Array and LinkedList data structure you will most likely derive following differences between them:

1) Since Array is an index based data-structure searching or getting element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements. On the Other hand LinkedList doesn't provide Random or index based access and you need to iterate over linked list to retrieve any element which is of order O(n).

2) Insertions  are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array

and copying content to new array if array gets full which makes adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList in Java. ArrayList also needs to update its index if you insert something anywhere except at the end of array.

3) Removal is like insertions better in LinkedList than ArrayList.

4) LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next  and previous node.

When to use LinkedList and ArrayList in Java

As I said LinkedList is not as popular as ArrayList but still there are situation where a LinkedList is better choice than ArrayList in Java. Use LinkedList in Java if:

1) Your application can live without Random access. Because if you need nth element in LinkedList you need to first traverse up to nth element O(n) and than you get data from that node.

2) Your application is more insertion and deletion driver and you insert or remove more than retrieval. Since insertion or

removal doesn't involve resizing its much faster than ArrayList.

That’s all on difference between ArrayList and LinkedList in Java. Use ArrayList in Java for all there situation where you need a non-synchronized index based access. ArrayList is fast and easy to use, just try to minimize array resizing by constructing arraylist with proper initial size.

Read more: http://javarevisited.blogspot.com/2012/02/difference-between-linkedlist-vs.html#ixzz3DURjWCvq