HashMap Internal Working - Java

Hashmap working in java

   Hashmap class is equivalent to hashmap besides two things that they are unsynchronized any permits null value.

So what is hashing ?

Hashing means that you use a function or method or algorithm to represent an object with an integer value which makes finding that element quite easy in a storage that can be hashtable ,hashmap or anything that is using hash technique.

Hashmap

Hash map is a collection in which the elements are stored as key-value pair and each element stored is known as an Entry object .

Entry object is an object of  a class named as Entry class which contains :

1.key

2.value.

3.next

4.hash

Now we will look how actually hashmap works and how values are stored in hashmap and retrieved from it?

There are main  methods used for storing and retereiving values from hash map

1.    put() method à to put /store values in hashmap

2.    get() methodàto retrieve data/values from hasmap

Values above means objects not the actual value .

Besides these two methods two more methods plays a vital role in working of hasmap

hashcode()

equals()

Both these methods are defined in Object class only .

Now let us assume we have a map and we put some elements inside it

HashMap<string,string> countryCapitalMap=new HashMap<string,string>();         countryCapitalMap.put(india,"Delhi");         countryCapitalMap.put(japan,"Tokyo");        countryCapitalMap.put(france,"Paris");         countryCapitalMap.put(russia,"Moscow");

So in the above example we have 4 entry objects with 4 key –value pair.

Now we are using put () method to add these objects to a hashmap name countryCapitalmap.

Let look inside code of put() method

public V put(K key, V value) {         if (key == null)             return putForNullKey(value);         int hash = hash(key.hashCode());         int i = indexFor(hash, table.length);         for (Entry<K,V> e = table[i]; e != null; e = e.next) {             Object k;             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                 V oldValue = e.value;                 e.value = value;                 e.recordAccess(this);                 return oldValue;             }         }           modCount++;         addEntry(hash, key, value, i);         return null;     }

First ,hashcode method calculates hashcode of key .

This hashcode actually indicates the index of array which stores entry objects.

The objects are stored in a single link list corresponding to each index which is also konwn as bucket

If two keys have same hashcode that means they will stored on the same index but in the same bucket or linked list .

Let us assume that we have four values in our hashmap.

countryCapitalMap.put(india,"Delhi");         countryCapitalMap.put(japan,"Tokyo");        countryCapitalMap.put(france,"Paris");         countryCapitalMap.put(russia,"Moscow");

And assume that hascode calculated on each key comes as

                                           India ->0

                                           Japan ->0

                                           France->1

                                           Russia ->2

                                           China->2

Hashmap Internal working

By default the size of hashmap is 16 that means there will be 16 buckets and 16 indexes .Here I have shown only 5.

Each node of a link list stores an Entry object which conatins following things

	Key Value Next hash

Above for illustration purposes I have shown only key.

So as india’s hashcode comes as 0and japan’s also 0 ,so the entry object corresponding to india will be stored in first node of linked list at 0 index and as entry object corresponding to japan also have same hashcode so it will stored in the next node to india and next pointer of india will point to japan’s entry object.

You will be confused that when hashcode of both keys is same then the value of india entry object should be replaced no but when hashcode of two entry objects Is same at that time equals() method comes into play .when we have to store key with same hashcode then first equals method checks whether the key for which value is to be stored and the key which is already present in hashmap is same ,if both are same then the value in entry object  is replaced by new value otherwise a new node is created and the new entry object( japan in our case) is stored.

Working of Get method in hashmap

Get method in hashmap is used to retrieve value from hashmap corresponding to a key.

Code of method get () of HashMap:

public V get(Object key) { 20   if (key == null) 21    return getForNullKey(); 22   int hash = hash(key.hashCode()); 23   for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e =     e.next) { 24    Object k; 25    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 26     return e.value; 27   } 28   return null; 29  }

First, same as put method , hashcode of key is calculated .

Then according to hashcode the index in array means index of bucket in which value/entry object is stored.

If there is only one node in the bucket/link list then the value is retrieved from that node.

If there are more than one node in the linklist then  equals() method comes into play .equals( ) methods traverse the list and compare value of each key present in bucket with the one for which we have to retrieve value  and retrieves value from entry object .

Author : Himanshu Bector

Read more

Method Overriding vs Method Overloading

Overriding concept is associated with Inheritance . If we have 2 classes ,one extending the other then child class can override methods of parent class . But there are some rules which needs to be followed :

