Map Interface

Map-Hashtable-HashMap-WeakHashMap-IdentityHashMap

MAP Interface:A Map is an object that maps keys to values. Maps cannot contain duplicate keys: Each key can map to at most one value.

• Map is not the child interface of Collection interface
• If you want to store the values or objects as key value pairs we go for the Map interface
• Both key and values are objects
• Duplication of keys is not allowed but values may be duplicated
• Key –Value Pair is called an Entry

Methods in Map Interface:
1)Object put(Object key,Object value) //Inserts a value into the map.if the key is already exists it will replace the old values with new one
2)Object get(Object key) // Returns the value associated with the key otherwise returns null
3)Object remove(Object key) // It removes the entry associated with the key and returns the corresponding value otherwise returns null
4)boolean containsKey(Object key)
5)boolean containsValue(Object key)
6)int size()
7)boolean isEmpty()
8)void clean()
9)void putAll(Map m)
10)Set keySet()
11)Collection values()
12)Set emptySet()
// The following three methods collection view of Map
13)Object getKey();
14)Object getValue();
15)Object setValue(Object obj)
//Entry is an inner interface present inside the map.It contains
the following three methods which can be applied on the entry object.
16)Object getKey();
17)Object getValue();
18)Object setValue(Object obj)

Note:
interface Map{
Interface Entry{ // inner interface entry
Object getKey();
Object getValue();
Object setValue(Object obj)
}
}

Hashtable:

• The underlying datastructure for the Hastable is the HashTable itself.
• Heterogeneous values are allowed for both keys and values
• null insertion is allowed for both keys and values for the first element violation leads to NullPointerException
• Almost all methods or Hashtable are synchronized hence it is thread safe
• Insertion order is not preserved and the objects are arranged based on hashcode
• Duplicate objects for values but keys are not to be duplicated

Hashtable Constructors:
Hashtable table=new Hashtable();
Hashtable table=new Hashtable(int initialCapacity);
Hashtable table=new Hashtable(int initialCapacity,float fillRatio);
Hashtable table=new Hashtable(Map m);

Hashtable Demo:
import java.util.Hashtable;

public class HashtableEx1 {
public static void main(String[] args) {
Hashtable table=new Hashtable();
table.put(new Integer(1),"xxx");
table.put(new Integer(24),"yyy");
table.put(new Integer(3),"zzz");
table.put(new Integer(8),"aaa");
table.put(new Integer(9),"bbb");
table.put(new Integer(2),"sss");
System.out.println("The Hashtable is "+table);
}
}

output:
The Hashtable is {9=bbb, 8=aaa, 3=zzz, 2=sss, 24=yyy, 1=xxx}


HashMap:

• The underlying datastructure for HashMap is Hashtable
• Duplicate keys are not allowed but values may be duplicated,i.e, it replace the new value for the key which is duplicated.

e.g :

            HashMap map=new HashMap();

            map.put(4, "Hi");

            map.put (1,"abhi");

            map.put (2,"abhinav");

            map.put(1,"mishra");

            map.put(3,"hello");

            System.out.println("The map: "+map);

     o/p>> The map: {1=mishra, 2=abhinav, 3=hello, 4=Hi}

  

    /**

     * Constructs an empty <tt>HashMap</tt> with the default initial capacity

     * (16) and the default load factor (0.75).

     */

    public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);

        table = new Entry[DEFAULT_INITIAL_CAPACITY];

        init();

    }

• Insertion order is not preserved
• Heterogeneous key and values are allowed
• Null key and values are allowed.

HashMap Constructors:
1) HashMap map=new HashMap();
it Create the empty hashmap with the default initial capacity 16 and fillRatio 0.75
2) HashMap map=new HashMap(int initialCapacity);
it Create a HashMap with the specified nitialCapacity and default load factor
3) HashMap map=new HashMap(int nitialCapacity,float loadFactor);
4) HashMap map=new HashMap(Map m);

HashMapDemo Program:
import java.util.*;
public class HashMapEx1 {
public static void main(String... args) {
HashMap map=new HashMap();
map.put("orange",new Integer(1000));
map.put("apple",new Integer(2000));
map.put("banana",new Integer(3000));
map.put("grapes",new Integer(4000));
System.out.println("The Map "+map);
System.out.println(map.put(("orange"),new Integer(1001)));
System.out.println("map "+map);
Set s=map.keySet();
System.out.println("The Key Set"+s);
Collection values=map.values();
System.out.println("The Values Are "+values);
Set s1=map.entrySet();
System.out.println("The Entry Set"+s1);
}
}


