Java Tutorial: Collection - Part 1 (Introduction)

Good use of the Collections framework can potentially reduce your workload in the projects. I have found many of my mates at IIT not aware of the power of this framework. Therefore, I have decided to help them a bit learning the Collections.
Throughout the tutorial, I will assume that you know when to use which data structure. I will not discuss it in detail.

Note that, Collections classes are generic. If you are not familiar with generic, these tutorials may not help you much.

This part of the tutorial will give you an overview on the interfaces covered by Collections Framework. In the later parts, we will discuss them separately.

General interfaces

Collection
This interface is the parent of all collection types. It declares the basic methods that all collection class should have. Like add(), remove(), isEmpty(), size() etc.
AbstractCollection
The default implementation of the interface Collection. Implements all the methods except iterator() and size(). Important thing is that, the access of the constractor is protected, so you cannot instanciate an AbstractCollection, you can only inherite one.

Specialized interfaces

These interfaces and the implementations will be discussed in separate topics. Here I am mentioning only the names
List
Set
NavigableSet
SortedSet
BlockingQueue
BlockingDeque
Deque

Maps

This is another interface which is not under the hierarchy of Collection, however is included in the framework. Map is the root interface of the Map hierarchy. We will discuss Map in a separate topic.

Collections

Collections is a class that has several static methods that manipulates the Collection objects. This is equivalent to the class Arrays that manipulates Array types. This class is easy to use and the methods are too self explanatory. So I am not discussing it in detail.

The part two of this tutorial will be continued with Lists. I will provide the link here when I complete writing that.

nice post. go ahead. I know some optimized technique. If you want, I can post them here.

BIT0112-Rokon wrote:nice post. go ahead. I know some optimized technique. If you want, I can post them here.

Of course I want.

Java Collection & Map: When what to use to get better performance


Optimization techniques in Lists

List types represent an ordered collection of objects. ArrayList, Vector, Stack and LinkedList are the List implementation classes. All List types support basic operations – adding objects, removing objects, accessing objects and iterating through the list.Performance is different for each class based on specific operations.

If you want your collection to be thread safe then Vector or Stack must be used because both have synchronized methods. While ArrayList and LinkedList are not thread safe. If you don’t want your collection to be thread safe then you can choose between ArrayList or LinkedList. General concept from performance point of view is that ArrayList gives better performance when accessing and iterating objects whereas LinkedList gives better performance when adding and removing objects.

The initial size for ArrayList and Vector is 10. ArrayList increases its capacity by half approximately whenever its capacity reaches maximum (10) but Vector increases its capacity by double whenever its capacity reaches maximum. That is the reason why ArrayList takes more time than Vector if it is not initialized with proper size though ArrayList is not synchronized. ArrayList with initialization gives better performance than others because its methods are non-synchronized. You can convert an ArrayList as thread safe collection using Collections.synchronizedList(ArrayList object) but it is more expensive than using a Vector.

LinkedList gives good performance when adding elements at the end and beginning but it is worse when adding objects at middle because it needs to scan the node whenever it needs to add an object. LinkedList cannot be initialized.

Iterating collection using all three types of classes ,ArrayList ,Vector and LinkedList gives similar performance

Optimization techniques in Sets

There are two implementations of the Set interface they are HashSet and TreeSet. HashSet gives better performance than TreeSet because , TreeSet is an ordered collection of objects and the objects are sorted while they are inserted in the TreeSet where as in case of HashSet objects are added in an adhoc manner. It is expensive to do all basic operations in TreeSet because it has to compare and sort every object. We can get better performance by using a HashSet and converting it to a TreeSet later on.

Optimization techniques in Maps

HashMap, Hashtable and WeakHashMap have similar implementations. TreeMap is meant for sorted collection. HashMap and WeakHashMap are not synchronized whereas Hashtable is synchronized. If you want your Map type collection to be thread safe, then you need to use Hashtable otherwise use HashMap. HashMap gives better performance than Hashtable because of it’s non-synchronized methods.

WeakHashMap is a special purpose map which uses an internal hashtable. When there are no more references to key object except weak reference maintained by WeakHashMap, the garbage collector reclaims the key object and mapping between key object and value object is also reclaimed, if the value object does not have any other references then the value object is also reclaimed by the garbage collector.

Key Points:

Lists:
1. Use ArrayList with proper initialization if you don’t want thread safe for the collection whenever you add/remove/access objects at end and middle of collection.
2. Use Vector with proper initialization if you want thread safe for the collection whenever you add/remove/access objects at end and middle of collection.
3. Use LinkedList if you don’t want thread safe for the collection whenever you add/remove/access objects at beginning of collection.
4. Use synchronized LinkedList if you want thread safe for the collection whenever you add/remove/access objects at beginning of collection.
5. Use ListIterator than Iterator and Enumeration for List types

Sets:
1. Use HashSet for maintaining unique objects if you don’t want thread safe for the collection for all basic(add/remove/access) operations otherwise use synchronized HashSet for thread safe.
2. Use TreeSet for ordered and sorted set of unique objects for non-thread safe collection otherwise use synchronized TreeSet for thread safe

Maps:
1. Use HashMap for non-thread safe map collection otherwise use Hashtable for thread safe collection.
2. Use TreeMap zed technique. If you want, I can post them here.for non-thread safe ordered map collection otherwise use synchronized TreeMap for thread safe.

To get details about performance of collection framework go to http://www.precisejava.com/javaperf/j2se/Collections.htm

Aaaaah... That one is big an cool. I think we should make a separate topic for this. May be Collection - Part 0

Hmm.. I agree with that. In that case, you can simply split this topic to two parts

Although i didn't read the details yet, I think rokon's part should be named to part 2, Mohaimin's part is the introduction, right?

'm not agreed. No need to do anything. Its going on nice. Its a reply nothing else. If, it would something like a tutorial, I would make it earlier.