DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Last call! Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Generics in Java and Their Implementation
  • Java String: A Complete Guide With Examples
  • Effective Java Collection Framework: Best Practices and Tips
  • Speeding Up Large Collections Processing in Java

Trending

  • Medallion Architecture: Why You Need It and How To Implement It With ClickHouse
  • Is Agile Right for Every Project? When To Use It and When To Avoid It
  • Automatic Code Transformation With OpenRewrite
  • Automating Data Pipelines: Generating PySpark and SQL Jobs With LLMs in Cloudera
  1. DZone
  2. Coding
  3. Languages
  4. HashMap Custom implementation in java

HashMap Custom implementation in java

By 
Ankit Mittal user avatar
Ankit Mittal
·
May. 13, 15 · Interview
Likes (10)
Comment
Save
Tweet
Share
74.2K Views

Join the DZone community and get the full member experience.

Join For Free
Contents of page :
  • Custom HashMap >
  • Entry<K,V>
  • Putting 5 key-value pairs in HashMap  (step-by-step)>
  • Methods used in custom HashMap >
  • What will happen if map already contains mapping for key?
  • Complexity calculation of put and get methods in HashMap >
    • put method - worst Case complexity >
    • put method - best Case complexity >
    • get method - worst Case complexity >
    • get method - best Case complexity >
  • Summary of complexity of methods in HashMap >



Custom HashMap >
This is very important and trending topic. In this post i will be explaining HashMap custom implementation in lots of detail with diagrams which will help you in visualizing the HashMap implementation.
I will be explaining how we will put and get key-value pair in HashMap by overriding-
>equals method - helps in checking equality of entry objects.
>hashCode method - helps in finding bucket’s index on which data will be stored.
We will maintain bucket (ArrayList) which will store Entry (LinkedList).
Entry<K,V>
We store key-value pair by usingEntry<K,V>
Entry contains
  • K key,
  • V value and
  • Entry<K,V>next  (i.e. next entry on that location of bucket).
static class Entry<K, V> {
   K key;
   V value;
   Entry<K,V> next;
   
   public Entry(K key, V value, Entry<K,V> next){
   this.key = key;
   this.value = value;
   this.next = next;
   }
 }

Putting 5 key-value pairs in custom HashMap (step-by-step)>
I will explain you the whole concept of HashMap by putting 5 key-value pairs in HashMap.
Initially, we have bucket of capacity=4. (all indexes of bucket i.e. 0,1,2,3 are pointing to null)

Let’s put first key-value pair in HashMap-
Key=21, value=12
newEntry Object will be formed like this >
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 21%4= 1.
So, 1 will be the index of bucket on which newEntry object will be stored.
We will go to 1stindex as it is pointing to null we will put our newEntry object there.


At completion of this step, our HashMap will look like this-


Let’s put second key-value pair in HashMap-
Key=25, value=121
newEntry Object will be formed like this >
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 25%4= 1.
So, 1 will be the index of bucket on which newEntry object will be stored.
We will go to 1st index, it contains entry with key=21, we will compare two keys(i.e. compare 21 with 25 by using equals method), as two keys are different we check whether entry with key=21’s next is null or not, if next is null we will put our newEntry objecton next.
At completion of this step our HashMap will look like this-


Let’s put third key-value pair in HashMap-
Key=30, value=151
newEntry Object will be formed like this >
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 30%4= 2.
So, 2 will be the index of bucket on which newEntry object will be stored.
We will go to 2nd index as it is pointing to null we will put our newEntry object there.
At completion of this step, our HashMap will look like this-


