Wednesday, February 23, 2011

Chapter 46: Using Maps

In the previous chapter, we took a look at Sets that let us store unique objects as a collection. We also have collections as part of the Java API that let us store values as key-value pairs. Each value in the collection would have a key that uniquely identifies this value. They are called “Maps”. We are going to take a look at these collections in this chapter.

So, lets get started!!!

Using Maps

Remember the full chapter we spent learning about hashCode() and equals() methods? You might have wondered where the hell am I supposed to use them when you read that chapter. Well my friend, you need to look no further. This is exactly where we use them.

When you use a class that implements Map, any classes that you use as a part of the keys for that map must override the hashCode() and equals() methods. (To be honest, you only have to override them if you’re interested in retrieving stuff from your Map. Seriously, it’s legal to use a class that doesn’t override equals() and hashCode() as a key in a Map; your code will compile and run, you just won’t find your stuff.)

Here’s a simple code demonstrating the use of a HashMap:

import java.util.*;
class Car {
public Car(String n) { name = n; }
public String name;
public boolean equals(Object o) {
if((o instanceof Car) && (((Car)o).name == name)) {
return true;
} else {
return false;
public int hashCode() {return name.length(); }

class Ferrari { }

enum Cars {CAR, FERRARI, BMW }

class MyFirstMapTestExample {

public static void main(String[] args) {

Map m = new HashMap();
m.put("k1", new Car("Porsche")); // add some key/value pairs
m.put("k2", Cars.CAR);
m.put(Cars.FERRARI, "FERRARI key");
Car d1 = new Car("Subaru"); // let's keep this reference
m.put(d1, "Car key");
m.put(new Ferrari(), "Ferrari key");
System.out.println(m.get("k1")); // #1
String k2 = "k2";
System.out.println(m.get(k2)); // #2
Cars p = Cars.FERRARI;
System.out.println(m.get(p)); // #3
System.out.println(m.get(d1)); // #4
System.out.println(m.get(new Ferrari())); // #5
System.out.println(m.size()); // #6

which produces something like this:
Let’s review the output.
The first value retrieved is a Car object (your value will vary).
The second value retrieved is an enum value (CAR).
The third value retrieved is a String; note that the key was an enum value.
On the Spot Quiz: What’s the implication of the fact that we were able to successfully use an enum as a key?

The implication of this is that enums override equals() and hashCode(). And, if you look at the java.lang.Enum class in the API, you will see that, in fact, these methods have been overridden.
The fourth output is a String. The important point about this output is that the key used to retrieve the String was made of a Car object.
The fifth output is null. The important point here is that the get() method failed to find the Ferrari object that was inserted earlier. (The last line of output confirms that indeed, 5 key/value pairs exist in the Map.)

Why didn’t we find the Ferrari key String? Why did it work to use an instance of Car as a key, when using an instance of Ferrari as a key failed?

It’s easy to see that Car overrode equals() and hashCode() while Ferrari didn’t. Let’s take a quick look at hashcodes. We used an incredibly simplistic hashcode formula in the Car class—the hashcode of a Car object is the length of the instance’s name.
So in this example the hashcode = 6.
Let’s compare the following two hashCode() methods:
public int hashCode() {return name.length(); } // #1
public int hashCode() {return 4; } // #2

Are the preceding two hashcodes legal? Will they successfully retrieve objects from a Map? Which will be faster?

The answer to the first two questions is Yes and Yes. Neither of these hashcodes will be very efficient (in fact they would both be incredibly inefficient), but they are both legal, and they will both work.

The answer to the last question is that the first hashcode will be a little bit faster than the second hashcode. In general, the more unique hashcodes a formula creates, the faster the retrieval will be. The first hashcode formula will generate a different code for each name length (for instance the name Suzuki will generate one hashcode and the name Bentley will generate a different hashcode). The second hashcode formula will always produce the same result, 4, so it will be slower than the first.

Our last Map topic is what happens when an object used as a key has its values changed? If we add two lines of code to the end of the earlier MyFirstMapTestExample.main(), = "Lincoln";

we get something like this:


The Car that was previously found now cannot be found. Because the variable is used to create the hashcode, changing the name changed the value of the hashcode. As a final quiz for hashcodes, determine the output for the following lines of code if they’re added to the end of MyFirstMapTestExample.main(): = "Lincoln";
System.out.println(m.get(d1)); // #1 = "Subaru";
System.out.println(m.get(new Car("Subaru"))); // #2 = "Ford";
System.out.println(m.get(new Car("Subaru"))); // #3

Remember that the hashcode is equal to the length of the name variable.

When you study a problem like this, it can be useful to think of the two stages of retrieval:

1. Use the hashCode() method to find the correct bucket
2. Use the equals() method to find the object in the bucket

In the first call to get(), the hashcode is 8 (Lincoln) and it should be 6 (Subaru), so the retrieval fails at step 1 and we get null. In the second call to get(), the hashcodes are both 6, so step 1 succeeds. Once in the correct bucket (the “length of name = 6” bucket), the equals() method is invoked, and since Car’s equals() method compares names, equals() succeeds, and the output is Car key. In the third invocation of get(), the hashcode test succeeds, but the equals() test fails because Ford is NOT equal to Subaru.

Previous Chapter: Chapter 45 - Using Sets

Next chapter: Chapter 47 - Searching Treesets and Treemaps

No comments:

Post a Comment

© 2013 by All rights reserved. No part of this blog or its contents may be reproduced or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the Author.