output:
The Map {orange=1000, grapes=4000, apple=2000, banana=3000}
1000
map {orange=1001, grapes=4000, apple=2000, banana=3000}
The Key Set[orange, grapes, apple, banana]
The Values Are [1001, 4000, 2000, 3000]
The Entry Set[orange=1001, grapes=4000, apple=2000, banana=3000]

LinkedHashMap:
It is exactly similar to the HashMap except the following differences

LinedHashMap:

• Underlying datastructures are hashtable and doubly linkedlist
• Insertion order of elements is preserved
• While iterating elements we can give guarantee for processing order.Hence we can use for caching.

HashMap

• Insertion order is not preserved
• While iterating we can not give guarantee for processing order. Hence we can not use it for caching
• Underlying datastructure is Hashtable

HashMap is a collection class that is designed to store elements as key-value pairs. Maps provide a way of looking up one thing based on the value of another.

We modify the above code by use of the HashMap class to store words along with their frequencies.

String[] data = new String("Nothing is as easy as it looks").split(" ");
HashMap‹String, Integer> hm = new HashMap‹String, Integer>();

for (String key : data)

{
  Integer freq = hm.get(key);

  if(freq == null) freq = 1; else freq ++;

  hm.put(key, freq);

}

System.out.println(hm);

This prints {as=2, Nothing=1, it=1, easy=1, is=1, looks=1}.

HashSet and HashMap will be printed in no particular order. If the order of insertion is important in your application, you should use LinkeHashSet and/or LinkedHashMap classes. If you want to print data in sorted order, you should use TreeSet and or TreeMap classes

NOTE:-

Ø LinkedHashMap/ LinkedHashSet are used when the order of insertion is important in your application, because these classes the iteration ordering method for this linked hash map and linked hash set is true for access-order and false for insertion order.

        public LinkedHashMap() {

           super();

             accessOrder = false;

          }

            And

       

               public LinkedHashSet() {

             super();

             accessOrder = false;

          }

Ø If you want to print data in sorted order, you should use TreeSet and or TreeMap classes

The following are some of the HashMap methods:

• map.get(key) -- returns the value associated with that key. If the map does not associate any value with that key then it returns null. Referring to "map.get(key)" is similar to referring to "A[key]" for an array A.
• map.put(key,value) -- adds the key-value pair to the map. This is similar to "A[key] = value" for an array A.
• map.containsKey(key) -- returns true if the map has that key.
• map.containsValue(value) -- returns true if the map has that value.
• map.keySet() -- returns a set of all keys
• map.values() -- returns a collection of all value

IdentityHashMap:
In case of HashMap JVM uses the equals() method to identify the duplicate keys
But if want to use the == operator to identify the duplicates we go for the IdentityHashMap
Incase of IdentityHashMap two key reference i1 and i2 are equal if and only if bot i1 and i2 are pointing to the same object on the heap

IdentityHashMap Demo Program:
import java.util.IdentityHashMap;

public class IdentityHashMapEx1 {
public static void main(String... args) {
IdentityHashMap map=new IdentityHashMap ();
Integer i1=new Integer(10);
Integer i2=new Integer(10);
map.put(i1,"orange");
map.put(i2,"apple");
System.out.println("The Map"+map);
}
}


WeakHashMap:

• WeakHashMap is not a child class of HashMap
• HashMap dominates the garbage collector.if any objects are associated with the HashMap eventhough that object does not have any external references .Garbage collector is not allowed to destroy that object
• But garbage collector dominate the WeakHashMap that is in case of hashmap if the key is not reachable garbage collector is allowed to destroy whole entry associated with the key

WeakHashMap Demo Program:
import java.util.WeakHashMap;
class Temp {
public void finalize() {
System.out.println("finalize() Called");
}
public String toString() {
return "Temp";
}
}
public class WeakHashMapEx1 {
public static void main(String[] args) {
WeakHashMap map=new WeakHashMap();
Temp t=new Temp();
map.put(t,"orange");
t=null;
System.gc();
System.out.println("The Map"+map);
}
}