Let’s put fourth key-value pair in HashMap-
Key=33, value=15
Entry Object will be formed like this >
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 33%4= 1,
So, 1 will be the index of bucket on whichnewEntry object will be stored.
We will go to 1st index -
>it contains entry with key=21, we will compare two keys (i.e. compare 21 with 33 by using equals method, as two keys are different,  proceed to next  of entry with key=21 (proceed only if next is not null).
>now, next contains entry with key=25, we will compare two keys (i.e. compare 25 with 33 by using equals method, as two keys are different,  now next of entry with key=25 is pointing to null so we won’t proceed further, we will put our newEntry object on next.
At completion of this step our HashMap will look like this-


Let’s put fifth key-value pair in HashMap-
Key=35, value=89
Repeat above mentioned steps.
At completion of this step our HashMap will look like this-

Must read: LinkedHashMap Custom implementation
Methods used in custom HashMap >
public void put(K newKey, V data)
-Method allows you put key-value pair in HashMap
-If the map already contains a mapping for the key, the old value is replaced.
-provide complete functionality how to override equals method.
-provide complete functionality how to override hashCode method.
public V get(K key)
Method returns value corresponding to key.
public boolean remove(K deleteKey)
Method removes key-value pair from HashMapCustom.
public void display()
-Method displays all key-value pairs present in HashMapCustom.,
-insertion order is not guaranteed, for maintaining insertion order refer LinkedHashMapCustom.
private int hash(K key)
-Method implements hashing functionality, which helps in finding the appropriate bucket location to store our data.
-This is very important method, as performance of HashMapCustom is very much dependent on  this method's implementation.


What will happen if map already contains mapping for key?
If the map already contains a mapping for the key, the old value is replaced.


Complexity calculation of put and get methods in HashMap >


put method - worst Case complexity >
O(n).
But how complexity is O(n)?
Initially, let's say map is like this -
And we have to insert newEntry Object with Key=25, value=121
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 25%4= 1.
So, 1 will be the index of bucket on which newEntry object will be stored.
We will go to 1st index, it contains entry with key=21, we will compare two keys(i.e. compare 21 with 25 by using equals method), as two keys are different we check whether entry with key=21’s next is null or not, if next is null we will put our newEntry objecton next.
At completion of this step our HashMap will look like this-

Now let’s do complexity calculation -

Earlier there was 1 element in HashMap and for putting newEntry Object we iterated on it. Hence complexity was O(n).
Note: We may calculate complexity by adding more elements in HashMap as well, but to keep explanation simple i kept less elements in HashMap.


put method - best Case complexity >
O(1).

But how complexity is O(n)?
Let's say map is like this -
And we have to insert newEntry Object with Key=30, value=151
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 30%4= 2.
So, 2 will be the index of bucket on which newEntry object will be stored.
We will go to 2nd index as it is pointing to null we will put our newEntry object there.
At completion of this step our HashMap will look like this-
Now let’s do complexity calculation -
Earlier there 2 elements in HashMap but we were able to put newEntry Object in first go. Hence complexity was O(1).



get method - worst Case complexity >
O(n).
But how complexity is O(n)?
Initially, let's say map is like this -
And we have to get Entry Object with Key=25, value=121
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 25%4= 1.
So, 1 will be the index of bucket on which Entry object is stored.
We will go to 1st index, it contains entry with key=21, we will compare two keys(i.e. compare 21 with 25 by using equals method), as two keys are different we check whether entry with key=21’s next is null or not,  next is not null so we will repeat same process and ultimately will be able to get Entry object.

Now let’s do complexity calculation -
There were 2 elements in HashMap and for getting Entry Object we iterated on both of them. Hence complexity was O(n).
Note: We may calculate complexity by using HashMap of larger size, but to keep explanation simple i kept less elements in HashMap.

get method - best Case complexity >
O(1).
But how complexity is O(n)?
Initially, let's say map is like this -
And we have to get Entry Object with Key=30, value=151
We will calculate hash by using our hash(K key) method - in this case it returns
key/capacity= 30%4= 2.
So, 2 will be the index of bucket on which Entry object is stored.
We will go to 2nd index and get Entry object.
Now let’s do complexity calculation -
There were 3 elements in HashMap but we were able to get Entry Object in first go.
Hence complexity was O(1).


Summary of complexity of methods in HashMap >
Operation/ method
Worst case
Best case
put(K key, V value)
O(n)
O(1)
get(Object key)
O(n)
O(1)

REFER: http://javamadesoeasy.com/2015/02/hashmap-custom-implementation.html
HashMap Custom implementation - put, get, remove Employee object.
Data structure Object (computer science) Implementation Java (programming language)

Opinions expressed by DZone contributors are their own.

Related

  • Generics in Java and Their Implementation
  • Java String: A Complete Guide With Examples
  • Effective Java Collection Framework: Best Practices and Tips
  • Speeding Up Large Collections Processing in Java

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!