HashMap internal working in Java

What is HashMap? When do you use HashMap?

Start with common facts about HashMap like HashMap accept null while Hashtable doesn't, HashMap is not synchronized, HashMap is fast and it stores key and value pairs in form of Map.Entry. Below are some points you can mention:

• HashMap is implemented as a hash table, and there is no ordering on keys or values.
• LinkedHashMap preserves the insertion order so when we need order Map we use LinkedHashMap.
• Hashtable is synchronized, in contrast to HashMap but it is slow.

How HashMap works in Java or How does get () method of HashMap works ?

The answer to this question is HashMap works on principle of hashing, we have put(key, value) and get(key) method for storing and retrieving Objects from HashMap. When we pass Key and Value object  to put() method on Java HashMap, HashMap implementation calls hashCode method on Key object and applies returned hashcode into its own hashing function to find a bucket location for storing Entry object, main point to mention is that HashMap in Java stores both key and value object as Map.Entry in bucket which is essential to understand the retrieving logic.

Now next question is like What will happen if two different objects have same hashcode ?

Here you need to remind yourself about equals() and hashCode() contract  that two unequal object in Java can have same hash code. So don't say its not possible or something like that. Now the answer to this question is "Since hashcode is same, bucket location would be same and collision will occur in HashMap, Since HashMap use LinkedList to store object, this entry (object of Map.Entry comprise key and value )  will be stored in LinkedList.

You have answered that two keys can have same hashCode but how will you retrieve Value object  if two Keys will have same hashcode?

The normal answer to this question is we will call get() method and then HashMap uses Key Object's hashcode to find out bucket location and retrieves Value object. But here case is different we have same bucket location for two different objects, so you can explain about traversal in LinkedList until we find the value object. Here we already know map stores Key as well as Value in Map.Entry, so after finding bucket location, we will call key.equals() method to identify correct node in LinkedList starting from head of LinkedList until key.equals() method return true and return associated value object for that key in Java HashMap. Also, 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. Immutability 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 very good keys in Java HashMap.
Below is sample image to show how Map.Entry saved in LinkedList.

Here for all there objects HashCode is same and it is an example of collision. Now consider a situation where we want to get Object whoes key is K2. So first bucket location will be decided by Key K2. Now we travers LinkedList on this location, first call K2.equeals(K1) it will return false so it ensures that this is not the Object we are looking for. Next we will travers to next node of LinkedList and will call K2.equals(K2), it will return true. This ensures that this is the Object which is associated with this key K2 and we will return this value of this node.

Loadfactor and Rehashing in HashMap:

The default initial capacity (16) and the default load factor (0.75). You can change these values by using any of the below methods while initializing hashmap:

HashMap(int initialCapacity)
Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).

HashMap(int initialCapacity, float loadFactor)
Constructs an empty HashMap with the specified initial capacity and load factor.

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%. Similar to other collection classes like ArrayList,  Java HashMap re-size itself by creating a new bucket array of size twice of previous size of HashMap , and then start putting every old element into that new bucket array. This process is called rehashing because it also applies hash function to find new bucket location. 

Last but not least as we know hashmap is not synchronized is there any potential race condition exists while resizing HashMap in Java, if two thread at the same time found that now HashMap needs resizing and they both try to resizing.

Answer to this question is Yes, in 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.

Points to remember:

• String, Integer and other wrapper classes are natural candidates of HashMap key, and String is most frequently used key as well because String is immutable and final,and overrides equals and hashcode() method.

• If you want to use any Object as key in Java HashMap you need to make sure it follows equals and hashCode contract and its hashCode should not vary once the object is inserted into Map. If custom object is Immutable than this will be already taken care because you can not change it once created.

• In HashMap bucket is allocated by using modulus (%) function. The bucket location will be basically the output of (key % size of HashMap), default HashMap size is 16 so by default bucket location will be decided by output of (key%16).

Special question some may ask 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 null key?
There are two separate method 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.

