Java Comparator for byte array (lexicographic)

Question

I have a hashmap with byte[] keys. I'd like to sort it through a TreeMap.

What is the most effective way to implement the comparator for lexicographic order?

Solution 1

Using Guava, you can use either of:

• UnsignedBytes.lexicographicalComparator()
• SignedBytes.lexicographicalComparator()

The UnsignedBytes comparator appears to have an optimized form using Unsafe that it uses if it can. Comments in the code indicate that it may be at least twice as fast as a normal Java implementation.

Solution 2

Found this nice piece of code in Apache Hbase:

    public int compare(byte[] left, byte[] right) {
        for (int i = 0, j = 0; i < left.length && j < right.length; i++, j++) {
            int a = (left[i] & 0xff);
            int b = (right[j] & 0xff);
            if (a != b) {
                return a - b;
            }
        }
        return left.length - right.length;
    }

Comments

[ColinD]

This is basically what the non-optimized version of Guava's UnsignedBytes.lexicographicalComparator() does.

[Deepak]

do we have the solution in "Java",if so please post a working example.

[marcorossi]

As ColinD says in the comment to my answer, my solution is the same as the non optimized one in Guava. So you can straight use mine, which is a working example, or follow ColinD's links.

[Lukas Eder]

Hmm, why did they use i and j, when one variable would've been sufficient. Also, storing int length = Math.min(left.length, right.length) and comparing i < length would improve this for large arrays

[marcorossi]

you would expect that the length field of the array would be as expensive