Things must know about java collection API - Part II

Continue part II....

9. Collection Name	Class LinkedList<E>
Implementation Of	extends AbstractSequentialList<E>  implements List<E>, Deque<E>, Cloneable, java.io.Serializable
Is Ordered	Yes
Is Resizable	Yes
Is Thread Safe	No. must be synchronized externally
Duplicate allowed	Yes
Null allowed	Yes
Iterate Logic	Iterator<Whatever> iter = list.iterator();
Complexity	get(int index) is O(n) add(E element) is O(1) add(int index, E element) is O(n) remove(int index) is O(n) Iterator.remove() is O(1) <--- main benefit of LinkedList<E> ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>
More info	ü  Linked list implementation of the List interface. ü  Allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. ü  The class implements the Deque interface, providing first-in-first-out queue operations for add, poll, along with other stack and deque operations. ü  Why it implements the Deque interface? In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue. ü  Below are few Deque methods ·         addFirst(E e); ·         addLast(E e); ·         offerFirst(E e); ·         offerLast(E e); ·         removeFirst(); ·         removeLast(); ·         pollFirst(); ü  you can reversed it using Collections.reverse(yourLinkedList); ü  fail-fast: if the list is structurally modified 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. ü  It uses lots of small memory objects, and therefore impacts performance across the process. Lots of small object are bad for cache-locality.