Below is code snippet to retrieve Null key 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;
    }

So that was all I have to share with you guys on this thread.

Find Bug...Static Analysis solution to find bugs in code

What is Static Analysis ?

• Analyzes your program without executing it
• Doesn’t depend on having good test cases or even any test cases
• Generally, doesn’t know what your software is supposed to do
• Looks for violations of reasonable programming
• Shouldn’t throw NPE
• Shouldn’t allow SQL injection
• Not a replacement for testing
• Very good at finding problems on untested paths
• But many defects can’t be found with static analysis

Common Wisdom about Bugs and Static Analysis

• Programmers are smart. Smart people don’t make dumb mistakes

• We have good techniques (e.g., unit testing, pair programming, code inspections) for finding bugs early

• So, bugs remaining in production code must be subtle, and finding them must require sophisticated static analysis techniques

• I tried lint and it sucked: lots of warnings, few real issues

Can You Find The Bug?

if (listeners == null)

listeners.remove(listener);

• JDK1.6.0, b105, sun.awt.x11.XMSelection

• lines 243-244

Why Do Bugs Occur?

• Nobody is perfect

• Misunderstood language features, API methods

• Typos (using wrong boolean operator, forgetting parentheses or brackets, etc.)

• Misunderstood class or method invariants

• Everyone makes syntax errors, but the compiler catches them

• What about bugs one step removed from a syntax error?

This tutorial

• What FindBugs is and does

• Using FindBugs well and wisely

• Customizing FindBugs to your needs

• Adapting FindBugs to your time budget

• Find your sweet spot

• Making FindBugs part of your continuous build and test framework

Bug Categories

• Correctness - the code seems to be clearly doing something the developer did not intend

• Bad practice - the code violates good practice

• Dodgy code - the code is doing something unusual that may be incorrect

• Multithreaded correctness

• Potential performance problems

• Malicious code vulnerability

Students are good bug generators.

A student came to office hours, was having trouble with

his constructor:

/** Construct a WebSpider */

public WebSpider() {

WebSpider w = new WebSpider();

}

• A second student had the same bug

• Wrote a detector, found 3 other students with same bug Infinite recursive loop

Does this code contain a null pointer bug?

String s = null;

if (x > 0) s = “x”;

if (y > 0) s = “y”;

return s.hashCode();

Finding Null Pointer Bugs

•FindBugs looks for a statement or branch that, if executed, guarantees a null pointer exception

•Either a null pointer exception could be thrown, or the program contains a statement/branch that can’t be executed

•Could look for exceptions that only occur on a path e.g., if x <= 0 and y <= 0, then a NPE will be thrown but would need to worry about whether that path is feasible

•FindBugs doesn’t do this

Bad Method Invocation

• Methods whose return value shouldn't be ignored

• Strings are immutable, so functions like trim() and toLowerCase() return new String

• Dumb/useless methods

• Invoking toString or equals on an array

• Lots of specific rules about particular API methods

• Hard to memorize, easy to get wrong

Bad Practice

•A class that defines an equals method but inherits hashCode from Object

•Violates contract that any two equal objects have the same hash code equals method doesn't handle null argument

•Serializable class without a serialVersionUID

•Exception caught and ignored

•Broken out from the correctness category because I never want a developer to yawn when I show them a "correctness" bug Fixing hashCode

• What if you want to define equals, but don't think your objects will ever get put into a HashMap?

• Suggestion:

public int hashCode() {

assert false

: "hashCode method not designed";

return 42;

}

Dodgy code

• Dead local store - a value is stored into a local

variable, but that value is never used

• Use of non-short circuit boolean logic

• Switch statement fallthrough

• Branch where code on both branches is identical

Multithreaded correctness

• Inconsistent synchronization - a lock is held most of the time a field is accessed, but not always

• Problems with wait/notify - e.g., call to wait() not in loop

• Thread unsafe lazy initialization of static field

Performance

• Unused field