output:
finalize() Called
The Map{}

Why ConcurrentHashMap is better than Hashtable and just as good as a HashMap...

ConcurrentHashMap is a pretty ignored class. Not many people know about it and not many people care to use it. The class offers a very robust and fast (comparatively, we all know java concurrency isn’t the fastest) method of synchronizing a Map collection.
There is no way you can compare the two, one offers synchronized methods to access a map while the other offers no synchronization whatsoever. What most of us fail to notice is that while our applications, web applications especially, work fine during the development & testing phase, they usually go tits up under heavy (or even moderately heavy) load. This is due to the fact that we expect our HashMap’s to behave a certain way but under load they usually misbehave.
Hashtable’s offer concurrent access to their entries, with a small caveat, the entire map is locked to perform any sort of operation. While this overhead is ignorable in a web application under normal load, under heavy load it can lead to delayed response times and overtaxing of your server for no good reason.
This is where ConcurrentHashMap’s step in. They offer all the features of Hashtable with a performance almost as good as a HashMap. ConcurrentHashMap’s accomplish this by a very simple mechanism. Instead of a map wide lock, the collection maintains a list of 16 locks by default, each of which is used to guard (or lock on) a single bucket of the map. This effectively means that 16 threads can modify the collection at a single time (as long as they’re all working on different buckets). Infact there is no operation performed by this collection that locks the entire map. The concurrency level of the collection, the number of threads that can modify it at the same time without blocking, can be increased. However a higher number means more overhead of maintaining this list of locks.
Retrieval operations on a ConcurrentHashMap do not block unless the entry is not found in the bucket or if the value of the entry is null. In such a case the map synchronizes on the bucket and then tries to look for the entry again just in case the entry was put or removed right after the get in synchronized mode.
Removal operations do require a bit of overhead. All removal operations require the chain of elements before and after to be cloned and joined without the removed element. Since the value of the map key is volatile (not really, the value of the inner Entry class is volatile) if a thread already traversing the bucket from which a value is removed reaches the removed element, it automatically sees a null value and knows to ignore such a value.
Traversal in a ConcurrentHashMap does not synchronize on the entire map either. Infact traversal does not synchronize at all except under one condition. The internal LinkedList implementation is aware of the changes to the underlying collection. If it detects any such changes during traversal it synchronizes itself on the bucket it is traversing and then tries to re-read the values. This always insures that while the values recieved are always fresh, there is minimalistic locking if any.
Iteration over a ConcurrentHashMap are a little different from those offered by other collections. The iterators are not fail-fast in the sense that they do not throw a ConcurrentModificationException. They also do not guarantee that once the iterator is created it will list/show all elements that are added after its creation. The iterators do however guarantee that any updates or removal of items will be reflected correctly in their behaviour. They also guarantee that no element will be returned more than once while traversal.
In conclusion, give it a try, replace some Hashtable’s in your application with ConcurrentHashMap and see how they perform under load. The two are interchangeable so it shouldn’t be hard to update your app.

How HashMap works in Java

"Have you used HashMap before" or "What is HashMap? Why do we use it “ 
Almost everybody answers this with yes and then interviewee keep talking about common facts about hashMap like hashMap accpt null while hashtable doesn't, HashMap is not synchronized, hashMap is fast and so on along with basics like its stores key and value pairs etc.
This shows that person has used hashMap and quite familier with the funtionalities HashMap offers but interview takes a sharp turn from here and next set of follow up questions gets more detailed about fundamentals involved in hashmap. Interview here you and come back with questions like

"Do you Know how hashMap works in Java” or 
"How does get () method of HashMap works in Java" 
And then you get answers like I don't bother its standard Java API, you better look code on java; I can find it out in Google at any time etc.
But some interviewee definitely answer this and will say "HashMap works on principle of hashing, we have put () and get () method for storing and retrieving data from hashMap. When we pass an object to put () method to store it on hashMap, hashMap implementation calls
hashcode() method hashMap key object and by applying that hashcode on its own hashing funtion it identifies a bucket location for storing value object , important part here is HashMap stores both key+value in bucket which is essential to understand the retrieving logic. if people fails to recognize this and say it only stores Value in the bucket they will fail to explain the retrieving logic of any object stored in HashMap . This answer is very much acceptable and does make sense that interviewee has fair bit of knowledge how hashing works and how HashMap works in Java.
But this is just start of story and going forward when depth increases a little bit and when you put interviewee on scenarios every java developers faced day by day basis. So next question would be more likely about collision detection and collision resolution in Java HashMap e.g 