import java.util.*; public class LinkedListDemo {    public static void main(String args[]) {       // create a linked list       LinkedList ll = new LinkedList();       // add elements to the linked list       ll.add("F");       ll.add("B");       ll.add("D");       ll.add("E");       ll.add("C");       ll.addLast("Z");       ll.addFirst("A");       ll.add(1, "A2");       System.out.println("Original contents of ll: " + ll);       // remove elements from the linked list       ll.remove("F");       ll.remove(2);       System.out.println("Contents of ll after deletion: "        + ll);             // remove first and last elements       ll.removeFirst();       ll.removeLast();       System.out.println("ll after deleting first and last: "        + ll);       // get and set a value       Object val = ll.get(2);       ll.set(2, (String) val + " Changed");       System.out.println("ll after change: " + ll);    } } O/P Original contents of ll: [A, A2, F, B, D, E, C, Z] Contents of ll after deletion: [A, A2, D, E, C, Z] ll after deleting first and last: [A2, D, E, C] ll after change: [A2, D, E Changed, C]

10. Collection Name	class Vector<E>
Implementation Of	AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
Is Ordered	YES
Is Resizable	YES
Is Thread Safe	YES
Duplicate allowed	YES
Null allowed	YES
Iterate Logic	Implements  Iterable<E>
Complexity	NA
More info	ü  Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. The capacity is always at least as large as the vector size; It is usually larger because as components are added to the vector, the vector's storage increases in chunks the size of capacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation. ü  it is recommended to use ArrayList in place of Vector. ü  Below are few Synchronized method. ·         copyInto() ·         trimToSize() ·         ensureCapacity() ·         setSize() ·         subList() ·         removeRange() ·         listIterator() ü  A Vector defaults to doubling the size of its array, while the ArrayList increases its array size by 50 percent. ü  it's always best to set the object's initial capacity to the largest capacity that your program will need. By carefully setting the capacity, you can avoid paying the penalty needed to resize the internal array later. If you don't know how much data you'll have, but you do know the rate at which it grows, ü  All of the get() set() methods are synchronized, so you can't have fine grained control over synchronization. ü  Generally you want to synchronize a whole sequence of operations. Synchronizing individual operations is both less safe (if you iterate over a Vector, for instance, you still need to take out a lock to avoid anyone else changing the collection at the same time, which would cause a ConcurrentModificationException in the iterating thread) but also slower (why take out a lock repeatedly when once will be enough)?

11. Collection Name	Interface Map<E>
Implementation Of	NA
Is Ordered	The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.
Is Resizable	YES
Is Thread Safe	No. Depends on subtypes
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Depends on Subtypes. Some implementations prohibit null keys and values, and some have restrictions on the types of their keys. Attempting to insert an ineligible key or value throws an unchecked exception, typically NullPointerException or ClassCastException.
Iterate Logic	Set<Map.Entry<K, V>> entrySet();
Complexity
More info	ü  An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. ü  Great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. ü  All general-purpose map implementation classes should provide two "standard" constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument. In effect, the latter constructor allows the user to copy any map, producing an equivalent map of the desired class. There is no way to enforce this recommendation (as interfaces cannot contain constructors) but all of the general-purpose map implementations in the JDK comply. ü  Below are the Map implementation ·         java.util.HashMap ·         java.util.Hashtable ·         java.util.EnumMap ·         java.util.IdentityHashMap ·         java.util.LinkedHashMap ·         java.util.Properties ·         java.util.TreeMap ·         java.util.WeakHashMap ü  By default you can put any Object into a Map, but from Java 5, Java Generics makes it possible to limit the types of object you can use for both keys and values in a Map Method like get(Object key) is not (fully) generic  because the key of the entry you are retrieving does not have to be the same type as the object that you pass in to get()

12. Collection Name	abstract class AbstractMap<E>
Implementation Of	implements Map<K,V>
Is Ordered	No. Depends on subtypes [HashMap No] [LinkedHashMap /TreeMap yes]
Is Resizable	Yes
Is Thread Safe	No . Depends on subtypes like ConcurrentHashMap
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Depends on Subtypes
Iterate Logic	Iterator<Entry<K,V>> i = entrySet().iterator();
Complexity
More info	ü  This class provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface. ü  To implement an unmodifiable map, the programmer needs only to extend this class and provide an implementation for the entrySet method, which returns a set-view of the map's mappings ü  To implement a modifiable map, the programmer must additionally override this class's put method (which otherwise throws an UnsupportedOperationException), and the iterator returned by entrySet().iterator() must additionally implement its remove method. ü  Implements methods like ·         containsKey(Object key) ·         containsValue(Object Value) ·         size() ·         values() ü  subclass must need to provide the method like entrySet();

13 Collection Name	class HashMap<E>
Implementation Of	implements Map<K,V>
Is Ordered	No.
Is Resizable	Yes
Is Thread Safe	No but can use Collections.synchronizedMap()
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Permits null values and the null key.
Iterate Logic	Iterator it = hashMap.entrySet().iterator();
Complexity	Provides constant-time performance for the basic operations (get and put)O(1)
More info	ü  Hash table based implementation of the Map interface. ü  Hashing means using some function or algorithm to map object data to some representative integer value. This so-called hash code (or simply hash) can then be used as a way to narrow down our search when looking for the item in the map. ü  An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor( the default load factor (.75) )is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets. ü  How it works 1) Calculate the hash of the object you're looking for. 2) Find that bucket 3) Search through that bucket for the item. So (1) is independent of the size of the hash map or number of items in it. (2) is O(1), assuming a standard hashmap implemented as an array of linked lists. (3) takes an amount of time related to the number of items in the bucket, which should be approximately (number of items added to hash) / (number of buckets). This part will start at O(1), but will very slowly increase as the number of items begins to greatly exceed the number of buckets.

package com.study.collection; import java.util.HashMap; import java.util.Map; public class HashMapDemo {        // static Initialization of Map        private static HashMap staticInitMap = new HashMap();        static {               staticInitMap.put("1", "Static Value 1");               staticInitMap.put("2", "Static Value 1");        }        // //instance initialization of Map        private static HashMap<String, String> instanceInitMap        = new HashMap<String, String>() {               {                      put("1", "Instance  Value 1");                      put("2", "Instance Value 2");               }        };        public static void main(String[] args) {               // iterate map        for (Map.Entry<String, String> entry : instanceInitMap.entrySet()) {               String key = entry.getKey();               String value = entry.getValue();               System.out.println("Key = " + entry.getKey() + " and  value = "                                   + entry.getValue());               }        } }

14  Collection Name	class EnumMap<E>
Implementation Of	extends Enum<K, V> extends AbstractMap<K, V> implements java.io.Serializable, Cloneable
Is Ordered	Enum maps are maintained in the natural order of their keys (the order in which the enum constants are declared).
Is Resizable	YES
Is Thread Safe	No
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Null keys are not permitted. Null values are permitted.
Iterate Logic	Use Key  Set Iterator.  Iterator iterKeySet = map.keySet().iterator();
Complexity
More info	ü  A specialized Map implementation for use with enum type keys. ü  All of the keys in an enum map must come from a single enum type that is specified, explicitly or implicitly, when the map is created. ü  Enum maps are represented internally as arrays. This representation is extremely compact and efficient. ü  If multiple threads access an enum map concurrently, and at least one of the threads modifies the map, it should be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the enum map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap(java.util.Map) method. ü  They are likely (though not guaranteed) to be faster than their HashMap counterparts. ü  Since enum can represent a type (like class or interface)  in Java and it can also override equals() and hashCode() , It can be used inside HashMap or any other collection but using  EnumMap brings implementation specific benefits which is done for enum keys, In short EnumMap is optimized Map implementation exclusively for enum keys . As per javadoc Enum is implemented using Arrays and common operations result in constant time. So if you are thinking of an high performance Map, EnumMap could be decent choice for enumeration data. ü  Also useful while using EnumMap in code to avoid any compile time or logical errors

package com.study.collection; import java.util.EnumMap; import java.util.Iterator; public class EnumMapDemo {       public enum CITY {             MUMBAI, PUNE, NAGPUR;       }       public static void main(String[] args) {             EnumMap<CITY, String> cityMap = new EnumMap<CITY, String>(CITY.class);             cityMap.put(CITY.MUMBAI, "850 KM");             cityMap.put(CITY.NAGPUR, "00 KM");             cityMap.put(CITY.PUNE, "950 KM");             // cityMap.put(Null, "00 KM"); not allow             // check size             System.out.println("Size = " + cityMap.size());             // check order             System.out.println("City Map = " + cityMap);             Iterator<CITY> iterKeySet = cityMap.keySet().iterator();             while (iterKeySet.hasNext()) {                   CITY city = iterKeySet.next();                   System.out.println("Key = " + city);             }       } } o/p Size = 3 City Map = {MUMBAI=850 KM, PUNE=950 KM, NAGPUR=00 KM} Key = MUMBAI Key = PUNE Key = NAGPUR

15 Collection Name	interface  SortedMap<E>
Implementation Of	extends Map<K,V>
Is Ordered	The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.
Is Resizable	Yes
Is Thread Safe	No
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Null keys are not permitted. Null values are permitted.
Iterate Logic	Set<Map.Entry<K, V > entrySet();
Complexity
More info	ü  The Iterator returned by the iterator operation on any of the sorted map's Collection views traverse the collections in order. ü  The arrays returned by the Collection views' toArray operations contain the keys, values, or entries in order. ü  All keys inserted into a sorted map must implement the Comparable interface (or be accepted by the specified comparator). Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) (or comparator.compare(k1, k2)) must not throw a ClassCastException for any keys k1 and k2 in the sorted map. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a ClassCastException. ü  Provide method for implementation like ·         Comparator<? super K> comparator(); ·         firstKey(); ·         lastKey();

16 Collection Name	interface  NavigableMap<K,V>
Implementation Of	extends SortedMap<K,V>
Is Ordered	Yes
Is Resizable	Yes
Is Thread Safe	No
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Null keys are not permitted. Null values are permitted.
Iterate Logic	entry set iterator
Complexity
More info	ü  A NavigableMap may be accessed and traversed in either ascending or descending key order. ü  It has a few extensions to the SortedSet which makes it possible to navigate the map. ü  The first interesting navigation methods are the descendingKeySet() and descendingMap() methods. ü  The descendingKeySet() method returns a NavigableSet in which the order of the elements is reversed compared to the original key set. The returned "view" is backed by the original NavigableSet ket set, so changes to the descending set are also reflected in the original set. However, you should not remove elements directly from the key set. Use the Map.remove() method instead. ü  The headMap() method returns a view of the original NavigableMap which only contains elements that are "less than" the given element. Here is an example: ü  The tailMap() method works the same way, except it returns all elements that are higher than the given parameter element. ü  The subMap() allows you to pass two parameters demarcating the boundaries of the view map to return. ü  The ceilingKey() method returns the least (smallest) key in this map that is greater than or equal to the element passed as parameter to the ceilingKey() method. ü  The higherKey() method returns the least (smallest) element in this map that is greater than (not equal too) the element passed as parameter to the higherKey() method. ü  The NavigableMap also has methods to get the entry for a given key, rather than the key itself. These methods behave like the ceilingKey() etc. methods, except they return an Map.Entry instead of the key object itself. ü  The pollFirstEntry() method returns and removes the "first" entry (key + value) in the NavigableMap or null if the map is empty. ü  The pollLastEntry() returns and removes the "last" element in the map or null if the map is empty. "First" means smallest element according to the sort order of the keys. "Last" means largest key according to the element sorting order of the map.

Continue reading.....Things must know about java collection API - Part III (coming soon)