• Invocation of Boolean or Integer constructors

• Using hashCode or equals method on a URL

• final constant field that could be made static

• Loop with quadratic string concatenation

• Inner class that could be made static

Vunerability to Malicious code

• public static non-final fields

• public static final fields that reference mutable objects

• Methods that don’t defensively copy mutable arguments before storing them into fields

• Methods that don’t defensively copy mutable values

stored in fields before returning them

Eclipse IDE

FindBugs Eclipse plugin
http://findbugs.cs.umd.edu/eclipse/
Run FindBugs incrementally as you edit code
This is how it will look like when we scan a file using findbug:

If you see OutOfMemory error dialogs after starting FindBugs analysis in Eclipse, please increase JVM available memory: change eclipse.ini and add the lines below to the end of the file:

    -vmargs
    -Xmx1000m

Plugin for Maven

Add <plugin> to <reporting> section of pom.xml:

Update for pom.xml

<plugin>
<groupId>org.codehaus.mojo</groupId>
<artifactId>findbugs-maven-plugin</artifactId>
<version>1.1.1</version>
<configuration>
<xmlOutput>true|false</xmlOutput>
<xmlOutputDirectory>directory location of xml findbugs
report</xmlOutputDirectory>
<threshold>High|Normal|Low</threshold>
<effort>Min|Default|Max</effort>
</configuration>
</plugin>

Maven useful commands for finbug:

‘mvn findbugs:findbugs’ generates report
‘mvn site’ generates site files including a FindBugs report

Sample report:

Sources: findbugs-tutorials.googlecode.com

Java Best Practice

Avoid creating unnecessary objects and always prefer to do Lazy Initialization

Object creation in Java is one of the most expensive operation in terms of memory utilization and performance impact. It is thus advisable to create or initialize an object only when it is required in the code.

public class Countries { 

    private List countries;     

    public List getCountries() {         

        //initialize only when required

        if(null == countries) {

            countries = new ArrayList();

        }

        return countries;

    }

}

Avoid Reassigning Parameters

Reassigning values to parameters is a questionable practice. Use a temporary local variable instead or use only when required.
Here's an example of code that would trigger this rule:

public class Foo {
 private void foo(String bar) {
  bar = "something else";
 }
}

Loose Coupling

Avoid using implementation types (i.e., HashSet); use the interface (i.e, Set) instead.
Here's an example of code that would trigger this rule:

import java.util.*;
public class Bar {
 // Use List instead
 private ArrayList list = new ArrayList();
 // Use Set instead
 public HashSet getFoo() {
  returnnew HashSet();
 }
}

Null Assignment

Assigning a "null" to a variable (outside of its declaration) is usually bad form. Some times, the assignment is an indication that the programmer doesn't completely understand what is going on in the code.
NOTE: This sort of assignment may in rare cases be useful to encourage garbage collection. If that's what you're using it for, by all means, disregard this rule :-)
Here's an example of code that would trigger this rule:

 public class Foo {
   public void bar() {
     Object x = null; // This is OK.
     x = new Object();
     // Big, complex piece of code here.
     x = null; // This is BAD.
     // Big, complex piece of code here.
   }
 }

Never make an instance fields of class public

Making a class field public can cause lot of issues in a program. For instance you may have a class called MyCalender. This class contains an array of String weekdays. You may have assume that this array will always contain 7 names of weekdays. But as this array is public, it may be accessed by anyone. Someone by mistake also may change the value and insert a bug!

public class MyCalender {

     

    public String[] weekdays = 

        {"Sun", "Mon", "Tue", "Thu", "Fri", "Sat", "Sun"};

     

    //some code 

     

}

Best approach as many of you already know is to always make the field private and add a getter method to access the elements.

private String[] weekdays = 

    {"Sun", "Mon", "Tue", "Thu", "Fri", "Sat", "Sun"};

public String[] getWeekdays() {

    return weekdays;

}

