ITV-Collection-How HasMap works?

1.A)How HasMap works?

1. HashMap in Java works on hashing principle. 
2. It is a data structure which allows us to store object and retrieve it in constant time O(1) provided we know the key.
3.  In hashing, hash functions are used to link key and value in HashMap. Objects are stored by calling put(key, value)method of HashMap and retrieved by calling get(key) method.
4. When we call put method, hashcode() method of the key object is called so that hash function of the map can find a bucket location to store value object, which is actually an index of the internal array, known as the table.
5. HashMap internally stores mapping in the form of Map.Entry object which contains both key and value object.
6. When you want to retrieve the object, you call the get() method and again pass the key object.
7.  This time again key object generate same hash code (it's mandatory for it to do so to retrieve the object and that's why HashMap keys are immutable e.g. String) and we end up at same bucket location.
8.  If there is only one object then it is returned and that's your value object which you have stored earlier.
9. Since the internal array of HashMap is of fixed size, and if you keep storing objects, at some point of time hash function will return same bucket location for two different keys, this is called collision in HashMap. In this case, a linked list is formed at that bucket location and a new entry is stored as next node.
10. If we try to retrieve an object from this linked list, we need an extra check to search correct value, this is done by equals() method. Since each node contains an entry, HashMap keeps comparing entry's key object with the passed key using equals() and when it return true, Map returns the corresponding value.
11. Since searching inlined list is O(n) operation, in worst case hash collision reduce a map to linked list. This issue is recently addressed in Java 8 by replacing linked list to the tree to search in O(logN) time. By the way, you can easily verify how HashMap works by looking at the code of HashMap.java 
    

1.B)why to use hashmap ?

1. Maps are used for when you want to associate a key with a value and Lists are an ordered collection. Map is an interface in the Java Collection Framework and a HashMap is one implementation of the Map interface. 
2. HashMap are efficient for locating a value based on a key and inserting and deleting values based on a key.

1.C)When to use HashMap over LinkedList or ArrayList and vice-versa

https://stackoverflow.com/questions/7975802/when-to-use-hashmap-over-linkedlist-or-arraylist-and-vice-versa#

1. Lists represent a sequential ordering of elements. Maps are used to represent a collection of key / value pairs.
2. While you could use a map as a list, there are some definite downsides of doing so.
3. Maintaining order: - A list by definition is ordered. You add items and then you are able to iterate back through the list in the order that you inserted the items. When you add items to a HashMap, you are not guaranteed to retrieve the items in the same order you put them in. There are subclasses of HashMap like LinkedHashMap that will maintain the order, but in general order is not guaranteed with a Map.
4. Key/Value semantics: - The purpose of a map is to store items based on a key that can be used to retrieve the item at a later point. Similar functionality can only be achieved with a list in the limited case where the key happens to be the position in the list.

Code readability Consider the following examples.

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

Collection functionality Some great utility functions are available for lists via the Collections class. For example ...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);  

1.D)When should we use HashMap over ArrayList?

https://www.quora.com/When-should-we-use-HashMap-over-ArrayList

ArrayList and HashMap are both part of collection framework which are very commonly used, but they differ in the way they store and process data.

ArrayList : Re-sizable array implementation of the List interface. It maintains the insertion order and can have duplicate values as well.

HashMap : Hash table based implementation of the Map interface. It stores the data in form of key-value pair where key must be unique. No order of data is maintained. It provides the constant time performance for the basic operations.

Now that the basic background is clear, lets get back to the question “ When should we use HashMap over ArrayList?”

1. When you can identify your data with some unique key i.e. your data can be processed in key value pair.
2. When no index based operations is required, instead key based operations are preferred.

1.E)10 things a java developer should know about HashMap

   

(1) Internals of lookup process:

Lookup process is at the heart of HashMap and almost all the complexity of hashMap lies here. The lookup process consists of 2 steps:

Step# 1: Quickly determine the bucket number in which this element may reside (using key.hashCode()).

Step# 2: Go over the mini-list and return the element that matches the key (using key.equals()).

Note the the value object is not used in any of the calculations within hashMap.



(2) Immutability of keys:

A class that we plan to use as a “key” in hashMap needs to follow certain restrictions.

If the object which is used as key in hashMap is modified, then we may have problem retrieving values from hashMap.

Let's say I use an object as key, and put this key and associated value into hashMap. Later I modify one of the properties of this key. If hashCode() and equals() method make use of this property, then we may not find this key in hashMap. If the property being modified is not being used by hashCode() and equals(), then we will still be able to find the key in hashMap. 

