Keys Must Not Change

LinkedMap<K, V> implements the Map ADT with a singly linked list, one node per pair. Its get finds a key by comparing the given key with each stored key using equals, and returns the stored value, or null if no stored key matches.

Badge is a class with one field, name, a setter setName, and an equals method that returns true when two badges have the same name.

Exercise

What do the last three lines return? Explain.

Badge b = new Badge("red");
Map<Badge, Integer> points = new LinkedMap<>();
points.put(b, 74);
b.setName("gold");

points.get(new Badge("red"));
points.get(new Badge("gold"));
points.size();

Solution

They return null, 74, and 1. The map stores a reference to the object b, so the stored key is b itself. After setName("gold"), the stored key no longer equals a badge named "red", and it now equals a badge named "gold". The entry was never removed, so the size is still 1.

Solution

A key must not change, while it is in the map, in any way that affects how it compares with other keys. An immutable key, such as a String or an Integer, follows the rule, because it cannot change after it is created.

Solution

No. The map never searches by value, so a change to a value cannot make an entry impossible to find.