Today's lesson introduces two new extremely useful data structures: maps and sets. Together, maps and lists can be used to solve almost any problem. And sets have their uses as well. So let's get started!
Maps represent a fundamentally new data structure for us to consider. So far we've looked at data structures that put items in order—like arrays and lists. We've also discussed using higher-dimensional arrays when needed to represent higher-dimensional data.
Maps are quite different. They don't put items in order. Rather, they allow us to store and look up mappings between one thing and other.
More specifically, maps store mappings between keys and values. Each key in a map maps to just one value. However, the same value can be mapped to by multiple keys.
Let's make this more concrete by looking at a few examples.
In Java, to create a map we'll import
java.util.HashMap, similarly to how we imported
java.util.ArrayList when working with lists:
Note that, like
Maps also utilize type parameters within the angle brackets:
<String, String> in the example above.
Maps require two type parameters: one for the key, and a second for the value.
Also note that we use the diamond operator
<> on the right, since the type parameters for the
HashMap are the same as for the
Don't worry too much about the hash in
HashMap yet, although we'll return to this later!
The map we created above can be used to map
Strings to other
We can add mappings to our
put, which accepts a key as the first parameter and a value as the second parameter.
We also show how a second call to
put replaces the mapping for "challen", since each key in the map maps to a single value.
Note that a map can have multiple keys that map to the same value:
To retrieve values from a
Map we use the
get method, which accepts a single parameter: the key to look up in the
get returns the value mapped to by that key, or
null if that key does not exist in the
Sometimes we also refer to this as looking up the key in the map: so looking up the mapping for "challen" or "student1" in the example above.
Maps are great for solving problems where we need to save and look up information based on a key. Let's look at an example that may hit close to home: Recording scores on a homework problem!
If you want to iterate over all of the mappings in a Java
Map, there are a few different ways to do that:
Before we wrap up, let's briefly examine one other potentially-useful data structure: sets. A set represents an unordered collection of distinct elements. We can add and remove items from a set, but the set either contains the item or does not. Items in a set don't have an index and are not counted.
Sets are generally less useful that lists or maps. But they do come in hand sometimes, particularly when you need to record membership but don't care about counts or ordering. Let's look at an example where a set might come in handy: