Skip to content

Latest commit

 

History

History
203 lines (133 loc) · 7.92 KB

2015-03-29.md

File metadata and controls

203 lines (133 loc) · 7.92 KB

Objective

To learn about HashMap:

  • What is an associative collection?
  • How to add keys and values.
  • How to look up keys to get values.

We'll also practice working with ArrayList.

Setup

This repo contains some Java source and an IntelliJ project in projects/2015-03-28. Please open (not import) this project directory in IntelliJ.

Maps

A map is a collection that associates keys with values.

Some examples of maps:

  • For each planet in the solar system, the number of moons.
  • For each U.S. state, the state capital.
  • For each student in Access Code, his/her birthday.
  • For registered voters, whether each voted in the last election.

For example, I tell you a state, you tell me its capital. Or, I tell you a planet, you tell me how many moons it has. You can think of a map as a table with two columns, like so:

key = Planet value = # Moons
Mercury 0
Venus 0
Earth 1
Mars 2
Jupiter 67
Saturn 62
Uranus 27
Neptune 14

The left column contains keys; the right, values. We say it maps keys to values, in this case maps planets to numbers of moons.

To look something up in a map, look down the key column until you find the row that matches. Once you do, read off the value in the column to its right. If you don't find the entry you need in the key column, for example if you try to look up Pluto, the lookup fails and there is no value.

Something facts about maps:

  • The keys are all the same type.

  • The values are all the same type.

  • The keys and values don't have to be the same types (though they may be).

  • Any key can appear only one time in the map.

  • A value may appear more than once in the map.

  • The map can look things up only in one direction: given the key, return the value. Because a value can appear more than once, it doesn't work the other way: for example, which planet has zero moons?

Java's HashMap

There are several ways to make a map in Java. Today we're going to use one named java.util.HashMap (API docs).

You'll have to import it like this, or let IntelliJ do it for you.

import java.util.HashMap;

Recall that with ArrayList, you have to tell Java the type of elements in angle brackets. With HashMap, you have to tell Java the types of both the keys and the values.

HashMap<String, Integer> numberOfMoons = new HashMap<String, Integer>();

The two types are the key type and the value type, respectively. In this case, the key type is String and the value type is Integer.

We now have an empty hash map, like a table with no entries.

key = Planet value = # Moons

To look up an entry in a map, use the get(key) method. Its argument is always the key type of the map (the first one in angle brackets). Its return type is the value type of the map (the second one in angle brackets).

Integer num = numberOfMoons.get("Neptune");

Our map is empty; it doesn't contain any keys at all. So, the value is null. But we can add values with the put(key, value) method.

numberOfMoons.put("Mercury", 0);
numberOfMoons.put("Venus", 0);
numberOfMoons.put("Earth", 1);
numberOfMoons.put("Mars", 2);

After this, the table would look as follows:

key = Planet value = # Moons
Mercury 0
Venus 0
Earth 1
Mars 2

Since it contains keys and values, we can look up a key to obtain a value.

Integer num = numberOfMoons.get("Earth");
System.out.println(num);

But any key other than one we've put in already returns null.

System.out.println(numberOfMoons.get("Neptune"));
System.out.println(numberOfMoons.get("Sun"));
System.out.println(numberOfMoons.get("Texas"));

Exercises

Please work through these exercises, completing as many as you can in class.

  1. Finish moons: Finish the hashmap of number of moons for each planet.

  2. Moons as method: Convert this to a method that returns this hashmap. It should look like this:

public static HashMap<String, Integer> getNumberOfMoons() {
    // Write code here!
}
  1. Moons overload: Create an overload for this method that takes a planet name as an argument and returns the specific number of moons. Be careful how you handle an argument that is not the name of a planet.
public static int getNumberOfMoons(String planet) {
    // Write code here!
}
  1. Is a planet: One nice bonus of having this hashmap is that you can check whether a string is the name of a planet by checking whether that string is a key in the hashmap. Write a method that does this:
public static boolean isPlanet(String name) {
    // Write code here!
}

Test your method on a few real and fake planet names.

  1. State capitals: The lesson project contains a class named Capitals, with a method getCapitals() that returns a hashmap from state names to capitals. In the main() method, write a program that prompts the user for a state name. If the user enters a state name, print out,
The capital of (state) is (capital).

Otherwise, print out,

(name) is not a state!

Make sure you test your program on correct and incorrect state names.

  1. Map of word lengths: Write a method that takes an array list of strings as a parameter, and creates and returns a hash map whose keys are the strings from the array and whose values are the lengths of these strings.
public static HashMap<String, Integer> getLengths(ArrayList<String> strings) {
    // Write code here!
}

For example, if you call it with an array containing "hello" and "goodbye", you'll get back a hash map with two keys: "hello" associated with the value 5, and "goodbye" associated with the value 7.

Test it with code similar to this.

ArrayList<String> words = new ArrayList<String>();
words.add("banana");
words.add("pineapple");
words.add("cantaloupe");

HashMap<String, Integer> lengths = getLengths(words);
System.out.println(lengths.get("banana"));      // should print 6
System.out.println(lengths.get("cantaloupe"));  // should print 10
System.out.println(lengths.get("broccoli"));    // should print null
  1. Count words: Write a method that takes an array of words as a parameter, and creates and returns a hash map whose keys are all unique words that appear in the list, and whose values are the number of times each word appears.

See the WordCount class for a skeleton. This class also contains code that loads the text of Obama's 2014 State of the Union speech and divides it into words.

  1. (Bonus) Two lists make a map: Another way to represent a mapping is with the key and value columns in the tables shown above, using one ArrayList for the keys and one ArrayList for the columns.

For example, to represent the number of moons for each planet, the keys will be a ArrayList<String> containing Mercury, Venus, Earth, Mars, etc. and the values will be a ArrayList<Integer> containing 0, 0, 1, 2, etc. To look up the value for a key, first find the index of the key in the keys list, and then extract the corresponding index from the values list.

The lesson project ListMap contains a class named ListMap, which sets this up for you. There are three methods for you to implement: one to put a key and value into the "map", one to look up a key, and one to remove a key and value. The main() method contains tests: once you have implemented the other three methods correctly, all the tests should print "true"!

Note: While this is a correct way to implement maps in Java, the reason we don't usually do it this way is because it is inefficient once there are many keys and values in the map.