Putting a new key into a HashMap replaces an existing different key

Question

The answer: Thanks for all the help! Like most of you said the solution was to make a new 2d int array, and copy the values from the old one. This was the function i made, and i can then add the new board into the hashmap, as a new key.

 void newboard(){
    NewBoard = new int[N][N];
    for(int n = 0; n < N; n++){
        for(int i = 0; i < N; i++){
            NewBoard[n][i] = CurrentBoard[n][i];
        }
    }
}

The Question:

I have the following code, that puts an 3x3 board along with a list of integers, specifically (f, g, h) into a hashmap. The Board CurrentBoard is an unsolved 8-puzzle.

public static HashMap<int[][], List<Integer>> map = new HashMap<>();
map.put(CurrentBoard, fgh);

I initialise the hashmap, and for the rest of the program I want to iterate through the map, to get the board I need. Every entry of the map will be a specific state of the 8-puzzle board after the '0' position has been moved.

This is my way of doing that. The 'cv' variable is just to choose the board (key) with the lowest "f" value.

for(Map.Entry<int[][], List<Integer>> mapentry : map.entrySet()) {
        if (cv > mapentry.getValue().get(0)) {
            cv = mapentry.getValue().get(0);
            CurrentBoard = mapentry.getKey();
            fgh = mapentry.getValue();
        }
}

Now that I've got a Board in the "CurrentBoard" variable, I want to move the '0' up one row. So I've called this function:

void moveUp(){
    NewBoard = CurrentBoard;
    memory = NewBoard[ZeroPositionX][ZeroPositionY - 1];
    NewBoard[ZeroPositionY- 1][ZeroPositionX] = 0;
    NewBoard[ZeroPositionY][ZeroPositionX] = memory;
}

Then I do a couple of (for this question) unimportant checks, and recalculate the fgh values for this NewBoard.

I then proceed to put the NewBoard along with the fgh values into the hashmap by using

map.put(NewBoard, fgh);

My problem is that this replaces the current key in the hashmap. In other words, instead of adding a key and a value to the hashmap, it replaces the already existing key and value. I have tried printing both the New and current boards to ensure they are different.

When I print the entrySet() of the hashmap it only gives me the latest entry. In other words the board, and the values after having moved the '0'.

for(Map.Entry mapentry : map.entrySet()){
        System.out.println(mapentry);
    }

Why does adding the new key and value to the hashmap not work?

Endnote: I am new to Java, so some of this is probably sub-optimal. I will do my best to explain more in detail if necessary.

Answer 1

You're changing the content of your NewBoard variable / array, but the reference remains the same. So when you call map.put(NewBoard, fgh);, the key is always the same reference (think same address in memory, although each time with different contents).

If you want to store a new entry in the map for each board state, you'll have to create a new array each time and copy + alter its content.

Answer 2

The problem is that you're modifying the int[][] that's your HashMap key, instead of creating a new one. Here's the summary of your code (some lines snipped):

CurrentBoard = mapEntry.getKey(); //here CurrentBoard points at the exact same object as the key in your map
NewBoard = CurrentBoard; //now NewBoard and CurrentBoard are both pointing at the same int[][]
NewBoard[a][b] = 0; //this updates that one object
NewBoard[c][d] = memory; //still updating the same object
map.put(NewBoard, fgh); //NewBoard is still the same object, so this is replacing the existing key

Note that, in general, modifying the content of any Key in a Map is not a good idea - it can lead to even stranger behavior than what you're seeing.

Note also that using an Array as a map key is usually wrong - since the map depends on the result of key1.equals(key2), and for any Java arrays a1, a2, a1.equals(a2) only if a1 == a2 (that is, they're the same array). For example:

int[] a1 = new int[1];
a1[0] = 1;
int[] a2 = new int[1];
a2[0] = 1;
System.out.println(a1.equals(a2)); //prints "false"

Answer 3

The problem is that you are modifying the same key, which will not work as you expect. To get the 'right' behavior you should clone your key. As your key is int[][] you don't need to do nothing, only call clone().

    int[][] currentBoard = {{1, 2, 3}, {4, 5, 6}};

    HashMap<int[][], String> map = new HashMap<int[][], String>();

    map.put(currentBoard, "test1");

    int[][] cloned = currentBoard.clone();

    cloned[0][0] = 10;

    map.put(cloned, "test2");

    for(Map.Entry mapentry : map.entrySet()){
        System.out.println(mapentry.getValue());
    }

prints

test1
test2

If you want to use some class that you've created, you need to override clone(), see Cloneable

Important to note that clone() will only clone the array reference, not it's values. So currentBoard[0].equals(cloned[0]) will be true, but i think it's make no difference for your case.

see also this question on SO about cloning Java: recommended solution for deep cloning/copying an instance

Answer 4

Changing the values in your Map key of type int[][] will not change how its equals and hashCode methods behave. Those are the methods that are called to determine, whether the key is semantically the same.

So to add a new key, you either have to create a new one or use a proper class with different equals/hashCode logic.

To create a new key you could use clone():

void moveUp() {
    NewBoard = new int[3][3];
    NewBoard[0] = CurrentBoard[0].clone();
    NewBoard[1] = CurrentBoard[1].clone();
    NewBoard[2] = CurrentBoard[1].clone();
    memory = NewBoard[ZeroPositionX][ZeroPositionY - 1];
    NewBoard[ZeroPositionY- 1][ZeroPositionX] = 0;
    NewBoard[ZeroPositionY][ZeroPositionX] = memory;
}

Note, that we have to invoke clone three times, as it is not capable of completely cloning a two-dim array (see here).

A cleaner way would be to create a Board class like this (untested, please excuse typos):

public class Board {

    private int[][] content = new int[3][3];

    /**
     * Creates a new empty board.
     */
    public Board() {
    }

    /**
     * Call this constructor to create a new instance of a given board.
     */
    public Board(Board otherBoard) {
        this.content[0] = otherBoard.content[0].clone()
        this.content[1] = otherBoard.content[1].clone()
        this.content[2] = otherBoard.content[2].clone()
    }

    public void set(int a, int b, int value) {
        content[a][b] = value;
    }

    public int get(int a, int b) {
        return content[a][b];
    }

    public int hashCode() {
        int code = 0;
        for (int a=0; a<3; a++) {
            for (int b=0; b<3; b++) {
                code += content[a][b];
            }
        }
        return code;
    }  

    public boolean equals(Object that) {
        if (!(that instanceof Board)) return false;
        return Arrays.equals(this.content[0], that.content[0])
            && Arrays.equals(this.content[1], that.content[1])
            && Arrays.equals(this.content[2], that.content[2])
    }
}

Overall, you should study the general contract of Map in https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

Also, in your code, make sure that you never change the content of a key, once it's used in a Map. Otherwise chaos will rule...

Good luck.