So we will see which are all these rules :

Rule 1 : The signature of method in the child class should be exactly same as that in Parent class which includes return type, method parameters and name.

Rule 2:  Argument list should be exactly same as that of overridden method.

Rule 3:  Constructors cannot be overridden .

Rule 4:  Static methods cannot be overridden but can be re declared which is actually method hiding .

 .

Method Overloading : Overloading in java occurs when methods in a same class or in child classes shares a same name with a ‘difference in number of arguments’ or ‘difference in argument type’ or both.

Argument list could differ in –
Number of parameters
Data type of parameters
Sequence of data type of parameters

You can read in details with example about Method Overloading here.

Method Overloading	Method Overriding
Signature of method in the child class differs as that in Parent class	Signature of method in the child class should be exactly same as that in Parent class
Argument list could differ in – Number of parameters Data type of parameters Sequence of data type of parameters	Argument list should be exactly same as that of overridden method.
Method overloading a single class is it means both of the method are written in the same clas	Method overriding we have two classes one is parent other is child .Child class Indane contain the overridden method and it  need to extend the parent class .
Method overloading is compile time polymorphism.In method overloading if there is an issue with the method signature it is shown in the eclipse as soon as you write the code	Method overriding is runtime polymorphism

Java Method Overloading example

class javaInHouseOverloadingExample {                    void int add(int a,int b)                 {                  return a+b;                  }                   void int add(int a,int b,int c)                {                 return a+b+c;                 }   }

Java Method Overriding example

class Parent {        void eat()     {      System.out.println("Parent...");      }   }   class Child extends Parent {         void eat()      {       System.out.println("Child..");       }   }

Read more

Abstract Class vs Interface

Well, I can say that interface is for "PURE ABSTRACTION". Pure abstraction means you can not have concrete methods. But an abstract class can have concrete methods. Interfaces should not have any concrete methods, it should only have method declarations.

I will explain the differences between the abstract class and Interface in an old-fashioned tabular format –

Abstract Class	Interface
It can have concrete methods	It can only have abstract methods
It can have variables of any access specifier	It can have only public static final data members(i.e. only constant)
Concrete methods can have any access specifier	For interfaces, all methods are public and abstract by default
A class can extend only one abstract class	A class can implement any no. of interfaces

Abstract classes are meant to be inherited from, and when one class inherits from another it means that there is a strong relationship between the 2 classes.

An abstract class would be better to use or I can say it would be more appropriate when there is a strong relationship between the abstract class and the classes that will derive from it. This is because an abstract class is very closely linked to inheritance, which signifies a strong relationship. But, with interfaces there need not be a strong relationship between the interface and the classes that implement the interface.

In Java, a class can only derive from one class, whether it’s abstract or not. However, a class can implement multiple interfaces – which could be considered as an alternative to for multiple inheritance. So, one major difference between the two is that a Java class can inherit from only one abstract class, but can implement multiple interfaces.

At times there is a lot of confusion among the developers regarding which should one use, abstract classes or interfaces?

Below are some of the scenarios where one can consider using either the abstract class or an interface -

·         Consider using abstract classes if any of these statements applies:

o You want to share code among several closely related classes.

o You expect that classes that extend your abstract class have many common methods or fields, or require access modifiers other than public (such as protected and private).

o You want to declare non-static or non-final fields. This enables you to define methods that can access and modify the state of the object to which they belong.

·         Consider using interfaces if any of these statements applies:

o You expect that unrelated classes would implement your interface.

o You want to specify the behavior of a particular data type, but not concerned about who implements its behavior.

o You want to take advantage of multiple inheritance of type.

Use abstract classes when you want common behavior for same category classes.

Use interfaces when you want common behavior for different category classes.

In simple words,

When you want to develop some defined methods and some undefined methods as a common for multiple developers then use abstract class, otherwise if you want give only definition of methods for multiple developers as a common methods in such a way that according to their need they will implement those methods then use interface... In simple terms Abstract class contains some implemented methods and some unimplemented methods, where as interface contains only unimplemented methods....

Here are some guidelines on when to use an abstract class and when to use interfaces in Java programming:

·   An abstract class is good if you think you will plan on using inheritance since it provides a common base class implementation to derived classes.