"What will happen if two different objects have same hashcode?”
Now from here confusion starts some time interviewer will say that since Hashcode is equal objects are equal and HashMap will throw exception or not store it again etc. then you might want to remind them aobut equals and hashCode() contract that two unequal object in Java very much can have equal hashCode. Some will give up at this point and some will move ahead and say "Since hashCode () is same, bucket location would be same and collision occurs in hashmap, Since HashMap use a linked list to store in bucket, value object will be stored in next node of linked list." great this answer make sense to me though there could be some other collision resolution methods available this is simplest and HashMap does follow this.
But story does not end here and final questions interviewer ask like 

"How will you retrieve if two different objects have same hashCode?” 
 
Interviewee will say we will call get() method and then HashMap uses keys hashCode to find out bucket location and retrieves object but then you need to remind him that there are two objects are stored in same bucket , so they will say about traversal in linked list until we find the value object , then you ask how do you identify value object because you don't value object to compare ,So until they know that HashMap stores both Key and Value in linked list node they won't be able to resolve this issue and will try and fail.

This is the implementation of get() :

Working of get()>>

public V get(Object key) {

        if (key == null)

            return getForNullKey();

        int hash = hash(key.hashCode());

        for (Entry<K,V> e = table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

                return e.value;

        }

        return null;

    }

But those bunch of people who remember this key information will say that after finding bucket location , we will call keys.equals() method to identify correct node in linked list and return associated value object for that key in Java HashMap. Perfect this is the correct answer.

In many cases interviewee fails at this stage because they get confused between hashcode () and equals () and keys and values object in hashMap which is pretty obvious because they are dealing with the hashcode () in all previous questions and equals () come in picture only in case of retrieving value object from HashMap.
Some good developer point out here that using immutable, final object with proper equals () and hashcode () implementation would act as perfect Java HashMap keys and improve performance of Java hashMap by reducing collision. Immutablity also allows caching there hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g. Integer provided by Java Collection API are very good HashMap keys.

Now if you clear all this java hashmap interview question you will be surprised by this very interesting question "What happens On HashMap in Java if the size of the Hashmap exceeds a given threshold defined by load factor?". Until you know how hashmap works exactly you won't be able to answer this question. 
if the size of the map exceeds a given threshold defined by load-factor e.g. if load factor is .75 it will act to re-size the map once it filled 75%. Java Hashmap does that by creating another new bucket array of size twice of previous size of hashmap, and then start putting every old element into that new bucket array and this process is called rehashing because it also applies hash function to find new bucket location. 

If you manage to answer this question on hashmap in java you will be greeted by "do you see any problem with resizing of hashmap in Java" , you might not be able to pick the context and then he will try to give you hint about multiple thread accessing the java hashmap and potentially looking for race condition on HashMap in Java. 

So the answer is Yes there is potential race condition exists while resizing hashmap in Java, if two thread at the same time found that now Java Hashmap needs resizing and they both try to resizing. on the process of resizing of hashmap in Java , the element in bucket which is stored in linked list get reversed in order during there migration to new bucket because java hashmap doesn't append the new element at tail instead it append new element at head to avoid tail traversing. if race condition happens then you will end up with an infinite loop. though this point you can potentially argue that what the hell makes you think to use HashMap in multi-threaded environment to interviewer :) 

How HashMAp works in Java?
HashMap works on principle of hashing, we have put () and get () method for storing and retrieving object form hashMap.When we pass an both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and they by applying hashing on that hashcode it identifies bucket location for storing value object.
While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses linked list in case of collision and object will be stored in next node of linked list.
Also hashMap stores both key+value tuple in every node of linked list.

What will happen if two different HashMap key objects have same hashcode?
They will be stored in same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.

In terms of usage HashMap is very versatile and I have mostly used hashMap as cache in electronic trading application I have worked . Since finance domain used Java heavily and due to performance reason we need caching a lot HashMap comes as very handy there.