To do away with this issue altogether, recommendation is to use immutable classes as keys.

Note, that even if only one of the methods hashCode() or equals() return different results(when a property is modified), the key becomes useless from the lookup perspective.



(3) Load factor and resize:

When a hashMap resizes, it will double in size and create a new instance and populate it.

When new hashHap is being populated, the linkedList associated with each bucket of source hashMap is iterated and nodes are copied to the destination bucket. However, note that these new nodes are prepended to the head of the destination linkedList. So resizing has an side effect of reversing the order of the items in the list. Default load factor for hashMap is 0.75.



(4) Worst-case performance:

In the worst case, a hashMap reduces to a linkedList.

However with Java 8, there is a change,

Java 8 intelligently determines if we are running in the worst-case performance scenario and converts the list into a binary search tree.



(5) Collisions:

Collisions happen when 2 distinct keys generate the same hashCode() value. Multiple collisions are the result of bad hashCode() algorithm.

The more the collisions the worse the performance of the hashMap.

There are many collision-resolution strategies - chaining, double-hashing, clustering.

However, java has chosen chaining strategy for hashMap, so in case of collisions, items are chained together just like in a linkedList.



(6) Adding duplicate entries into hashMap:

Attempt to put the same key with a different value, will overwrite the old value.

1: hashHap.put(myKey, oldValue);

2: hashHap.put(myKey, newValue);

3: hashMap.get(myKey);// This line will return newValue

Line# 2, above will essentially over-write oldValue with newValue. so hashMap.put() is actually "add or overwrite".



(7) Concurrency:

Do not use HashMap in multi-threaded environment.
What if 2 threads starts resizing the hashMap at the same time?
(8) Map of maps:

HashMap of hashMaps are very popular.
Pseudo code below to give an idea:

Map<String, Map<String, Object>> multiHashMap = new HashMap<>();
Map<String, Object> myHashMap1;
Map<String, Object> myHashMap2;
multiHashMap.put(“one”, myHashMap1);
multiHashMap.put(“two”, myHashMap2);

Also, "multimap" is a common dataStructure, where value is a collection.
You use the key to retrieve the collection and the manipulate the collection.
Map<Double,List<Object>> multiMap = new TreeMap<Double,List<Object>>();

(9) Some specialized hashMaps for specific purposes:

- ConcurrentHashMap: HashMap to be used in multithreaded applications.

- EnumMap: HashMap with Enum values as keys.

- LinkedHashMap: HashMap with predictable iteration order (great for FIFO/LIFO caches)



(10) Code samples:

It is really insightful to jump into the source, here is how hashCode() and equals() are implemented in jdk.

(a) Here is how String.hashCode() and String.equals() are implemented.

(b) Here is how Object.hashCode() and Object.equals() are implemented.

1.F)What will happen if two different objects have the same hashcode?
https://stackoverflow.com/questions/6493605/how-does-a-java-hashmap-handle-different-objects-with-the-same-hash-code/6493946
https://stackoverflow.com/questions/11195027/what-happens-if-two-different-objects-have-the-same-hashcode

1.G)What will happen if two different objects have the same hashcode?
https://coderanch.com/t/540275/java/objects-hashcode-HashMap-retrieve-objects

1.H)How will you retrieve Value object  if two Keys will have the same hashcode?
https://stackoverflow.com/questions/27817985/how-will-you-retrieve-value-object-if-two-keys-will-have-same-hashcodehttps://stackoverflow.com/questions/27817985/how-will-you-retrieve-value-object-if-two-keys-will-have-same-hashcode/27818081#27818081

What will happen if two different HashMap  key objects have the same hashcode?

They will be stored in the same bucket but no next node of linked list. And keys equals () method will be used to identify correct key value pair in HashMap.

How null key is handled in HashMap? Since equals() and hashCode() are used to store and retrieve values, how does it work in case of the null key?
The null key is handled specially in HashMap, there are two separate methods for that putForNullKey(V value) and getForNullKey(). Later is offloaded version of get() to look up null keys.  Null keys always map to index 0.  This null case is split out into separate methods for the sake of performance in the two most commonly used operations (get and put), but incorporated with conditionals in others. In short, equals() and hashcode() method are not used in case of null keys in HashMap.

here is how nulls are retrieved from HashMap

   private V getForNullKey() {

        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

In terms of usage, Java HashMap is very versatile and I have mostly used HashMap as cache in an electronic trading application I have worked. Since finance domain used Java heavily and due to performance reason we need caching HashMap and ConcurrentHashMap  comes as very handy there. You can also check following articles from Javarevisited to learn more about HashMap and Hashtable in Java: