Java比较器用于字节数组（词典顺序）

Question

我有一个使用byte[]作为键的哈希映射表，我想通过TreeMap对其进行排序。

实现按字典顺序比较器的最有效方法是什么？

- marcorossi

Answer 1

使用Guava，你可以使用以下任一方法：

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

UnsignedBytes比较器似乎采用了使用Unsafe的优化形式（如果可能），代码中的注释表明它可能比普通Java实现快至少两倍。

- ColinD

---

我们是否有“Java”的解决方案？如果有，请发布一个可工作的示例。 - Deepak

正如ColinD在评论中所说，我的解决方案与Guava中的非优化解决方案相同。因此，您可以直接使用我的解决方案，它是一个可工作的示例，或者按照ColinD提供的链接进行操作。 - marcorossi

Answer 2

我在 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;
    }

- marcorossi

---

这基本上就是Guava的UnsignedBytes.lexicographicalComparator()非优化版本所做的事情。 - ColinD

嗯，为什么他们使用了 i 和 j，一个变量就足够了。此外，存储 int length = Math.min(left.length, right.length) 并比较 i < length 可以改善大数组的情况。 - Lukas Eder

你会期望数组的长度字段会很昂贵。 - marcorossi

Answer 3

我假设问题只在于“字节与字节”的比较。处理数组很简单，所以我不会涉及它。关于字节与字节的比较，我的第一个想法是这样的：

public class ByteComparator implements Comparator<byte> {
  public int compare(byte b1, byte b2) {
    return new Byte(b1).compareTo(b2);
  }
}

但这不是按字典顺序排列的：0xFF（-1的有符号字节）将被认为比0x00小，而按字典顺序它实际上更大。我认为这应该解决问题：

public class ByteComparator implements Comparator<byte> {
  public int compare(byte b1, byte b2) {
    // convert to unsigned bytes (0 to 255) before comparing them.
    int i1 = b1 < 0 ? 256 + b1 : b1;
    int i2 = b2 < 0 ? 256 + b2 : b2;
    return i2 - i1;
  }
}

可能在Apache的commons-lang或commons-math库中有做这个的东西，但我不是很清楚。

- Julius Musseau

---

Java中已经内置了Byte.comparator，无需自行实现。 - KenHuffman