Hashmaps in Java

Copy Link LinkedIn Message Facebook Email X

A HashMap is a super fast and useful data structure. In this lesson, you'll learn how hash maps work, how they are so fast, and why they are so commonly used.

Components of a Hashmap

Hashmaps are different than what you've learned so far since they are "key-value" stores.

A simple example of a key-value store is an old-fashioned phone book. In the phone book example, a person's name would be the key, and their phone number would be the value. Another example could be storing countries with their capitals, as seen in the table below:

Under the covers of a hashmap, you actually use an object called an Entry or a Node. These are classes that look like this:

public class Entry<K, V> {  
  
    K key;  
    V value;  
    // this is capable of being a LinkedList (for collisions)  
    Entry<K, V> next;
} 

So your underlying array inside the hashmap actually looks like this:

private Entry<K, V>[] entryTable;

This allows you to store the key and the value inside a simple object. (You'll dig into this further in the coming pages, and it will make perfect sense.)

Big O Complexity for a Hashmap

While the hash map is different than the linked list, their complexities are the same! So for adding and removing it's constant time (O(1)) and to search it's linear (O(n)).

How Does a Hash Map Work

Like several other data structures, a HashMap uses a simple Array as its underlying data structure.

A hash map simply adds a bit of functionality above the underlying array and controls how you can add, search, and retrieve elements out of the underlying array.

The magic of a hash map lies in the hash() method and the hashCode() method - the latter is found in Java's Object class.

As you now know, all objects in Java are subclasses of the Object class. So, all objects in Java have direct access to the hashCode() method (since it's in the Object class).

The hashCode() method returns an int. What makes this function so useful is that the hashCode() method is guaranteed to return the same exact int value for a specific object every time it is called (during a single run of said application).

HashCode Requirements in Java

The hashCode() method has a specific contract in Java.

1. The hashCode() must return the same int for the same object every time it is called during an execution of a Java application.
2. Two objects that are equal according to the equals(Object) method must produce the same int result when their hashCode method is called.
3. It is not required for the hashCode to produce different int values for two unequal objects during an execution of a Java application (although creating this rule can improve the performance of hash tables).

So, since you know you have this hashCode() method, and you know it always returns the same int value for a given object, you can leverage the hash of a given object to determine exactly which index (of the underlying array) a given object should be placed, or currently resides, within the hash map.

Modulus

The way you determine the index to place or retrieve a given object in the hash map is by getting the hash for a given key and then using the modulus operation on that hash. You mod the hash by the length of the underlying array.

The result of this modulus operation will be an int. This integer will be used as the array index where you place/find the value. This works because the result of the mod operation can never be larger than the length of the array. So if the array length is 10, and you mod by 10, you're guaranteed to get a result between 0 and 9. This result acts as the index of where to place/find the element.

If the hash map's underlying array has a length of 10, and the hash value of a given object is, for example, 3098. Then the remainder, or mod, of that hash is 8. This is because 10 goes into 3098 evenly 309 times with a remainder of 8. So, in this case, you would put/find the value at the index of 8 in the underlying array. 

Handling (Expected) Hash Map Collisions

Coming back to hash map entries, this Entry object also has an instance variable named next of type Entry. This means that the Entry class can be used as a LinkedList in the case of collisions.

When working with hash maps, you often run into the concept of collisions. A collision occurs when you have two elements that mod to the same index in the array.

For instance, if the hash code of one object is 465431 and the hash code of another object is 8979861, when you mod these both by 10 (the length of your example underlying array), they'll both need to be placed at the index 1 (465431 % 10 equals 1, and 8979861 % 10 equals 1). This will result in a "collision".

In the case of a collision such as this, then you will place the elements that you are adding into the hash map as a node in a linked list of type Entry at the given index in the array (this will also make much more sense shortly as you build your own custom Hash maps).

Benefits of a Hash Map

The primary benefit of a hash map is that, unlike a traditional array, you do not need to (potentially) iterate over each and every element in the array in order to find a given element within the array.

Imagine searching for an element in an array. The only way to search it is to iterate over each and every element and compare each value to the one you're looking for. There's a decent chance the element you're looking for could be at the beginning of the array. But there's an equally decent chance that it could be at the end of the array or even the final element of the array. In these cases, it's horribly inefficient to search an array in an iterative fashion.

Just as it's horribly inefficient to search a phone book by starting at page 1 and simply scanning each and every element until you find the person and number you're looking for.

In the case of a hash map, you can run a simple hashCode() function to determine the exact index where you can insert and/or find an element within an array rather than iterate over each element.

Experiment with Java's Built-in HashMap Class

Java provides a fully functional HashMap class for you to use. In your day-to-day life as a programmer, you always use Java's implementation of the hashmap rather than creating your own implementation.

That said, creating your own implementation of the HashMap class is always a great idea so that you fully understand how it works. You'll do this in an upcoming lesson. But for now, explore how to use Java's built-in HashMap class.

import java.util.HashMap;

public class Main {  
  public static void main(String[] args){
    // create the hashmap  
    // the "key" will be the email, a String
    // and the "value" will the Person object
    HashMap<String, Integer> capitalCityPopulations 
      = new HashMap();
  
    // "put" a few capital cities with their population
    capitalCityPopulations.put("Ottawa", 1077900);
    capitalCityPopulations.put("Lima", 11204000);
    capitalCityPopulations.put("Nairobi", 5541172);

    // demonstrate "getting" an 
    // element out of the HashMap
    int limaPopulation = 
      capitalCityPopulations.get("Lima");
    System.out.println(limaPopulation);

    // demonstrate iterating through 
    // the entries of a HashMap
    Set entries = capitalCityPopulations.entrySet();
    Iterator iterator = entries.iterator();
    // loop through the entries
    while(iterator.hasNext()) {
      // get each Entry individually
      Map.Entry city = 
        (Map.Entry)iterator.next();
      // print out the entry's key and value
      System.out.print(
        "The key is: "+ city.getKey() +
        " and the value is: " + city.getValue());
      }
  }
}

If you'd like to continue learning about HashMaps, check out the following resources in the Data Structures & Algorithm course:

• Hash Functions
• Hash Maps
• Java HashMaps

Summary: What is a Java Hashmap

• A HashMap is an abstract data type in Java
• Hash maps are super fast and useful
• Hash maps are collections key value pairs
• The hashCode() method provides the ability to locate elements at their exact index
• The primary benefit of hash maps is avoiding the requirement to blindly iterate over an entire list while looking for an element
• The hash code of an object is an int
• A hash map collision is when two elements are placed at the same index
• Collisions are resolved by placing the elements in a linked list of type Entry at that index
• Creating your own hash map class is an excellent way to validate your understanding - this is coming up next

Big O Complexity

• Best Case: O(1)
• Worst case: O(n)

Hash Code Requirements

1. The hashCode must return the same int for the same object every time it is called during an execution of a Java application.
2. Two objects that are equal according to the equals(Object) method must produce the same int result if their hashCode method is called.
3. It is not required for the hashCode to produce different int values for two unequal objects during the execution of a Java application.

Steps for Working with a HashMap

1. Create the HashMap
2. Add elements to the HashMap (put())
3. Find elements within the HashMap (get(<KEY>)) using the "key"
4. Iterate through all the elements in the HashMap using entrySet() and an iterator