But writing getter method does not exactly solve our problem. The array is still accessible. Best way to make it unmodifiable is to return a clone of array instead of array itself. Thus the getter method will be changed to.

public String[] getWeekdays() {

    return weekdays.clone();

}

Avoid Protected Field In Final Class

Do not use protected fields in final classes since they cannot be subclassed. Clarify your intent by using private or package access modifiers instead.
Here's an example of code that would violate this rule:

public final class Bar {
 private int x;
 protected int y;  // Bar cannot be subclassed, so is y really
                           // private or package visible???
 Bar() {}
}

Position Litera ls First In Comparisons

Position literals first in String comparisons - that way if the String is null you won't get a NullPointerException, it'll just return false.
Here's an example of code that would violatethis rule:

class Foo {
 boolean bar(String x) {
  return x.equals("2"); // should be "2".equals(x)
 }
}

Avoid Synchronized At Method Level

Method level synchronization can backfire when new code is added to the method. Block-level synchronization helps to ensure that only the code that needs synchronization gets it.
Here's an example of code that would violate this rule:

public class Foo {
 // Try to avoid this
 synchronized void foo() {
 }
 // Prefer this:
 void bar() {
  synchronized(this) {
  }
 }
}

Always try to minimize Mutability of a class

Making a class immutable is to make it unmodifiable. The information the class preserve will stay as it is through out the lifetime of the class. Immutable classes are simple, they are easy to manage. They are thread safe. They makes great building blocks for other objects.

However creating immutable objects can hit performance of an app. So always choose wisely if you want your class to be immutable or not. Always try to make a small class with less fields immutable.

To make a class immutable you can define its all constructors private and then create a public static method

to initialize and object and return it.

public class Employee {

    private String firstName;
    private String lastName;
   
    //private default constructor
    private Employee(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
   
    public static Employee valueOf (String firstName, String lastName) {
        return new Employee(firstName, lastName);
    }
}

Try to prefer Interfaces instead of Abstract classes

First you can not inherit multiple classes in Java but you can definitely implements multiple interfaces. Its very easy to change the implementation of an existing class and add implementation of one more interface rather then changing full hierarchy of class.

Again if you are 100% sure what methods an interface will have, then only start coding that interface. As it is very difficult to add a new method in an existing interface without breaking the code that has already implemented it. On contrary a new method can be easily added in Abstract class without breaking existing functionality.

Always try to limit the scope of Local variable

Local variables are great. But sometimes we may insert some bugs due to copy paste of old code. Minimizing the scope of a local variable makes code more readable, less error prone and also improves the maintainability of the code.

Thus, declare a variable only when needed just before its use.

Always initialize a local variable upon its declaration. If not possible at least make the local instance assigned null value.

Try to use standard library instead of writing your own from scratch

Writing code is fun. But “do not reinvent the wheel”. It is very advisable to use an existing standard library which is already tested, debugged and used by others. This not only improves the efficiency of programmer but also reduces chances of adding new bugs in your code. Also using a standard library makes code readable and maintainable.

For instance Google has just released a new library Google Collections that can be used if you want to add advance collection functionality in your code.

Wherever possible try to use Primitive types instead of Wrapper classes

Wrapper classes are great. But at same time they are slow. Primitive types are just values, whereas Wrapper classes are stores information about complete class.

Sometimes a programmer may add bug in the code by using wrapper due to oversight. For example, in below example:

int x = 10;

int y = 10;

Integer x1 = new Integer(10);

Integer y1 = new Integer(10);

System.out.println(x == y);

System.out.println(x1 == y1);

The first sop will print true whereas the second one will print false. The problem is when comparing two wrapper class objects we cant use == operator. It will compare the reference of object and not its actual value.

Also if you are using a wrapper class object then never forget to initialize it to a default value. As by default all wrapper class objects are initialized to null.

Boolean flag;

if(flag == true) {

    System.out.println("Flag is set");

} else {

    System.out.println("Flag is not set");

}

The above code will give a NullPointerException as it tries to box the values before comparing with true and as its null.

Use Strings with utmost care.

Always carefully use Strings in your code. A simple concatenation of strings can reduce performance of program. For example if we concatenate strings using + operator in a for loop then everytime + is used, it creates a new String object. This will affect both memory usage and performance time.

Also whenever you want to instantiate a String object, never use its constructor but always instantiate it directly. For example:

//slow instantiation

String slow = new String("Yet another string object");

//fast instantiation

String fast = "Yet another string object";

Use String Buffer For String Appends

Finds usages of += for appending strings.

Here's an example of code that would violate this rule:

Public class Foo {

 void bar() {

  String a;

  a = "foo";

  a += " bar";

  // better would be:

  // StringBuffer a = new StringBuffer("foo");

  // a.append(" bar);

 }

}

String Instantiation

Avoid instantiating String objects; this is usually unnecessary.

Here's an example of code that would violate this rule:   

public class Foo {

