Hash Maps in Java

Hash Tables, better known as Hash Maps, are just collections of key-value pairs. In other words, they are pieces of data (values) mapped to unique identifiers called properties (keys).

Hash Maps were designed to give us a way of, given a key, associating a value with it for very quick lookups.

In Java, the Hash Map is implemented as a HashMap

Creation:

You create an empty Hash Map by declaring an Map<keyType, valueType> and initializing it with using new HashMap<>(), where the keyType and valueType are the data types of the keys and values.

Let's declare a Hash Map that maps text values represing digits to their numerical value (e.g. "two" => 2). We wil map strings to integers, so the two types are String and Integer. We will name the map digitValue

Map<String, Integer> digitValue = new HashMap<>();

Creating an empty dictionary takes O(1) time.

Initialization:

You can also add some key-value pairs in your dictionary at creation:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};

Accessing values:

A value is retrieved from a map using the get() method:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};

// Accesing values:
digitValue.get("zero"); // returns  0

digitValue.get("one"); //  returns 1

digitValue.get("three"); // raises an exception since 'three' does not exist

digitValue.getOrDefault("three", 0); // returns 0 as the default value

As you can see, if you refer to a key that is not in the map, Java raises an exception. We can use getOrDefault to specify a default value in case it does not exist

Accessing a value from a map takes O(1) time.

Adding an entry:

We can add a key / value pair by using the put() method as follows:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};

// Adding new entries:
digitValue.put("three", 3);

//The new Hash Map:
// {
//	"zero": 0,
//  "one":  1,
//	"three": 3
//}

Adding a new entry to a map takes O(1) time.

Updating an entry:

We can update an existing entry by using the put() method as follows:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};

// updating entries:
digitValue.put("zero", 5);

//the new hash map:
// {
//	"zero": 5,
//  "one":  1
//}

Updating an entry from a map takes O(1) time.

Deleting entries:

The remove() method allows you to remove a key from a map:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};

// removing entries:
digitValue.remove("zero");

//the new hash map:
// {
//  "one":  1
//}

If you try to delete a key that is not in the map, it won't do anything.

Deleting an entry from a map takes O(1) time.

Checking if a key exists:

You can check if a key exists in a map using the containsKey() method:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};


digitValue.containsKey("zero"); // returns true since the key exists

digitValue.containsKey("three"); // returns false since the key does not exist

Checking if a key exists in the map is O(1) time.

Iterating over the map keys:

If we want to iterate over keys of the map, we can use the for loop along with the : operator and the keySet() method as follows:

Map<String, Integer> digitValue = new HashMap<>() {{
    put("zero", 0);
    put("one", 1);
}};

for (String key : digitValue.keySet()) {
    System.out.println(key + " is " + digitValue.get(key));
}

// This will print:
// one is 1
// zero is 0

Notice the order is not the same as initiated. HashMap keeps the data in random order

Iterating over a dictionary takes O(n) time.

Assignment
Follow the Coding Tutorial and let's play with some dictionaries.

Hint
Look at the examples above if you get stuck.

Introduction

In this lesson, we will explore the concept of Hash Maps in Java. Hash Maps are a fundamental data structure that allows for efficient storage and retrieval of key-value pairs. They are widely used in various applications, such as caching, indexing, and associative arrays. Understanding how to use Hash Maps effectively can significantly improve the performance of your programs.

Understanding the Basics

Hash Maps, also known as Hash Tables, are collections of key-value pairs. Each key is unique and maps to a specific value. The primary advantage of Hash Maps is their ability to provide constant-time complexity (O(1)) for basic operations like insertion, deletion, and lookup. This efficiency makes them ideal for scenarios where quick data retrieval is essential.

Let's start with a simple example to illustrate the basic concepts:

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // Creating a HashMap
        Map<String, Integer> digitValue = new HashMap<>();
        
        // Adding key-value pairs
        digitValue.put("zero", 0);
        digitValue.put("one", 1);
        
        // Accessing values
        System.out.println("Value for 'zero': " + digitValue.get("zero")); // Output: 0
        System.out.println("Value for 'one': " + digitValue.get("one"));   // Output: 1
    }
}

Main Concepts

Now that we understand the basics, let's delve into the main concepts and techniques involved in using Hash Maps:

Creation: Initializing an empty Hash Map.
Initialization: Adding key-value pairs during creation.
Accessing Values: Retrieving values using keys.
Adding Entries: Adding new key-value pairs.
Updating Entries: Modifying existing key-value pairs.
Deleting Entries: Removing key-value pairs.
Checking Key Existence: Verifying if a key exists.
Iterating Over Keys: Looping through all keys in the map.