·   An abstract class is also good if you want to be able to declare non-public members. In an interface, all methods must be public.

·   If you think you will need to add methods in the future, then an abstract class is a better choice. Because if you add new method headings to an interface, then all of the classes that already implement that interface will have to be changed to implement the new methods. That can be quite a hassle.

·  Interfaces are a good choice when you think that the API will not change for a while.

· Interfaces are also good when you want to have something similar to multiple inheritance, since you can implement multiple interfaces.

I think that interfaces should be used when we need to define a common behaviour which can have different variations of implementation, but abstract classes are used when we have some algorithmic steps/template for a behaviour that should be followed by all subclasses irrespective of each step implementation in the algorithm.
Interfaces are just the blueprints whereas abstract class include partial implementation. Obviously we can do our job without using interfaces and only using abstract classes but this will be bad practice because the code will NOT be modular.

Read more

Abstraction

Hey Guys, I am going to explain you a very basic and an important oops concept - Abstraction.

Abstraction in simple way or Abstraction in easy way can be said as Hiding . I have explained the whole abstraction concept with the help of abstract classes and abstraction examples.

Abstract classes -

What are the Abstract classes meant for?

The answer to my question is abstract classes are meant for 'abstracting' means if some classes are having common behavior, instead of writing every time the same thing in each class, write that in one class and ask the other classes to use it (by making the classes as sub classes to the abstract class). this is nothing but inheritance.

In simple words I would say - A class must be declared abstract when it has one or more abstract methods. So a class having no method can be declared as abstract or not ?? Think Think about it

or simply try in eclipse.

A method is declared abstract when it has a method heading, but no body – which means that an abstract method has no implementation code inside curly braces like normal methods do.

A non-abstract class is called a concrete class.

Now, the question arises - When to use abstract methods in java?

I would like to explain this by illustrating an example here -

/* the GeometricalFigure class must be declared as abstract

   because it contains an abstract method  */

public abstract class GeometricalFigure

{

        /* because this is an abstract method so the

       body will be blank  */

        public abstract float getArea();

}

public class Circle extends GeometricalFigure

{

        private float radius;

        public float getArea()

        {

                return (3.14 * (radius * 2));

        }

}

public class Rectangle extends GeometricalFigure

{

        private float length, width;

public float getArea(GeometricalFigure other)

        {

                return length * width;

        }

}

But one question you all would be thinking is as to why did I declare the getArea method to be abstract in the GeometricalFigure class? Well, what does the getArea method do? It returns the area of a specific shape. But, because the GeometricalFigure class isn’t a specific shape (like a Circle or a Rectangle), there’s really no definition we can give the getArea method inside the GeometricalFigure class. That’s why we declare the method and the GeometricalFigure class to be abstract. Any classes that derive from the GeometricalFigure class basically has 2 options: 1. The derived class must provide a definition for the getArea method OR 2. The derived class must be declared abstract itself.

In a nutshell, An abstract class is a class that is declared abstract—it may or may not include abstract methods. Abstract classes cannot be instantiated, but they can be subclassed.

When an abstract class is subclassed, the subclass usually provides implementations for all of the abstract methods in its parent class. However, if it does not, then the subclass must also be declared abstract.

With abstract classes, you can declare fields that are not static and final, and define public, protected, and private concrete methods.

Important points you all need to make a note of -

• An abstract class may have static fields and static methods.

• An abstract class can also have constructors and instance variables as well. It can have static or final instance variables as well.

• An abstract class may have static fields and static methods.

• An abstract class can also have constructors and instance variables as well. It can have static or final instance variables as well.

I would want like to give  an illustration on the concept of abstract classes and methods with the help of a basic self explanatory example ---->

You want to use an AbstractClass when although your sub-types have to implement some specific logic, you still have logic common to all sub-types like in this case:

public abstract class GeometricalShape

{

     private String name;

     private int  noOfEdges;

     protected GeometricalShape(name,noOfEdges)

**abstract methods

     public abstract GetArea();

      public abstract GetPerimeter();

**Concrete methods

      public GetName()

                                          {

return name;

}

     

public int GetNoOfEdges()

{

return noOfEdges;

}

}

In this example each geometric shape will have to implement specific logic regarding Area and Perimeter like before, but now all sub-types will share common methods for retrieving the name and no. of edges of the geometrical, which would be redundant to be defined in each and every sub-class.

Read more