JavaByPatel: Data structures and algorithms interview questions in Java: What is Hashmap data structure? What is the need of Hashmap? How Hashmap data structure API works in Java? What is Hashcode? Can 2 objects have same hashcode?

What is Hashmap data structure?
What is the need of Hashmap?
How Hashmap data structure API works in Java?
What is Hashcode?
Can 2 objects have same hashcode?

This is the famous interview question for the beginners as well as for experienced, So Let's see what it is all about. Hashmap is very popular data structure and found useful for solving many problems due to O(1) time complexity for both get and put operation.

What is the need of Hashmap data structure? What problem it solves?

When we have many objects and if we want to search a particular object among them,
How to search??
(Say we have 100 Student object and we want to search Student having Roll No. 35, how to do?)

We pick one object and see, this is the object we are looking for? No.
Pick next object and check again. Repeat the steps until we found the object.
Imagine the time it will take???

The time it will take to search a particular object will be even high if total objects are more.
This is where hashmap will come in picture.

Hashmap arranges the objects in such a way, that searching any object in hashmap will be done in almost O(1) complexity.

How arranging items in particular way can make searching faster. Lets see with example,

Ms. Khyati is working for XYZ Computers in Bangalore and for work assignment she has to relocate to Pune for 1 month.
Khyati noted down important house items to carry for 1 month and started packing like shown below,
She packed all items randomly in 2 boxes.

After reaching Pune, before unpacking any item, She got a call from office to report as soon as possible. Khyati wants to apply hair-oil before going to office, but which box contains hair-oil??

Now Khyati started searching for "hair oil" in Box 1 and she didn't able to find there.
She started searching in Box 2 and she found there.

As there was only 2 boxes, she was able found hair-oil in 10 minutes, What if there was 50 boxes filled with house items. The time it will take for searching hair-oil will be much more.

If Khyati had applied some smartness while packing items, then searching can be made faster.
If items are distributed across several boxes based on its type like,
Kitchen items in one box, Liquid items in one box, Electronic items in one box.
Then the time it will take to search any particular item will be very less.

Now, If she needs hair-oil, She can directly look into Liquid item box and discard looking into other boxes.

So, arranging data in particular way, can make searching very fast. Hashmap exactly does the same thing.

Whenever any object is placed inside hashmap, It doesn't put into it blindly, instead it puts data in such a way that, searching for data can be done very easily.

Hashmap basically solves the problem of searching objects from large set.
Hashmap will be very helpful when there is large set of objects and frequent access to objects will be required. So instead of every time searching the object sequentially, hashmap can be used which searches very fast.

How Hashmap data structure API works?

Hashmap is a data structure that maps keys to values.

HashMap hashMap = new HashMap();
hashMap.put( key , value );

Lets understand it with an example:

Hashmap internally maintains table of Key-Value pair like shown above.

Put Method
1. When request comes to put any key-value pair, say hashMap.put("hello","world");
     (here key to store is "hello" and value is "world).
   It checks the table and see, is there any Key-Value pair present in table, which has the same
     key as "hello"
2. If there is NO such key(hello) present, then hashmap will create one new key-value pair
     and put it.
3. If there is key present, then hashmap will not create new key-value pair instead it will simply
     replace the value against matched key.

Get Method
1. When request comes to get any key-value pair, say hashMap.get("hello");
    get() method checks in the table for the key(hello) supplied.
2. If the match key is found in the table, then it gives the value stored against that key.
(In our Case, it will return "world")
3. If no matching key is found in the table, then it returns null.

Example:
        System.out.println( hashMap.get("hello") );
        Output:
                 myworld

Hashmap table structure which is displayed in figure above looks simple, but internally it is bit complex to get time complexity O(1) for both get and put operation.

What is Hashcode?

Hashcode is integer value that identifies the object and is built using object's hashcode() method.
Every object have hashcode() method, when called, it returns integer value that represents object.

Two different objects can have same identifier/hashcode, in that case, to uniquely identify an object, other properties of object is used.

Lets understand it with "Employee Letter Box" example,

From above letter box example we can say,
hashcode is a integer value given to an object which identifies it.
hashcode of an object is generated using hashcode() method, which looks into object properties, manipulate on it and come up with specific integer value which represents that object.
hashcode is basically used for distributing and arranging objects across hashmap table.

As we saw, with the help of hashcode, searching for the Letter within Letter box became very fast.
Employee just need to go into appropriate Letter box and search letter only within that box and discard other boxes. This make searching for Letter very fast.

So, Tim will have hashcode "T" and Ted will also have hashcode "T". both Employee's Letter will be placed in same Letter box marked "T".
Letter box marked "T" will have letters from other Employee's as well, but all of those Employee name should be starting with "T", that is their hashcode should be same.

hashcode in above example is "First Letter of Employee name" and is used to distribute Letters across the Letter box instead of dumping all letters in one box. By distribution, Searching for letter became very fast.

In our previous, packing and moving example, systematic arrangement of house items like,
Liquid items to place in Liquid Items Box. Kitchen items in Kitchen item box,
Electronic items in Electronic Items Box. etc.
So, packing items in systematic manner helps searching item easier.
So guess what will be hashcode here?????
hashcode here is item type, based on which decision is taken, whether it will be part of which box.

Hashcode of "Spoon" will be "Kitchen", Hashcode of "iPod" will be "Electronics",
Hashcode of "Hanger" will be "Clothing", Hashcode of "Tea cup" will be "Kitchen".
Hashcode of "Mobile" will be "Electronics" etc.

So we saw, hashcode is used basically to distribute the objects systematically, so that searching can be done faster.

Why we need hashcode of object? what is the use of Hashcode?

Hashcode has many useful application and one of popular data structure Hashmap uses Objects's hashcode as its base for storing and retrieving object.
With the help of hashcode, it distributes objects in such a way, that both putting the object in hashmap and look up for any object within hashmap can be done very quickly, almost with O(1) time complexity.

Hashcode help in Packing and Moving example.

Can two objects have same hashcode?

Yes. Two objects can very well have same hashcode.

In our Packers & Movers example, we saw that hashcode/item type, for Tea cup and Spoon evaluate same, that is both are Kitchen item.

In our Letter Box example, we saw that hashcode of "Tim" and "Ted" evaluate same, that is both have hashcode "T".

If two Objects have same hashcode, it doesn't mean both are same. hashcode is used to group all Objects having same hashcode at one place, So that searching within them can be done faster compare to all Objects dumped at one place.

So here 2 Employee, Ted and Tim have same hashcode, it doesn't mean they both are same.
For finding their respective letters, they still have to look into all Letters present inside Letter box marked "T".

Hashcode only helped in arrangement of letters, which actually made searching faster.

So, In object perspective, two in-different object's can have same hashcode and to uniquely identify it, each object need to be scan and see, whether it is the same object we are looking for.

That is where hashcode() and equals() method come into picture.

1. hashcode() method generate hashcode/identifier of a object. (which can be same for 2 different objects).
2. Once hashcode is evaluated, equals() method helps us to look within the objects that have
the same hashcodes and get the object we are interested in by comparing object internal properties.

hashcode() methods helps in finding the correct Letter box.
equals() method helps to look for each letter within that Letter box.

JavaByPatel: Data structures and algorithms interview questions in Java

Wednesday, 30 September 2015

What is Hashmap data structure? What is the need of Hashmap? How Hashmap data structure API works in Java? What is Hashcode? Can 2 objects have same hashcode?

What is Hashmap data structure?
What is the need of Hashmap?
How Hashmap data structure API works in Java?
What is Hashcode?
Can 2 objects have same hashcode?