CODEWITHSUNDEEP
javahashmap
bijiDango
bijiDango

Reputation: 1596

How does a hashmap saves and looks up for a key

I encountered a problem about HashMap. After some debugging with no result, I wrote a short piece of code to test the HashMap. But the result turns out more confusing!

public static void main(String[] args) {
    Point a = new Point(0, 0);          // java.awt.Point
    Map<Point, Integer> map = new HashMap<Point, Integer>();
    map.put(a, 0);
    System.out.println(map.containsKey(new Point(0, 0)));    // true
    a.x = 1;
    System.out.println(map.containsKey(new Point(0, 0)));    // false
    System.out.println(map.containsKey(new Point(1, 0)));    // false
    System.out.println(map.containsKey(a));                  // false
}

I was expecting the 2nd or 3rd output could give me a true, and the 4th definitely true. But the fact seems not consent.

About my intent to change the key, I used the map to save some mobs. The mob has Point field, and the key of the map uses the same reference. Then I might be able to look for the mob by its coordination and also changes the coordination easily.

Upvotes: 2

Views: 538

Answers (2)

Jawher
Jawher

Reputation: 7097

The behavior you're getting is normal due albeit confusing due to how HashMap is implemented.

Roughly, here how putting a value V with a key K works:

  • HashMap computes the hashcode H of the key K
  • H is used as an index (trimming it if necessary) in an array where the values are stored: data[H] = Entry(K, V)

Afterwards, when you call get(K) or containsKey(K):

  • HashMap computes the hashcode H of the key
  • It then checks if data[H] is not null and that it's key equals the key you provided
  • If so, it returns the value V for get or true for containsKey

In you case, you called put with Point(0, 0). Let's say Point(0, 0).hashcode() returned 0. So the value gets stored in index 0:

data = [Point(0, 0), null, ...]

You then modify the point (a.x=1). The key is modified but HashMap can't detect it and so it won't move the entry to the correct index.

data = [Point(1, 0), null, ...]

Afterwards, map.containsKey(new Point(0, 0)) returns false because according to how containsKey works as shown above:

  • hashcode returns 0 (same as when you originally put it)
  • But then, Point(0, 0) (the key you're testing) is not equal to Point(1, 0) (the key you stored), hence the false

The third test also prints false because hashcode(Point(1, 0)) (the key you're testing) might and does return a different value from hashcode(Point(0, 0)) (the key you stored). Let's say it returns 1, whereas the initial point is stored at index 0. That's why it also returns false.

Morale of the story: The keys used in a HashMap must be immutable or weird behavior would ensue.

Upvotes: 2

Angelo Fuchs
Angelo Fuchs

Reputation: 9941

You can look it up in the source code and understand it, although not so easily as I thought.

The problem is that when you change the value of x you make the object within the hash tree seem to be at the wrong position, I'll illustrate it.

You place the key inside a tree that looks like this:

.../-- Point(0,0)
root
---\.. nothing

If you had put Point(1,0) inside it it would look like this:

.../.. nothing
root
...\.. Point(1,0)

So when you altered the key the tree looks like this:

.../.. Point(1,0)
root
...\.. nothing

Now you look for Point(1,0) and the map traverses the lower branch where such a key should belong, but there is nothing. And when you look for Point(0,0) it traverses the upper branch where there is the wrong key.

Therefore it is important to NEVER change a value thats part of the .hashCode() of an object. Instead use a new instance of that object to do alternations or use a clone of the Object to place inside the HashMap.

Alternatively if you want to change the keys you can remove it from the map, alter it and put it back in. Like this:

public static void main(String[] args) {
    Point a = new Point(0, 0);          // java.awt.Point
    Map<Point, Integer> map = new HashMap<Point, Integer>();
    map.put(a, 0);
    System.out.println(map.containsKey(new Point(0, 0)));    // true
    Integer value = map.remove(a);
    a.x = 1;
    map.put(a,value);
    System.out.println(map.containsKey(new Point(0, 0)));    // false
    System.out.println(map.containsKey(new Point(1, 0)));    // true
    System.out.println(map.containsKey(a));                  // true
}

You may want to shift the remove, alter and put method to an own method inside the object to have it available. You can call it setAndRelocate(int newX, int newY, Map container) and have it back to one line in your regular code.

Upvotes: 3

Related Questions