Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article at OpenGenus, we will implement Hash Map in Java using OOP concepts and Generics.
Table of Contents
- Introduction
- Code Explanation
- Implementation
- Applications of HashMap
- Time Complexity of HashMap
Introduction
A HashMap in Java is a data structure that provides an efficient way to store and retrieve key-value pairs. It is part of the Java Collections Framework and is based on the concept of hashing. It allows constant-time performance for basic operations like insertion, retrieval, and deletion.
In a HashMap, each key is unique and associated with a value. The keys are used to calculate hash codes, which are then mapped to specific indexes in an array known as buckets. The values are stored at these indexes, allowing for quick access based on the key's hash code.
Implementing a HashMap with generics improves type safety, code reusability, readability, maintainability, and overall flexibility. It enables the HashMap to work with different data types while ensuring compile-time type safety and reducing the need for duplicate code.
Code Explanation
In this section, we will break down the building blocks of the code into smaller code snippets, provide detailed explanations for each part for better understanding and clarity.
Create the Entry class
// Entry class represents a key-value pair in the hash map
class Entry<K, V> {
private final K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
The Entry class represents a key-value pair in the hash map. It has generic type parameters K and V to accommodate different key and value types. The class has a private key field to store the key and a value field to store the associated value. Getter and setter methods are provided to access and modify the key and value.
Create the HashMap class
// HashMap class represents a hash map and provides various operations
class HashMap<K, V> {
private final int capacity;
private final LinkedList<Entry<K, V>>[] buckets;
public HashMap(int capacity) {
this.capacity = capacity;
this.buckets = new LinkedList[capacity];
}
The HashMap class represents the hash map and provides operations to manage key-value pairs. It is parameterized with generic types K and V to handle different key and value types. The class has a capacity field to store the capacity of the hash map (number of buckets) and an array of linked lists, buckets, to store the entries.
The constructor initializes the hash map with the specified capacity and creates an array of linked lists to hold the entries.
Create the getBucketIndex method
private int getBucketIndex(K key) {
int hashCode = key.hashCode();
return Math.abs(hashCode) % capacity;
}
The getBucketIndex method calculates the bucket index for a given key. It uses the key's hash code to determine the index within the array of buckets. The Math.abs() method is used to ensure a positive value, and the % operator is used to keep the index within the valid range of bucket indices.
The put method
public void put(K key, V value) {
int bucketIndex = getBucketIndex(key);
if (buckets[bucketIndex] == null) {
buckets[bucketIndex] = new LinkedList<>();
}
LinkedList<Entry<K, V>> bucket = buckets[bucketIndex];
for (Entry<K, V> entry : bucket) {
if (entry.getKey().equals(key)) {
entry.setValue(value);
return;
}
}
bucket.add(new Entry<>(key, value));
}
The put method inserts a key-value pair into the hash map. It calculates the bucket index using the getBucketIndex method. If the bucket at that index is null, it creates a new linked list to hold the entries.
The method then checks if the key already exists in the bucket. If found, it updates the value associated with the key. Otherwise, it creates a new Entry object with the given key and value and adds it to the bucket.
The get method
public V get(K key) {
int bucketIndex = getBucketIndex(key);
LinkedList<Entry<K, V>> bucket = buckets[bucketIndex];
if (bucket != null) {
for (Entry<K, V> entry : bucket) {
if (entry.getKey().equals(key)) {
return entry.getValue();
}
}
}
return null;
}
The get method retrieves the value associated with the given key from the hash map. It calculates the bucket index using getBucketIndex and retrieves the bucket at that index.
If the bucket exists, it iterates through the entries in the bucket and checks if the key matches. If a match is found, it returns the associated value. If no match is found or the bucket doesn't exist, it returns null.
The remove method
public void remove(K key) {
int bucketIndex = getBucketIndex(key);
LinkedList<Entry<K, V>> bucket = buckets[bucketIndex];
if (bucket != null) {
for (Entry<K, V> entry : bucket) {
if (entry.getKey().equals(key)) {
bucket.remove(entry);
return;
}
}
}
}
The remove method removes the key-value pair associated with the given key from the hash map. It calculates the bucket index using getBucketIndex and retrieves the bucket at that index.
If the bucket exists, it iterates through the entries in the bucket and checks if the key matches. If a match is found, it removes the entry from the bucket.
The Main method
// Example usage
public class Main {
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>(10);
hashMap.put("apple", 5);
hashMap.put("banana", 8);
hashMap.put("orange", 12);
System.out.println("Value associated with 'apple': " + hashMap.get("apple"));
hashMap.put("apple", 10);
System.out.println("Updated value associated with 'apple': " + hashMap.get("apple"));
hashMap.remove("banana");
System.out.println("Value associated with 'banana': " + hashMap.get("banana"));
}
}
In the example usage, we create an instance of HashMap with a capacity of 10. We then use the put method to add key-value pairs to the hash map. We retrieve values associated with specific keys using the get method and print them. The put method is used again to update the value associated with the key "apple". Finally, we remove the key-value pair associated with the key "banana" using the remove method.
Implementation
Here's a Java implementation of a hash map using object-oriented programming (OOP) concepts and generics:
import java.util.ArrayList;
import java.util.LinkedList;
// Entry class represents a key-value pair in the hash map
class Entry<K, V> {
private final K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
// HashMap class represents a hash map and provides various operations
class HashMap<K, V> {
private final int capacity;
private final LinkedList<Entry<K, V>>[] buckets;
public HashMap(int capacity) {
this.capacity = capacity;
this.buckets = new LinkedList[capacity];
}
private int getBucketIndex(K key) {
int hashCode = key.hashCode();
return Math.abs(hashCode) % capacity;
}
// Method to put a key-value pair into the hash map
public void put(K key, V value) {
int bucketIndex = getBucketIndex(key);
if (buckets[bucketIndex] == null) {
buckets[bucketIndex] = new LinkedList<>();
}
LinkedList<Entry<K, V>> bucket = buckets[bucketIndex];
for (Entry<K, V> entry : bucket) {
if (entry.getKey().equals(key)) {
entry.setValue(value);
return;
}
}
bucket.add(new Entry<>(key, value));
}
// Method to get the value associated with a key from the hash map
public V get(K key) {
int bucketIndex = getBucketIndex(key);
LinkedList<Entry<K, V>> bucket = buckets[bucketIndex];
if (bucket != null) {
for (Entry<K, V> entry : bucket) {
if (entry.getKey().equals(key)) {
return entry.getValue();
}
}
}
return null;
}
// Method to remove a key-value pair from the hash map
public void remove(K key) {
int bucketIndex = getBucketIndex(key);
LinkedList<Entry<K, V>> bucket = buckets[bucketIndex];
if (bucket != null) {
for (Entry<K, V> entry : bucket) {
if (entry.getKey().equals(key)) {
bucket.remove(entry);
return;
}
}
}
}
}
// Example usage
public class Main {
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>(10);
hashMap.put("apple", 5);
hashMap.put("banana", 8);
hashMap.put("orange", 12);
System.out.println("Value associated with 'apple': " + hashMap.get("apple"));
hashMap.put("apple", 10);
System.out.println("Updated value associated with 'apple': " + hashMap.get("apple"));
hashMap.remove("banana");
System.out.println("Value associated with 'banana': " + hashMap.get("banana"));
}
}
Applications of HashMap in Java:
-
Efficient Data Retrieval: HashMaps are commonly used to store and retrieve data based on unique keys. It provides a fast lookup mechanism to retrieve values associated with specific keys.
-
Caching: HashMaps are useful for caching frequently accessed data. The keys can be used to quickly check if a particular value is already stored, avoiding the need for expensive calculations or database queries.
-
Indexing: HashMaps can be utilized to create indexes for large datasets. The keys can represent attributes or properties of the data, allowing efficient lookup and retrieval.
Time Complexity of HashMap (in average case):
Insertion (put): O(1)
Retrieval (get): O(1)
Deletion (remove): O(1)
In the average case, HashMap operations have constant time complexity. However, in certain scenarios, such as a high number of collisions or a poorly designed hash function, the performance of HashMap operations can degrade to O(n) in the worst case. To maintain optimal performance, it is important to choose a good hash function, manage load factors, and handle collisions effectively.
Overall, HashMaps provide a powerful and efficient way to store and access key-value pairs, making them widely used in various applications, including caching, indexing, and efficient data retrieval.
With this article at OpenGenus, you have gained valuable knowledge on implementing Hash Map in Java using OOP concepts and Generics.
