Implementing a memoization mechanism using HashMap in Java

23 Oct 2023

References

In many programming scenarios, we may come across situations where a particular function or algorithm is called multiple times with the same input, and it can be time-consuming to recompute the result every time. Memoization is a technique that helps optimize such scenarios by caching the results of previous function calls and reusing them when the function is called again with the same input.

Java provides the HashMap class that can be used to implement a simple memoization mechanism. Let’s see how we can implement it.

Step 1: Create a HashMap

First, we need to create an instance of the HashMap class to store the results of function calls. Here’s how we can do it:

// Create a HashMap to store memoized results
HashMap<FunctionSignature, ReturnType> memo = new HashMap<>();

In the above code, FunctionSignature represents the signature of the function we want to memoize, and ReturnType represents the return type of the function.

Step 2: Define the Memoized Function

Next, we need to define the function that we want to memoize. For example, let’s consider a function fibonacci that calculates the nth Fibonacci number.

public int fibonacci(int n) {
    // Check if the result is already memoized
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    
    // If the result is not memoized, compute it
    int result;
    if (n < 2) {
        result = n; // Base case
    } else {
        result = fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
    }
    
    // Memoize the result
    memo.put(n, result);
    
    return result;
}

In the above code, we first check if the result for the input n is already memoized in the HashMap. If it is, we directly return the memoized result. Otherwise, we compute the result and memoize it by storing it in the HashMap.

Step 3: Test the Memoized Function

Now let’s test our memoized function to see if it indeed provides improved performance. Consider the following code snippet:

public static void main(String[] args) {
    MemoizationExample example = new MemoizationExample();
    
    // Test the memoized function
    long startTime = System.currentTimeMillis();
    int result = example.fibonacci(40); // Call the memoized function
    long endTime = System.currentTimeMillis();
    
    System.out.println("Result: " + result);
    System.out.println("Time taken: " + (endTime - startTime) + " ms");
}

In the above code, we calculate the 40th Fibonacci number using our memoized fibonacci function and measure the time taken. Compare the execution time with and without memoization to observe the improvement.

Conclusion

Memoization is a valuable technique that can significantly optimize the performance of functions that are called repeatedly with the same input. In this blog post, we demonstrated how to implement a simple memoization mechanism using the HashMap class in Java. By caching the results of previous function calls, we can avoid unnecessary re-computation and improve the overall performance of our code.

Remember to use memoization wisely, as it can consume additional memory depending on the number of unique function inputs.

#References