HashMap Introduction — Collections and Generics

Student: So ArrayList lets me put things at specific positions, and HashSet ensures that there are no duplicates. But what if I wanted something different? Let’s say I was storing a bunch of students in a class, and some of them have the same first name. I can’t use a HashSet because then there would be no way to have two students with the same name, and an ArrayList would have no way to distinguish between the students.

Prof: Hmm, that is a real problem. In practice, when you turn in an assignment what do you put on your submission so that we can tell students with the same name apart?

Student: My student ID number? That’s unique. But if I created a HashSet of student ID numbers, how would I be able to know which name corresponds to which ID?

Prof: Java has a data structure that is perfect for this: HashMap. It stores data as key-value pairs. Here is your student example written out as a HashMap. What do you notice?

import java.util.HashMap;

HashMap<Integer, String> directory = new HashMap<Integer, String>();
String name;
int count;
String all;
void main() {
  directory.put(12345, "Ricardo");
  directory.put(67890, "Navya");
  directory.put(13579, "Sofia");

  name = directory.get(67890);
  count = directory.size();
  all = directory.toString();
}

Student: So when we define a HashMap, we give two different types inside the angle brackets. And then instead of using add(), we use put() and are passing in two values for each element?

Prof: Yes, in this example the Integer student ID is the key, while the String student name is the value.

Student: What would happen if I put the same student ID number twice? Would it be ignored, like adding a duplicate to a HashSet?

Prof: Not quite. The keys are unique, just like the elements of a HashSet, but a second put with the same key replaces the old value instead of being ignored. The values are not unique, though. This is important for our student directory example, as we want to be able to support multiple students with the same name.

import java.util.HashMap;

HashMap<Integer, String> directory = new HashMap<Integer, String>();
String before;
String fresh;
String current;
int count;
void main() {
  directory.put(12345, "Ricardo");
  directory.put(67890, "Navya");

  before = directory.put(12345, "Maitrayee");
  fresh = directory.put(24680, "Maitrayee");
  current = directory.get(12345);
  count = directory.size();
}

Prof: Notice what put() returns when you already have a value at that key?

Student: It returns the old value, and replaces it in the HashMap with the new one. But when there wasn’t a value there yet, it returns null. And you also used a method we have seen before, get(). You passed in the key and it returned the value.

Prof: Yep, HashMap is designed for you to fetch a value using a key.

Student: What if you try to fetch a value from a key that doesn’t exist? Will it give you an error?

import java.util.HashMap;

HashMap<Integer, String> directory = new HashMap<Integer, String>();
String missing;
void main() {
  directory.put(12345, "Ricardo");
  directory.put(67890, "Navya");

  missing = directory.get(11111);
}

Student: Ah so it’s null.

Prof: A null value can be problematic for your program, so it’s a good idea to check if a key exists before attempting to fetch and use a value. HashMap provides a method for this called containsKey(). And just like ArrayList and HashSet you can remove elements. remove() takes the key and removes both the key and the value.

import java.util.HashMap;

HashMap<Integer, String> directory = new HashMap<Integer, String>();
boolean hasRicardo;
boolean hasNobody;
String removed;
String removedAgain;
int count;
void main() {
  directory.put(12345, "Ricardo");
  directory.put(67890, "Navya");

  hasRicardo = directory.containsKey(12345);
  hasNobody = directory.containsKey(11111);

  removed = directory.remove(12345);
  removedAgain = directory.remove(12345);
  count = directory.size();
}

Student: Hey Professor, I made a HashMap of how many points each student has, and asked for a student I haven’t added yet. But, my program crashed! Do I need to use the containsKey here? Or is there a better way to deal with this problem?

import java.util.HashMap;

HashMap<String, Integer> points = new HashMap<String, Integer>();
int adaPoints;
int linusPoints;
void main() {
  points.put("Ada", 90);

  adaPoints = points.get("Ada");
  linusPoints = points.get("Linus");
}

Prof: For situations like this, there is a special kind of get method. You can use getOrDefault() which takes a second argument representing the default value to use if the HashMap doesn’t contain that key.

import java.util.HashMap;

HashMap<String, Integer> points = new HashMap<String, Integer>();
int adaPoints;
int linusPoints;
void main() {
  points.put("Ada", 90);

  adaPoints = points.getOrDefault("Ada", 0);
  linusPoints = points.getOrDefault("Linus", 0);
}

Student: What if I want to use a for-each loop? If I try to write it like this there is an error.

import java.util.HashMap;

HashMap<String, Integer> points = new HashMap<String, Integer>();
int total;
void main() {
  points.put("Ada", 90);
  points.put("Grace", 75);

  total = 0;
  for (int p : points) {
    total += p;
  }
}

Prof: Think about this: when you are looping through points, and setting int p to be each element, how are we supposed to know whether you want int p to be the key or the value?

Student: Well obviously I want it to be the value. The value is the one that is an Integer.

Prof: We need to specify whether you are trying to loop through the keys or the values. Let’s start with an example of the keys. We can use points.keySet() to tell Java that we want to loop through the set of all keys in the HashMap.

Student: Ok, but what if I want to loop through all the point values?

Prof: You can use points.values(). Remember that just like HashSet, there isn’t a set order. This is fine in this case for summation.

import java.util.HashMap;

HashMap<String, Integer> points = new HashMap<String, Integer>();
int total;
int sameTotal;
void main() {
  points.put("Ada", 90);
  points.put("Grace", 75);
  points.put("Alan", 60);

  total = 0;
  for (String student : points.keySet()) {
    total += points.get(student);
  }

  sameTotal = 0;
  for (int p : points.values()) {
    sameTotal += p;
  }
}

Prof: Based on what we have talked about, try writing code that checks how many times each word appears in an array. I’ll give you a String[] array to start off with, try to use a HashMap.

Student: Ok, to count the number of times a word appears, I would need to loop through the list and add 1 to the total for each appearance. So the keys should be the word, because that is unique, and the values should be the count. At the beginning the HashMap is empty, and whenever a word appears, I either add it to the HashMap if it is new, or increment the value by 1.

import java.util.HashMap;

String[] words = {"to", "be", "or", "not", "to", "be"};

HashMap<String, Integer> counts = new HashMap<String, Integer>();
int toCount;
int distinct;
void main() {
  for (String w : words) {
    counts.put(w, counts.getOrDefault(w, 0) + 1);
  }

  toCount = counts.get("to");
  distinct = counts.size();
}

Prof: There you go. Now that we have seen all three, here is how to choose between them. Use an ArrayList when the position of your elements matters, or when you need to allow duplicates. Use a HashSet when you only care whether or not an element is present, and you don’t want duplicates. Use a HashMap when you want to look up a value using a key, like finding a student’s name from their ID. Keys are unique, but the values can be duplicates. Both HashSet and HashMap are unordered, and their advantage is fast lookups, so ask yourself what question your program is really asking.

Student: So how would I use one of these in a real program, like with the Post class from before?

Prof: Let’s look at that next.

Practice

stock starts out mapping "apple" to 3 and "pear" to 5. Fill in the missing pieces so that the apple count is replaced by 4, the pear is removed entirely, and apples holds the apple count afterwards.

import java.util.HashMap;

HashMap<String, Integer> stock = new HashMap<String, Integer>();
void main() {
stock.put("apple", 3);
stock.put("pear", 5);

int apples = ;
System.out.println(apples);
System.out.println(stock.size());
}