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.

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

Recommended Posts

How to use an array for a TreeMap key
How to use an array for HashMap keys
How to create pagination for a "kaminari" array
[Java] How to turn a two-dimensional array with an extended for statement
How to make a judgment method to search for an arbitrary character in an array
How to make a Java array
How to use a foreign key with FactoryBot ~ Another solution
How to change a string in an array to a number in Ruby
How to output array values without using a for statement
How to use binding.pry for view files
How to add a new hash / array
How to create a Maven repository for 2020
[Ruby] How to use slice for beginners
[Java] How to search for a value in an array (or list) with the contains method
[For Rails beginners] Summary of how to use RSpec (get an overview)
[Java] [For beginners] How to insert elements directly in a 2D array
How to create a database for H2 Database anywhere
How to make a lightweight JRE for distribution
How to generate a primary key using @GeneratedValue
[Rails] How to use Gem'rails-i18n' for Japanese support
How to use nginx-ingress-controller with Docker for Mac
[For super beginners] How to use autofocus: true
How to use Map
How to use rbenv
How to use letter_opener_web
How to use with_option
How to use fields_for
How to use java.util.logging
How to use map
How to use collection_select
How to use Twitter4J
How to use active_hash! !!
How to use MapStruct
How to use hidden_field_tag
How to use TreeSet
[How to use label]
How to use identity
How to use hashes
How to use JUnit 5
How to use Dozer.mapper
How to use Gradle
How to use org.immutables
How to use java.util.stream.Collector
How to use VisualVM
How to use Map
[Java] How to convert one element of a String type array to an Int type
[Rails] How to create a signed URL for CloudFront
How to write a unit test for Spring Boot 2
How to write to apply gem Pagy (pagination) to an array
[Spring Boot] How to create a project (for beginners)
How to output standard from an array with forEach
How to use Truth (assertion library for Java / Android)
[For those who create portfolios] How to use font-awesome-rails
How to convert a file to a byte array in Java
How to write an external reference key in FactoryBot
How to make a mod for Slay the Spire
How to use GitHub for super beginners (team development)
How to use a structure with variable length array or bit field in Ruby-FFI
How to create an application
[Java] How to use Map
[Java] How to use Map