 private String bar = new String("bar"); // just do a String bar = "bar";

} 

Always return empty Collections and Arrays instead of null

Whenever your method is returning a collection element or an array, always make sure you return empty array/collection and not null. This will save a lot of if else testing for null elements. For instance in below example we have a getter method that returns employee name. If the name is null it simply return blank string “”.

public String getEmployeeName() {

    return (null==employeeName ? "": employeeName);

}

Defensive copies are savior

Defensive copies are the clone objects created to avoid mutation of an object. For example in below code we have defined a Student class which has a private field birth date that is initialized when the object is constructed.

public class Student {

    private Date birthDate;

     

    public Student(birthDate) {

        this.birthDate = birthDate;

    }

     

    public Date getBirthDate() {

        return this.birthDate;

    }

}

Now we may have some other code that uses the Student object.

public static void main(String []arg) {

    Date birthDate = new Date();

    Student student = new Student(birthDate);

    birthDate.setYear(2019);

     

    System.out.println(student.getBirthDate());

}

In above code we just created a Student object with some default birthdate. But then we changed the value of year of the birthdate. Thus when we print the birth date, its year was changed to 2019!

To avoid such cases, we can use Defensive copies mechanism. Change the constructor of Student class to following.

public Student(birthDate) {

    this.birthDate = new Date(birthDate);

}

This ensure we have another copy of birthdate that we use in Student class.

Never let exception come out of finally block

Finally blocks should never have code that throws exception. Always make sure finally clause does not throw exception. If you have some code in finally block that does throw exception, then log the exception properly and never let it come out :)

Never throw “Exception”

Never throw java.lang.Exception directly. It defeats the purpose of using checked Exceptions. Also there is no useful information getting conveyed in caller method.

Sources: https://sites.google.com/site/javatouch/javacode-bestpractices

Hit Subscribe by email if you like the post.

How to save credential in Tortoise GIT.

This is for those who have created long User Name & Password for GitHub and now each time you want to pull/push you need to fill up user name and password which consumes enough time in full day. Personaly it iretates me to enter user name and password more than 20 time in a single day. Then I found a way to save credentials in GIT as we do in SVN. Following are the steps to do so:

  

Step 1:

Right click on the Project clone àTortoiseGitàSetting  screen will look like below:

Step 2:

Select credential from Git:  Gitàcredential screen will look like:

Step 3:

Select “wincred-current windows user” from available option in Credential helper if you want to save User name as well as Password, if you want to save only User name Skip Step 3 go to Step 4. Click apply screen will look like:

Step 4:

NOTE: This step is only applicable if you want save only User name NOT password for Git.

Select “Advance” from available option in Credential helper.

Enter URL of clone URL(project specific git checkout/clone url).

Select “wincred” from Helper drop down.

Enter your git user name  in “Username” textbox.

Click on “Add New/Save” button. Screen will look like:

That’s all now you are ready to avoid entering User name/ password each time you Pull/Push.

Hit Subscribe by email if your purpose is solved.