Examples and Use Cases

Let's explore some examples and real-world use cases to demonstrate the versatility of Hash Maps:

import java.util.HashMap;
import java.util.Map;

public class HashMapUseCases {
    public static void main(String[] args) {
        // Example 1: Counting word frequencies
        String[] words = {"apple", "banana", "apple", "orange", "banana", "apple"};
        Map<String, Integer> wordCount = new HashMap<>();
        
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }
        
        System.out.println("Word Frequencies: " + wordCount);
        
        // Example 2: Caching results of expensive computations
        Map<Integer, Integer> factorialCache = new HashMap<>();
        
        int number = 5;
        int result = factorial(number, factorialCache);
        System.out.println("Factorial of " + number + " is " + result);
    }
    
    public static int factorial(int n, Map<Integer, Integer> cache) {
        if (n == 0) return 1;
        if (cache.containsKey(n)) return cache.get(n);
        
        int result = n * factorial(n - 1, cache);
        cache.put(n, result);
        return result;
    }
}

Common Pitfalls and Best Practices

When working with Hash Maps, it's essential to be aware of common pitfalls and follow best practices:

Avoiding Null Keys and Values: Hash Maps do not allow null keys or values.
Handling Collisions: Understand how Hash Maps handle collisions and ensure your hash function distributes keys uniformly.
Choosing Appropriate Initial Capacity: Set an appropriate initial capacity to minimize rehashing.
Using Immutable Keys: Use immutable objects as keys to prevent unexpected behavior.

Advanced Techniques

For more advanced usage, consider the following techniques:

Custom Hash Functions: Implement custom hash functions for specific use cases.
Concurrent Hash Maps: Use ConcurrentHashMap for thread-safe operations in multi-threaded environments.
LinkedHashMap: Maintain insertion order using LinkedHashMap.

Code Implementation

Here is a comprehensive example demonstrating various operations on a Hash Map:

import java.util.HashMap;
import java.util.Map;

public class HashMapOperations {
    public static void main(String[] args) {
        // Creating and initializing a HashMap
        Map<String, Integer> digitValue = new HashMap<>();
        digitValue.put("zero", 0);
        digitValue.put("one", 1);
        
        // Accessing values
        System.out.println("Value for 'zero': " + digitValue.get("zero"));
        System.out.println("Value for 'one': " + digitValue.get("one"));
        
        // Adding new entries
        digitValue.put("three", 3);
        System.out.println("After adding 'three': " + digitValue);
        
        // Updating entries
        digitValue.put("zero", 5);
        System.out.println("After updating 'zero': " + digitValue);
        
        // Deleting entries
        digitValue.remove("zero");
        System.out.println("After removing 'zero': " + digitValue);
        
        // Checking if a key exists
        System.out.println("Contains 'one': " + digitValue.containsKey("one"));
        System.out.println("Contains 'three': " + digitValue.containsKey("three"));
        
        // Iterating over keys
        for (String key : digitValue.keySet()) {
            System.out.println(key + " is " + digitValue.get(key));
        }
    }
}

Debugging and Testing

Debugging and testing are crucial aspects of working with Hash Maps. Here are some tips:

Debugging: Use breakpoints and inspect the state of the Hash Map during execution.
Testing: Write unit tests to verify the correctness of your Hash Map operations.

Example of a simple test case:

import java.util.HashMap;
import java.util.Map;

public class HashMapTest {
    public static void main(String[] args) {
        Map<String, Integer> digitValue = new HashMap<>();
        digitValue.put("zero", 0);
        digitValue.put("one", 1);
        
        assert digitValue.get("zero") == 0 : "Test failed for key 'zero'";
        assert digitValue.get("one") == 1 : "Test failed for key 'one'";
        
        System.out.println("All tests passed.");
    }
}

Thinking and Problem-Solving Tips

When working with Hash Maps, consider the following strategies:

Break Down Problems: Divide complex problems into smaller, manageable parts.
Practice: Solve coding exercises and projects to reinforce your understanding.
Explore Documentation: Refer to the official Java documentation for detailed information on Hash Maps.

Conclusion

In this lesson, we covered the fundamental concepts of Hash Maps in Java, including creation, initialization, accessing values, adding entries, updating entries, deleting entries, checking key existence, and iterating over keys. We also discussed common pitfalls, best practices, advanced techniques, debugging, testing, and problem-solving tips. Mastering Hash Maps will enhance your ability to write efficient and effective Java programs.

Additional Resources

For further reading and practice, consider the following resources: