Skip to main content

HashMap Internal

I always wanted to implement the logic behind the famous data structure of Java, HashMap and here it comes. Though it’s not the complete implementation considering all optimization scenarios, but it will highlight the basic algorithm behind the HashMap.

So let’s start, this implementation will use my LinkedList implementation (Reason: for this implementation I thought to write everything from the scratch apart from primitive data types. Sounds weird? May be ;-) ). You may refer my earlier post on LinkedList, as I’m going to use it.

HashMap is a key-value pair data structure, where you retrieve value by passing key. To optimize the search of key, a concept of Bucket (an Array of Java Objects) has been introduced. This is used, so that if search hits this Bucket, corresponding value element is instantly retrieved, otherwise it iterates sequentially through the Linked List associated with each Bucket element. So you can say if all HashMap elements get fit into the Bucket, retrieving elements back, will be super fast and this is the Best Case. But that also means you are keeping everything in an array which is not good in-terms of heap memory storage limitation. So we need to consider both the things Bucket and LinkedList. This is really interesting, so let me know, if you guys want to discuss more on this.

To make sure that all Key_Index (Hashcode of Key Object, calculated by calling Object’s hashCode method) becomes less than Bucket_Size, we will do the mod operation i.e.

Key_Index = key.hashCode() % Bucket_Size

This returns integer value which is always less than Bucket_Size. If multiple key Objects return same Key_Index, then all matching keys will be stored in the associated LinkedList of the Bucket element. So if the bucket size is 10, following figure depicts the behavior of element entry into HashMap-


K0, K1 etc. are elements stored in the bucket, where as V0, V1, etc. are elements stored in LinkedList of corresponding bucket elements. So, 3 elements stored in K0’s LinkedList, 1 element stored in K1’s LinkedList.

Structure of HashMap Node Object

import com.ds.link.LinkedList;

public class HashNode {

      /**
       * HashMap Key
       */
      Object key;
      /**
       * HashMap Value
       */
      Object value;
      /**
       * List of HashMap nodes which doesn't get fit into bucket
       */
      LinkedList list;
     
      /**
       * by default the list will be null
       */
      public void initList(){
            if(list == null)
                  list = new LinkedList();
      }
}

MyHashMap.java
First thing first, define the Bucket (an Object Array)

final int bucket_size = 10;
Object[] bucket;
/**
  * @param bucket_size- custom bucket size
  */
public MyHashMap(int bucket_size){
      this.bucket_size = bucket_size;
      bucket = new Object[bucket_size];
}
     
/**
  * default bucket_size
  */
public MyHashMap(){
      bucket = new Object[bucket_size];
}

Add Element

/**
  * Add key, value pair in the HashMap
  * @param key
  * @param value
  */
public void add(Object key, Object value){
      int kCode = key.hashCode();
      int index = kCode % bucket_size;
      System.out.println("->"+ index);
           
      if(bucket[index] == null){
            System.out.println("First entry in Bucket: Key="+ key);
            HashNode node = new HashNode();
            node.key = key;
            node.value = value;
            bucket[index] = node;
      }
      else{
            // value already exists, so add this element into LinkedList
            HashNode node = (HashNode)bucket[index];
            System.out.println("Add into List of: "+ node.key +" Key="+ key);
            // initiate the list
            node.initList();
            HashNode newNode = new HashNode();
            newNode.key = key;
            newNode.value = value;
            // add the new element into list
            node.list.addToEnd(newNode);
      }
}

Get Element

/**
  * If the key is not present, it will return null
  * @param key
  * @return
  */
public Object get(Object key){
           
      int index = key.hashCode() % bucket_size;
      System.out.println("Searching for Bucket Index: "+ index);
      if(index >= bucket.length)
            new ArrayIndexOutOfBoundsException("Invalid Attempt: Index="+ index);
           
      HashNode node = (HashNode)bucket[index];
           
      if(node == null){
            // At this position, there is no node in the bucket
            return null;
      }
           
      if(node.key.hashCode() == key.hashCode()){
            // element is found in the bucket
            System.out.println("1st Level Match....");
            return node.value;
      }
           
      // unable to find in the element in the bucket
      // find in the associated list
      LinkedList list = node.list;
           
      if(list == null){
            System.out.println("No associated list");
            return null;
      }
           
      // pointer to the root node of the linkedlist
      Node first = list.getFirst();
           
      while(true){
            if(first == null)
                  break;
            HashNode hn = (HashNode)first.data;
            if(key.hashCode() == hn.key.hashCode()){
                  System.out.println("2nd Level Match Found...");
                  return hn.value;
            }
            first = first.pointer;
      }
           
      // still unable to find the element
      System.out.println("Failed to hit bulls eye!! No match found");
      return null;
}
Share your comments, I'm listening. For more on my open source work, visit Git Hub

Comments

  1. Hi Prasanta,

    Nice effort to understand the working of a HashMap.

    Just to add on to the above algorithm :

    Java HashMap supports null keys, and null doesn't have a hash code

    So to deal with it and prevent NPE, it just defaults to 0th index if key is null.
    That means whenever key is null..bucket 0 is selected and the node is added to the corresponding list.
    Similarly while fetching the value of null key , bucket 0 is searched for node whose key is null.

    ~Sachin

    ReplyDelete
  2. Very Nice Prasanta.
    I have 2 observations.
    bucket_size can not be final & in the add method
    node.initList() should be done following a null check .
    if(node.list == null){ node.initList() }

    ReplyDelete
  3. Wonderful, too good !

    ReplyDelete
  4. Thanks, it was helpful, Could you add details on Resizing and Race conditions too ?

    ReplyDelete
  5. Excellent explanation,I am still confuse how it handles null key and why we require to add this feature

    ReplyDelete
  6. Nice explanation. Keep sharing about collections and Threads. Thanks in advance

    ReplyDelete
  7. Awesome...!

    By
    Vasan Rajendran

    ReplyDelete
  8. Good Explanation and thanks!
    but i am confused in the following code of lines:
    if(node.key.hashCode() == key.hashCode()){
    // element is found in the bucket
    System.out.println("1st Level Match....");
    return node.value;
    }

    Here we are just matching the key hashcode and according to that we are returning value but If more that one keys returned the same hashcode then then what will be returned/

    For example if our key was AB and hascode return its length that is bucket is 2 now suppose if we search with key CD then again hashcode is 2 and according to above line of code it will return the value of associated with key AB.

    Please let me know

    ReplyDelete
  9. Nice One...
    But 1 Observation in 2nd Level Match in place of
    if(key.hashCode() == hn.key.hashCode()){ It should be
    if(key.equals(hn.key)){}

    Please correct me if I am wrong

    Thanks

    ReplyDelete
  10. nice explanation

    ReplyDelete
  11. your above mentioned linkedList link is not working.. kindly check and let us know the exact URL for your linkedList post

    ReplyDelete
  12. I have changed the URL. Pls check-
    http://prasanta-paul.blogspot.in/2010/06/linkedlist-in-java.html

    BR,
    Prasanta

    ReplyDelete

Post a Comment

Popular posts from this blog

Android Parcelable Example

Few days back I had a requirement to send a ArrayList of my Custom Class Objects through Android Intent , I guess most of you also find this requirement now and then. I never thought it can be that tricky. There are built in functions in Intent to send ArrayList of primitive objects e.g. String, Integer, but when it comes to Custom Data Handling Objects, BOOM … you need to take that extra pain! Android has defined a new light weight IPC ( Inter Process Communication ) data structure called Parcel , where you can flatten your objects in byte stream, same as J2SDK’s Serialization concept. So let’s come back to my original requirement, I had a Data Handling class, which groups together a set of information- public class ParcelData {       int id;       String name;       String desc;       String[] cities = {"suwon", "delhi"}; } I want an ArrayList<ParcelData> of Data Handling objec...

Call Control in Android

This tutorial is for those who want to control Phone Call in Android OS. Programmatic approach to Accept or Reject call without user intervention. Kindly note, this approach uses Java Reflection to call methods of an internal class of Android Telephony Framework and might not work with all versions of Android OS. The core concept has been explained in this Android open code . 1st thing 1st, Give the permission . You need to define 3 User Permissions to handle call related functionality- android.permission.READ_PHONE_STATE android.permission.MODIFY_PHONE_STATE (For answerRingingCall() method) android.permission.CALL_PHONE (For endCall() method) Define a Receiver... Create a Receiver which accepts broadcasts with intent action android.intent.action.PHONE_STATE, define following in the Manifest- [receiver android:name=".PhoneCall"]         [intent-filter]             [action android:name="android.in...

Android Looper and Toast from WorkerThread

Have you ever tried to launch Android Toast message from worker thread? Probably you are wondering why the heck it is giving this error- java.lang.RuntimeException: Can't create handler inside thread that has not called Looper.prepare() In this article we are going to explore reason behind the above exception and try to understand how Looper works in Android. At the end, I am going to explain one approach to run Toast from a worker thread, but before that we need to understand how Looper works. If you already know in/out of Looper, you can skip below section and directly move to the solution part. Looper is a very basic wrapper class which attach a MessageQueue to a Thread and manage this queue. MessageQueue is a structure to sequentialize simultaneous processing requests of a Thread.  In Android, message/request processing classes like Handler uses Looper to manage their respective MessageQueue. Looper = Thread + MessageQueue Android Looper Life Cycle: As you can see in the abo...

Overlay on Android Layout

This will help you to create custom Layout and add Overlay on a LinearLayout. The concept can be reused on other Layout classes i.e. RelativeLayout, FrameLayout etc. I have added a popup Selection Palette, containing "Map Pin" and "List" icons. You can minimize the popup by clicking on the section in Green on the left side bottom corner of the screen.   How can I do that- You need to follow 4 steps- 1. Override LinearLayout Create a Class MyLinearLayout.java which should overwrite LinearLayout 2. Drawing You need to overwrite dispatchDraw (Canvas canvas) method. It gives control to the whole screen. Make sure you set android:layout_height="fill_parent" for the associated layout definition in XML. You can draw anything and anywhere on the canvas. dispatchDraw (Canvas canvas) gets called only after underlying views are drawn, so whatever you draw comes in the foreground.   3. Event Handling You need to overwrite dispatchTouchEvent (MotionEvent e...

Android Custom TextView

Have you ever tried to add custom behavior to in-build Android Text View or create custom attributes? If yes, this article is going to help you. Here we'll create Single Custom TextView with support for custom attributes to display First and Last Name in different font and colors. During this process we'll learn following topics- 1. How to override default Views in Android 2. How to define custom Layout Attributes in Android So, Let's get started... Following sections explains necessary changes required in Java code and XML layout files. Create Custom Text View (MyTextView.java) 1. Override Android's default TextView   2. Implement Constructors. If you want custom attributes, override Constructor having Attributes in argument. 3. Override onMeasure(): Calculate required width and height, based on Text Size and selected Font. Once calculation is complete, set updated measure using setMeasuredDimension (reqWidth, reqHeight) Note: It’s really important to define the corr...

Google SpreadSheet Library for Android

You might have already tried using Google's GData Lib to access SpreadSheet from Android, and after few hours of try, you start Google for any alternate solution. I have also spent number of hours without any solution. So, I have developed SpreadSheet client Lib [ works on Android :-) ] and ideally work on any Java platform- http://code.google.com/p/google-spreadsheet-lib-android/ Latest version: 2.1 (Added support for List Feed. Please visit above link to get more info.) Supported Features: 1. Create/Delete Spreadsheet 2. List all stored Spreadsheets 3. Add/Delete WorkSheet into/from a given SpreadSheet 4. List all Worksheets of a given Spreadsheet 5. Add Records into WorkSheet/SpreadSheet (It supports Table based record handling) 6. Retrieve Record from WorkSheet/SpreadSheet ( Structured Query support) 7. Retrieve Record as List Feed from Worksheet 8. Update/Delete Records 9. Share ShreadSheet with user/group/domain. 10. Conditional data retrieval- ...

Android Fragment

Fragment is being hanging out since Andriod 3.0, but with the release of 4.0, it has become an obvious choice for Android Application development for both Tabs and Smart phones. Few people think, fragment is a " Superman " which can add any kind of UI layout/style/decoration. But that is not true, rather than being an UI layout or decoration enhancer, Fragment is a very important concept to manage segments of your UI component code base . Prior to Fragment, developers were able manage UI flow only at the Activity level. All UI components were Views (mentioned in XML layout and part of Activity) and there was no way to manage these components separately. As a result all view management code were in a single file i.e. Activity class. With fragment approach, we can now remove View management code from Activity and place them in their respective Java classes. So, a pretty neat approach for code management. Here I'll explain various concepts of Fragment with an example appli...

Accessing Yahoo Finance API

Since last few days I was wondering the right set of Web Service to read Country wise Stock Exchange index information . I found a bunch of scattered information, but no straight forward answer. It seems there are not many "reliable" and "flexible" options and Yahoo Finance is one of the top of this class. Though Yahoo Finance is very powerful, some how its very less documented and it seems Yahoo doesn't care much about this wonderful web service and expect Developers to do some kind of "hacking". The only online resource that I (and most of you as well ) found is one 3rd party web site- http://www.gummy-stuff.org/Yahoo-data.htm and it seems they know much more than what Yahoo dose..;-) Anyway let me continue and share my experience and information to help budding developer who wants to use Yahoo Finance Web Service in their Mobile, Web o r Desktop s olution. There are 2 set of APIs to access Yahoo Finance details- YQL based Web Service : Th...

Eclipse EGIT, Download Code, Attach Framework code & Debug

This article explains procedure to download Android source (few important Apps and Framework base code) using Eclipse EGit plugin and then attach framework code to debug important framework classes (e.g. Activity etc.). Install EGit Download Source from GIT Repository Attach Framework code Debug Download EGit Plug-in EGit is a GIT plugin for Eclipse which helps to mange GIT clone, Check-ins, Sync etc. from your Eclipse workspace. Eclipse (Version: 3.7.x) -> Help -> Install New Software -> "Add" - " http://download.eclipse.org/egit/updates ". Once the plug-in installation is successful, you'll find a new Eclipse View perspective- "Git Repository Exploring"    Download Android source To download code from Android GIT repository, we need to create "local Git clone". Each local clone is associated with Remote Clone URL.   https://android.googlesource.com/ lists Git Repository URLs for different sections of An...