Things must know about java collection API - Part III

17. Collection Name	java.util.Collections.synchronizedMap
Implementation Of	implements Map<K,V>, Serializable
Is Ordered	Yes
Is Resizable	Yes
Is Thread Safe	Yes
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	ü  All method calls on the collection are synchronized. Only one thread will be allowed to read/modify the collection at a time. ü  So there is much less chances to make a mistake if you use synchronized collection instead of doing all synchronization stuff by yourself. ü  Map<String,String> synmap = Collections.synchronizedMap(map); ü  The synchronized collection protects itself from multiple threads corrupting the map itself. It does not protect against logic race conditions around multiple calls to the map like below. synchronized (synchronizedMap) {     // test for a key in the map     if (synchronizedMap.containsKey(key)) {       synchronizedMap.get(key).add(value);     } else {       List<String> valuesList = new ArrayList<String>();       valuesList.add(value);       // store a value into the map       synchronizedMap.put(key, valuesList);    } } if you don't synchronize block/method, assume there may be case like Thread1 executing first part and thread2 executing second part, your business operation may results in weird results (even though updates to map are synchronized) ü  Collections.synchronizedMap(map) creates a blocking Map which will degrade performance, albeit ensure consistency (if used properly). ü  Becomes a big problem when you need to iterate over the entire Map, which can take a long time for a large Map - while one thread does that, all others have to wait if they want to insert or lookup anything. ü  Map m = Collections.synchronizedMap(new HashMap()); Set returned by m.keySet() also a synchronized SynchronizedSet uses the same mutex which SynchronizedMap returned by Collections.synchronizedMap(new HashMap()); is using.                         Set s = m.keySet();           public Set<K> keySet() {               synchronized (mutex) {                     if (keySet==null)                        keySet = new SynchronizedSet<>(m.keySet(), mutex);                    return keySet;                 }             } ü  synchronizedMap is just a wrapper. It wraps all data access functions of underlying Map and makes them thread safe

18. Collection Name	java.util.Collections.TreeMap
Implementation Of	extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable
Is Ordered	Sorted
Is Resizable	Yes
Is Thread Safe	NO.  can use Collections.synchronizedSortedMap
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	Read/Search any element O(log n)  Update : O(log n) Delete : O(log n) Add : O(log n)
More info	ü  Red-Black tree based NavigableMap implementation. ü  The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used. ü  Natural" ordering is the ordering implied by the implementation of the Comparable interface by the objects used as keys in the TreeMap. Essentially, RBTree must be able to tell which key is smaller than the other key, and there are two ways to supply that logic to the RBTree implementation: ü  Implement Comparable interface in the class(es) used as keys to TreeMap, or ü  Supply an implementation of the Comparator that would do comparing outside the key class itself. ü  All keys inserted into the map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable ü  One should use TreeMap only when we have a large data and need frequent search operation ü  TreeMap uses a binary tree organization that gives balanced trees, so O(log2N) is the worst case lookup time. ü  Using TreeMap and TreeSet work properly when compareTo and equals are implemented in such a way that they are compatible with each other. Furthermore, when searching in a Map, only the search for the key will be efficient (for a TreeMap O(log n)). When searching for a value in a Map, the complexity will become linear. ü  There is a way to optimize the search in the inner TreeSet though, when implementing your own Comparator for the Element type. This way you can implement your own compareTo method without changing the Element object itself.

package com.study.collection; import java.util.Comparator; import java.util.Map; import java.util.SortedMap; import java.util.TreeMap; public class TreeMapDemo {       /**        * @param args        */       public static void main(String[] args) {             // TODO Auto-generated method stub             TreeMap<String, String> tree = new TreeMap<String, String>();             tree.put("4", "A");             tree.put("3", "B");             tree.put("5", "C");             tree.put("7", "D");             for (Map.Entry<String, String> entry : tree.entrySet()) {                   System.out.println("Key = " + entry.getKey() + ", Value = "                               + entry.getValue());             }             System.out.println("====== headMap method usage ==============");             SortedMap<String, String> sort = tree.headMap("5");             for (Map.Entry<String, String> entry : sort.entrySet()) {                   System.out.println("Key = " + entry.getKey() + ", Value = "                               + entry.getValue());             }             System.out.println("====== tailMap method usage ==============");             SortedMap<String, String> sortTail = tree.tailMap("5");             for (Map.Entry<String, String> entry : sortTail.entrySet()) {                   System.out.println("Key = " + entry.getKey() + ", Value = "                               + entry.getValue());             }             System.out.println("====== tailMap method usage ==============");             SortedMap<String, String> subMap = tree.subMap("2", "8");             for (Map.Entry<String, String> entry : subMap.entrySet()) {                   System.out.println("Key = " + entry.getKey() + ", Value = "                               + entry.getValue());             }             // Sort by value             System.out.println("==========================================");             System.out.println("Sorted by value ASC = "                         + TreeMapDemo.sortByValues(tree));       }       // How to sort TreeMap by value in desc       public static <K, V extends Comparable<V>> Map<K, V> sortByValues(                   final Map<K, V> map) {             Comparator<K> valueComparator = new Comparator<K>() {                   public int compare(K k1, K k2) {                         int compare = map.get(k1).compareTo(map.get(k2));                         if (compare == 0)                               return 1;                         else                               return compare;                   }             };             Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);             sortedByValues.putAll(map);             return sortedByValues;       } } o/p Key = 3, Value = B Key = 4, Value = A Key = 5, Value = C Key = 7, Value = D ====== headMap method usage ============== Key = 3, Value = B Key = 4, Value = A ====== tailMap method usage ============== Key = 5, Value = C Key = 7, Value = D ====== tailMap method usage ============== Key = 3, Value = B Key = 4, Value = A Key = 5, Value = C Key = 7, Value = D =========================================== Sorted by value ASC = {4=A, 3=B, 5=C, 7=D}

19. Collection Name	java.util.WeakHashMap
Implementation Of	extends AbstractMap<K,V> implements Map<K,V>
Is Ordered	No
Is Resizable	Yes
Is Thread Safe	NO.  can use Collections.synchronizedSortedMap
Duplicate allowed	A map cannot contain duplicate keys
Null allowed	Both null values and the null key are supported.
Iterate Logic	entry set iterator
Complexity	log(n)
More info	ü  Hash table based implementation of the Map interface, with weak keys. ü  An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use. More precisely, the presence of a mapping for a given key will not prevent the key from being discarded by the garbage collector, that is, made finalizable, finalized, and then reclaimed. When a key has been discarded its entry is effectively removed from the map, so this class behaves somewhat differently from other Map implementations. ü  This class has performance characteristics similar to those of the HashMap class, and has the same efficiency parameters of initial capacity and load factor. ü  The behavior of the WeakHashMap class depends in part upon the actions of the garbage collector, so several familiar (though not required) Map invariants do not hold for this class. ü  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. ü  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.

package com.study.collection; import java.util.HashMap; import java.util.Map; import java.util.WeakHashMap; public class WeakHashMapDemo {       /**        * @param args        * @throws InterruptedException        */       public static void main(String[] args) throws InterruptedException {             Map hashMap = new HashMap();             Map weakHashMap = new WeakHashMap();             String keyHashMap = new String("keyHashMap");             String keyWeakHashMap = new String("keyWeakHashMap");             hashMap.put(keyHashMap, "A");             weakHashMap.put(keyWeakHashMap, "B");                         System.gc();             System.out.println("Before: hash map value:"                         + hashMap.get("keyHashMap") + " and weak hash map value:"                         + weakHashMap.get("keyWeakHashMap"));             //Make elligible for garbage collection             keyHashMap = null;             keyWeakHashMap = null;             System.out.println("Running Garbage Collector....");             System.gc();             System.out.println("After: hash map value:" + hashMap.get("keyHashMap")                         + " and weak hash map value:"                         + weakHashMap.get("keyWeakHashMap"));                           } } O/P Before: hash map value:A and weak hash map value:B Running Garbage Collector.... After: hash map value:A and weak hash map value:null

20. Collection Name	java.util. IdentityHashMap
Implementation Of	extends AbstractMap<K,V>  implements Map<K,V>, Serializable, Cloneable
Is Ordered	No
Is Resizable	Yes
Is Thread Safe	No.  Collections.synchronizedMap(new IdentityHashMap(...));
Duplicate allowed	Two keys k1 and k2 are considered equal if and only if (k1==k2).
Null allowed
Iterate Logic	Iterator<Entry<K,V>> i = entrySet().iterator();
Complexity
More info	ü  This class implements the Map interface with a hash table, using reference-equality in place of object-equality when comparing keys (and values). ü  In other words, 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)).) ü  This class is not a general-purpose Map implementation! While this class implements the Map interface, 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. ü  HashMap creates Entry objects every time you add an object, which can put a lot of stress on the GC when you've got lots of objects. In a HashMap with 1,000 objects or more, you'll end up using a good portion of your CPU just having the GC clean up entries (in situations like pathfinding or other one-shot collections that are created and then cleaned up). IdentityHashMap doesn't have this problem, so will end up being significantly faster ü  Its very fast and consume less memory

package com.study.collection; import java.util.IdentityHashMap; public class IdentityHashMapDemo {       /**        * @param args        */       public static void main(String[] args) {             // TODO Auto-generated method stub             IdentityHashMap map1 = new IdentityHashMap();             String s1 = new String("1");             String s2 = new String("1");             map1.put(s1, "value");             map1.put(s2, "value");             map1.put("2", "value");             map1.put("3", "value");             System.out.println("Map key as different Object referance value = "                         + map1.size());             IdentityHashMap map2 = new IdentityHashMap();             String s3 = s1;             map2.put(s1, "value");             map2.put(s3, "value");             map2.put("2", "value");             map2.put("3", "value");             System.out.println("Map key as same object referance value = "                         + map2.size());       } } o/p Map key as different Object referance value = 4 Map key as same object referance value = 3

21. Collection Name	java.util. LinkedHashMap
Implementation Of	extends HashMap<K,V> implements Map<K,V>
Is Ordered	Yes, Order of insertion
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<Entry<K, V>> mapValues = map.entrySet();
Complexity	Read/Search any element O(1)/Update : O(1)/Delete : O(1)/Add at beginning: O(1)/Add in middle: O(n)/Add at end: O(n)
More info	ü  This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). ü  Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.) ü  This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose order is determined by that of the copy. (Clients generally appreciate having things returned in the same order they were presented.) ü  A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order) ü  It maintains a doubly-linked list because with an additional hash map, you can implement deletes in O(1). If you are using a singly linked list, delete would take O(n). ü  Consider a hash map for storing a key value pair, and another internal hash map with keys pointing to nodes in the linked list. When deleting, if it's a doubly linked list, I can easily get to the previous element and make it point to the following element. This is not possible with a singly linked list. ü  Consider a hash map for storing a key value pair, and another internal hash map with keys pointing to nodes in the linked list. When deleting, if it's a doubly linked list, we can easily get to the previous element and make it point to the following element. This is not possible with a singly linked list. ü  The putAll method is used to copy all of the mappings from the specified map to this map. Copies all of the mappings from the specified map to this map (optional operation). The effect of this call is equivalent to that of calling put(k, v) on this map once for each mapping from key k to value v in the specified map. The behavior of this operation is undefined if the specified map is modified while the operation is in progress. ` ü  "one entry access for each mapping" means the effect of putall call is equivalent to that of calling put(k, v) on this map once for each mapping from key k to value v in the specified map. ü  How it works internally? Internally LinkedHashMap uses an Entry object called header as a starting node to link with all the items that you add to the map. So in this case it will be The header Entry object is both the start and the end of the doubly linked list since header.before = header.after = header when it initially constructs.               [header] ->  ["a"] -> ["b"] -> ["c"] -> ["d"] -> [header] A zero size LinkedHashMap contains just the Head element with before and after pointing to itself. void init() { header = new Entry<K,V>(-1, null, null, null); header.before = header.after = header; } Each node contains references to the previous and to the next node . A new node is always added to the end of the list. In order to do so, the last node's and the header node's links have to be adjusted. The new node's next reference will point to the head. The new node's previous reference will point to the current last node. The current last node's next reference will point to the new node instead of head. Head's previous reference will point to the new node private static class Entry<K,V> extends HashMap.Entry<K,V> {      // These fields comprise the doubly linked list used for iteration.         Entry<K,V> before, after;         Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {           super(hash, key, value, next);         } An entry finds its location in the array based on its hash value. If an array element is already occupied, the new entry replaces the old entry and the old entry is linked to the new one.

22. Collection Name	java.util.Set
Implementation Of	extends Collection<E>
Is Ordered	No. Depends on subtypes.
Is Resizable	Yes
Is Thread Safe	No. Depends on subtypes .
Duplicate allowed	No
Null allowed	At most one null element
Iterate Logic	Iterator<E>  iterator();
Complexity	Worst case O(n), best case O(1)
More info	ü  A Set is a Collection that cannot contains duplicate elements ü  Method declared in set is almost similar to Collection interface but they have different meaning, adds the restriction that duplicate elements are prohibited and also helpful in creating more specific java documentation. ü  Two Set instances are equal if they contain the same elements. ü  Some set implementations have restrictions on the elements that they may contain. For example, some implementations prohibit null elements, and some have restrictions on the types of their elements. Attempting to add an ineligible element throws an unchecked exception, typically NullPointerException or ClassCastException. ü  If you insert duplicate in Set it will replace the older value.

23. Collection Name	java.util. AbstractSet
Implementation Of	extends AbstractCollection<E> implements Set<E>
Is Ordered	No
Is Resizable	Yes
Is Thread Safe	No. Depends on subtypes
Duplicate allowed	No
Null allowed	No
Iterate Logic	Iterator<E> iterator();
Complexity	NA
More info	ü  Note that this class does not override any of the implementations from the AbstractCollection class. It merely adds implementations for equals and hashCode. ü  Implements method like ·         removeAll() ·         hashCode() ·         equals(Object o) ü  equals(Object o)  Returns true if the given object is also a set, the two sets have the same size, and every member of the given set is contained in this set. This ensures that the equals method works properly across different implementations of the Set interface. This implementation first checks if the specified object is this set; if so it returns true. Then, it checks if the specified object is a set whose size is identical to the size of this set; if not, it returns false. If so, it returns containsAll((Collection) o). ü  hashCode() returns the hash code value for this set. The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hash code of a null element is defined to be zero. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two sets s1 and s2, as required by the general contract of java.lang.Object.hashCode(). This implementation iterates over the set, calling the hashCode method on each element in the set, and adding up the results.

Coming soon .. Things must know about java collection API - Part IV