[JAVA] How to use an array for a TreeMap key

In How to use an array for a HashMap key, it should be different if it is a TreeMap, but I could not verify it at once, so I divided it.

TreeMap key assumptions

Here, it is a TreeMap. HashMap is a little different. → How to use arrays for HashMap keys The key premise is --Implementing equals --Comparator is passed to or TreeMap that implements Comparable --Immutable instance

The first is that the containsKey, get, and put of the TreeSet use compareTo, so strictly speaking, equals may not be necessary, but it is necessary. The second is that implementing Comparable means implementing compareTo. If you cannot make it Comparable, prepare a Comparator separately and pass it to the TreeMap constructor. The third is not imuutable and can be changed later, but if you change the key value after putting it, it may not be found. This is implemented in a binary tree, so if you change the key from the outside and the right or left is incorrect, it will explode.

The difference between a HashMap and a TreeMap is whether you need a hashCode or a compareTo. If you have both, you can use both HashMap and TreeMap.

Results of array equals and hashCode

If it's an array, equals isn't correct, it doesn't implement Comparable.

Main.java

    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        System.out.println(b01 == b02);
        System.out.println(b01.equals(b02));
        System.out.println(Arrays.equals(b01, b02));
        //Comparable c = (Comparable)b01;
        TreeMap<byte[], String> map = new TreeMap<>();
        map.put(b01, "OK");
    }

A cast that is commented out will result in a compilation error. When you run ...

false
false
true
Exception in thread "main"
java.lang.ClassCastException: [B cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1290)
    at java.util.TreeMap.put(TreeMap.java:538)
    at Main.main(Main.java:15)

I have Arrays.equals, but I have to make compareTo by myself.

Part 1: Use ByteBuffer

I wondered who implemented Comparable in the first place, and when I grep, I also implemented the java.nio.Buffer corps.

• Boolean, Byte, Character, Double, Float, Integer, Long, Short, String
• ByteBuffer, CharBuffer, DoubleBuffer, FloatBuffer, IntBuffer, LongBuffer, ShortBuffer

Let's test it.

Main.java

    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        ByteBuffer w01 = ByteBuffer.wrap(b01);
        ByteBuffer w02 = ByteBuffer.wrap(b02);
        Map<ByteBuffer, String> map = new TreeMap<>();
        map.put(w01, "OK");
        System.out.println(w01 == w02);
        System.out.println(w01.equals(w02));
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
    }

When you run ...

false
true
OK
OK

OK at all. This is the best feeling. I like the standard library added from JDK 1.4.

Part 2: Make a ByteArrayWrapper

I dare to create a class that wraps byte []. I used ByteBuffer as a reference.

ByteArrayWrapper.java

import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte[] data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }
        return false;
    }

    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

Let's test it.

Main.java

    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper(b02);
        Map<ByteArrayWrapper, String> map = new TreeMap<>();
        map.put(w01, "OK");
        System.out.println(w01 == w02);
        System.out.println(w01.equals(w02));
        System.out.println(map.get(w01));
        System.out.println(map.get(w02));
    }

Result is···

false
true
OK
OK

I'm cloning () this time based on the lesson I learned from HashMap, but it's probably okay.

Modified ByteArray Wrapper

(1/18 postscript) I tried to fix it by changing the argument of the constructor from byte [] to byte ... (variadic argument) in the comment.

ByteArrayWrapper.java

import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte... data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return Arrays.equals(data, ((ByteArrayWrapper) other).data);
        }
        return false;
    }
    
    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

You can pass the array as before, or you can pass it as ByteArrayWrapper (1, 2, 3). It was supposed to be, but there wasn't much merit in the byte type because it required casting. With int type and long type, you can create an instance without casting and without preparing an array.

Main.java

    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper((byte)1, (byte)2, (byte)3);
        Map<ByteArrayWrapper, String> map1 = new HashMap<>();
        map1.put(w01, "OK");
        Map<ByteArrayWrapper, String> map2 = new TreeMap<>();
        map2.put(w01, "OK");
        System.out.println(map1.get(w01));
        System.out.println(map1.get(w02));
        System.out.println(map2.get(w01));
        System.out.println(map2.get(w02));
    }

Part 3: Use BigInteger → No

java.math.BigInteger is also Comparable, but it cannot be used because {0, 100} becomes {100}.

Part 4: Convert to a character string → Not efficient

It would have been nice if the HashMap was unique, but since the TreeMap has a size relationship, there is no choice but to set the numerical value to a fixed length. If there are not enough digits, pad 0 to the left.

Part 5: Pass the Comparator to the TreeMap

(1/18 postscript) At the beginning, I wrote that "Comparator is implemented or Passing Comparator to TreeMap", and I made only the example of Comparator, so I made an example of Comparator additionally.

Part 1 to part 3 is a method to implement and realize Comparable that wraps byte []. The fifth is the case of preparing a Comparator, which is another method.

It is almost the same as compareTo of ByteArrayWrapper, but creates ByteArrayComparator.

ByteArrayComparator.java

import java.util.Comparator;

public class ByteArrayComparator implements Comparator<byte[]> {
    public int compare(byte[] o1, byte[] o2) {
        int n = Math.min(o1.length, o2.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(o1[i], o2[i]);
            if (cmp != 0)
                return cmp;
        }
        return o1.length - o2.length;
    }
}

Let's test it.

Main.java

    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        byte[] b02 = { 1, 2, 3 };
        Map<byte[], String> map = new TreeMap<>(new ByteArrayComparator());
        map.put(b01, "OK");
        System.out.println(map.get(b01));
        System.out.println(map.get(b02));
    }

Result is···

OK
OK

Maybe it's okay.

Finally

It was confirmed that ByteArrayWrapper does not need hashCode in TreeMap, but usually it is better to implement both if you make it anyway. (1/18 postscript) I changed the argument of the constructor from byte [] to byte ... (variadic argument). Also added equals (byte [] other).

ByteArrayWrapper.java

import java.util.Arrays;

public class ByteArrayWrapper implements Comparable<ByteArrayWrapper> {
    private byte[] data;

    public ByteArrayWrapper(byte... data) {
        this.data = data.clone();
    }

    public boolean equals(Object other) {
        if (other instanceof ByteArrayWrapper) {
            return equals(((ByteArrayWrapper) other).data);
        }
        return false;
    }
    
    public boolean equals(byte[] other) {
        return Arrays.equals(data, other);
    }
    
    public int hashCode() {
        return Arrays.hashCode(data);
    }

    public int compareTo(ByteArrayWrapper that) {
        int n = Math.min(this.data.length, that.data.length);
        for (int i = 0; i < n; i++) {
            int cmp = Byte.compare(this.data[i], that.data[i]);
            if (cmp != 0)
                return cmp;
        }
        return this.data.length - that.data.length;
    }
}

Main.java

    public static void main(String[] args) {
        byte[] b01 = { 1, 2, 3 };
        ByteArrayWrapper w01 = new ByteArrayWrapper(b01);
        ByteArrayWrapper w02 = new ByteArrayWrapper((byte)1, (byte)2, (byte)3);
        Map<ByteArrayWrapper, String> map1 = new HashMap<>();
        map1.put(w01, "OK");
        Map<ByteArrayWrapper, String> map2 = new TreeMap<>();
        map2.put(w01, "OK");
        System.out.println(map1.get(w01));
        System.out.println(map1.get(w02));
        System.out.println(map2.get(w01));
        System.out.println(map2.get(w02));
    }

When I test ...

OK
OK
OK
OK