Design Good Key for HashMap

View: 431    Dowload: 0   Comment: 0   Post by: hanhga   Category: Javascript   Fields: Other

A very popular interview question indeed. It is asked immediately after “How HashMap works?”. Lets make a reasoning around a good key class design.

The very basic need for designing a good key is that “we should be able to retrieve the value object back from the map without failure“, otherwise no matter how fancy data structure you build, it will be of no use. To decide that we have created a good key, we MUST know that “how HashMap works?”. I will leave, how hashmap works, part on you to read from linked post, but in summary it works on principle of Hashing.

Key’s hash code is used primarily in conjunction to its equals() method, for putting a key in map and then getting it back from map. So, our only focus point is these two methods. So if hash code of key object changes after we have put a key value pair in map, then its almost impossible to fetch the value object back from map. It is a case of memory leak.

On runtime, JVM computes hash code for each object and provide it on demand. When we modify an object’s state, JVM set a flag that object is modified and hash code must be AGAIN computed. So, next time you call object’s hashCode() method, JVM recalculate the hash code for that object.

For this basic reasoning, key objects are suggested to be IMMUTABLE. IMMUTABILITY allows you to get same hash code every time, for a key object. So it actually solves most of the problems in one go. Also, this class must honor the hashCode() and equals() methods contract.

This is the main reason why immutable classes like String, Integer or other wrapper classes are a good key object candidate.

But remember that immutability is recommended and not mandatory. If you want to make a mutable object as key in hashmap, then you have to make sure that state change for key object does not change the hash code of object. This can be done by overriding the hashCode() method. But, you must make sure you are honoring the contract with equals() also.

An example is always better for demonstration, right? Then lets have one

In this example, I have created an account class with only two fields for simplicity. I have overridden the hash code and equals method such that it uses only account number to verify the uniqueness of Account object. All other possible attributes of Account class can be changed on runtime.

package com.howtodoinjava.demo.map;
 
public class Account 
{
    private int accountNumber;
    private String holderName;
 
    public Account(int accountNumber) {
        this.accountNumber = accountNumber;
    }
 
    public String getHolderName() {
        return holderName;
    }
 
    public void setHolderName(String holderName) {
        this.holderName = holderName;
    }
 
    public int getAccountNumber() {
        return accountNumber;
    }
 
    //Depends only on account number
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + accountNumber;  
        return result;
    }
 
    //Compare only account numbers
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Account other = (Account) obj;
        if (accountNumber != other.accountNumber)
            return false;
        return true;
    }
 
}

Will this cause any undesired behavior???

NO, it will not. The reason is that Account class’s implementation honor the contract that “Equal objects must produce the same hash code as long as they are equal, however unequal objects need not produce distinct hash codes.” i.e.

1) Whenever a.equals(b) is true, then a.hashCode() must be same as b.hashCode().
2) Whenever a.equals(b) is false, then a.hashCode() may/may not be same as b.hashCode().

Lets test our Account class for above analysis.

package com.howtodoinjava.demo.map;
 
import java.util.HashMap;
 
public class TestMutableKey
{
    public static void main(String[] args)
    {
        //Create a HashMap with mutable key
        HashMap map = new HashMap();
          
        //Create key 1
        Account a1 = new Account(1);
        a1.setHolderName("A_ONE");
        //Create key 2
        Account a2 = new Account(2);
        a2.setHolderName("A_TWO");
          
        //Put mutable key and value in map
        map.put(a1, a1.getHolderName());
        map.put(a2, a2.getHolderName());
          
        //Change the keys state so hash map should be calculated again
        a1.setHolderName("Defaulter");
        a2.setHolderName("Bankrupt");
          
        //Success !! We are able to get back the values
        System.out.println(map.get(a1)); //Prints A_ONE
        System.out.println(map.get(a2)); //Prints A_TWO
          
        //Try with newly created key with same account number
        Account a3 = new Account(1);
        a3.setHolderName("A_THREE");
          
        //Success !! We are still able to get back the value for account number 1
        System.out.println(map.get(a3)); //Prints A_ONE
    }
}
 
Output:
 
A_ONE
A_TWO
A_ONE

This is my understanding on designing a key object for HashMap. If you disagree or feel otherwise, please drop me a comment.

Happy Learning !!

Design Good Key for HashMap

A very popular interview question indeed. It is asked immediately after “How HashMap works?”. Lets make a reasoning around a good key class design.

Posted on 27-07-2016 

Comment:

To comment you must be logged in members.

Files with category

  • Angular 6 Starter with Laravel 5.6 API Service

    Angular 6 Starter with Laravel 5.6 API Service

    View: 5    Download: 0   Comment: 0

    Category: Javascript     Fields: none

    Angular 6 and Laravel 5.6 This project is a starter for creating interface with Angular using bootstrap && css && sass and using Laravel 5.6 for api requests. Demo Installation This project is divided in two parts (projects) and before use them you...

  • Simple Richtext Editor Based on pellJS

    Simple Richtext Editor Based on pellJS

    View: 5    Download: 0   Comment: 0

    Category: Javascript     Fields: none

    A simple visual editor for websites using the pell javascipt. It also has the option to switch between visual editor mode and source code mode. I will upload an update for new functionality soon. Source Code Editor Visual Editor

  • Data Visualization for BI: How to Design Layouts for .NET Financial Reports

    Data Visualization for BI: How to Design Layouts for .NET Financial Reports

    View: 15    Download: 0   Comment: 0

    Category: Javascript     Fields: Other

    With the Active Reports Server, you can have a multi-tenant environment where users from various departments, companies, or other specifications can log in, view their reports (and only their reports), export the data, or set up a distribution...

  • AngularJS and REST API

    AngularJS and REST API

    View: 179    Download: 0   Comment: 0

    Category: Javascript     Fields: Other

    This is a tutorial for those interested in a quick introduction to AngularJS and REST API. We will build the familiar Periodic Table of the Elements found in every chemistry textbook, and allow the user to select a Chemical Element by clicking on...

  • Collective Intelligence, Recommending Items Based on Similar Users' Taste

    Collective Intelligence, Recommending Items Based on Similar Users' Taste

    View: 143    Download: 0   Comment: 0

    Category: Javascript     Fields: Other

    Using Collaborative Filtering to find people who share tastes, and for making automatic recommendations based on things that other people like.

  • Think Like a Bird for Better Parallel Programming

    Think Like a Bird for Better Parallel Programming

    View: 134    Download: 0   Comment: 0

    Category: Javascript     Fields: Other

    Coding an application to run in parallel is hard, right? I mean, it must be hard or we’d see parallel programs everywhere. All we'd see are slick parallel apps that use every available core effortlessly. Instead multi-threaded apps are the exception...

  • Getting Started with the Bing Search APIs

    Getting Started with the Bing Search APIs

    View: 140    Download: 0   Comment: 0

    Category: Javascript     Fields: Other

    Bing Search API is a set of REST interfaces that find web pages, news, images, videos, entities, related searches, spelling corrections, and more in response to queries from any programming language that can generate a web request. Applications that...

  • Brief Introduction of SocketPro High Performance and Scalable Persistent Message Queue

    Brief Introduction of SocketPro High Performance and Scalable Persistent Message Queue

    View: 458    Download: 0   Comment: 0

    Category: Javascript     Fields: Other

    Continuous in-line request/result batching, real-time stream sending/processing, asynchronous data transferring and parallel computation for best performance and scalability

 
File suggestion for you
File top downloads
Codetitle - library source code to share, download the file to the community
Copyright © 2018. All rights reserved. codetitle Develope by Vinagon .Ltd