java - 按数字顺序对字节数组进行排序

Question

我有一个使用 byte[] 作为键的持久映射。访问是通过带有任意比较器的迭代器进行的。由于字节数组表示带符号的数值(整数或小数)，我想对 byte[] 进行数字排序，使得 1 后面的数字是 2，而不是 11。

该数组是使用 UTF8 从数字的字符串表示形式编码的。

我一直在寻找可靠的、线程安全的代码来执行此操作，例如 Guava 比较器 SignedBytes.lexicographicalComparator，但用于数字排序。

这样的东西存在吗？

如果没有，是否有一种快速可靠的方法可以做到这一点？

为了使用例更加清晰:我正在使用 Leveldb 的 Java 端口。 Leveldb 将键和值存储为 byte[]。它支持对键进行范围查询，但默认比较器是字典顺序的，因此当值表示数字时，它会产生较差的范围查询结果。

我不想先转换回 String，然后再转换为 Int(或 Double)，因为比较方法将被调用数十亿次。

Answer 1

在我看来，您只想使用排序的 map 。 Java 有几个(ConcurrentSkipListMap 和 TreeMap 是最大的两个)。这个问题似乎有点模糊，特别是关于线程安全点(你有人能够同时进行写入、读写和可迭代更新等吗？)。如果您只需要同时写入 map ，我不会浪费时间在 ConcurrentSkipListMap 或 java.util.Collections.synchronizedMap(java.util.Map) 之类的包装器上，而只会在您需要的地方执行同步块(synchronized block)它在写入的方法中。

如果你写了很多并且只需要偶尔获取一个迭代器，请尝试使用常规的 HashMap，然后返回迭代器的方法可以简单地使用比较器创建一个新的 SortedMap，并将数据推送到新 map ，但这很昂贵，因此只有在您确实不经常读取、没有那么多数据并且可以忍受读取操作的情况下才会这样做。即便如此，这也不是一个非常昂贵的行动。

在我看来，您确实想要一个可以做到这一点的比较？可比性决定了 11 还是 2 先出现。因为它是一个字节数组，所以你会有这样的东西(请注意，我还没有测试过这个，我假设你使用的是大端):

class NumberComparator implements Comparator<byte[]> {
    /*
     * (non-Javadoc)
     * 
     * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
     */
    @Override
    public int compare(byte[] o1, byte[] o2) {
        if (o1 == null) {
            if (o2 == null)
                return 0;
            return -1;
        }

        if (o2 == null)
            return 1;

        // I'm going to cheat and assume that if the lengths aren't the same, you didn't pad... but really, the
        // lengths should always be the same because you shouldn't allow pushing doubles and ints
        if (o1.length != o2.length) {
            return o1.length - o2.length;
        }
        if (o1.length == 0)
            return 0;

        // For the sake of things, I'm assuming you've taken care of endianness and that we're using big-endian
        // We're an int (note that you can make the size of an int a constant)
        if (o1.length == Integer.SIZE >> 3) {
            int o1Integer = 0;
            int o2Integer = 0;

            int shift = 0;
            for (int i = 0; i < o1.length; i++) {
                o1Integer |= ((o1[i] & 0xFF) << shift);
                o2Integer |= ((o2[i] & 0xFF) << shift);
                shift += 0x8;
            }

            return Integer.compare(o1Integer, o2Integer);
        }
        // We're a double (note that you can make the size of a double a constant)
        else if (o1.length == Double.SIZE >> 3) {
            long o1Bits = 0L;
            long o2Bits = 0L;

            int shift = 0;
            for (int i = 0; i < o1.length; i++) {
                o1Bits |= ((o1[i] & 0xFFL) << shift);
                o2Bits |= ((o2[i] & 0xFFL) << shift);
            }

            return Double.compare(Double.longBitsToDouble(o1Bits), Double.longBitsToDouble(o2Bits));
        }

        // Who knows what we are...but again, we're assuming big-endian
        final boolean o1Neg = ((o1[0] & 0x80) == 0) ? false : true;
        final boolean o2Neg = ((o2[0] & 0x80) == 0) ? false : true;
        // o1 is negative and o2 is positive
        if (o1Neg && !o2Neg)
            return -1;
        // o1 is positive and o2 is negative
        if (!o1Neg && o2Neg)
            return 1;

        // o1 is positive and o2 is positive
        if (!o1Neg && !o2Neg)
            for (int pos = 0; pos < o1.length; pos++) {
                int comp = (o1[pos] & 0xFF) - (o2[pos] & 0xFF);
                if (comp != 0)
                    return comp;
            }
        // TODO I leave handling if both are negatives to the reader

        // Everything was the same!  We are equal :-)
        return 0;
    }
}

<小时/>

编辑

好吧，经过一番澄清后，您的比较器应该更像是:

class NumberStringComparator implements Comparator<byte[]> {
    private static final Pattern leftZeroPadding = Pattern.compile("^[\\-\\+]?0+");
    private static final Pattern rightZeroPadding=Pattern.compile("0+$");

    /*
     * (non-Javadoc)
     * 
     * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
     */
    @Override
    public int compare(byte[] o1, byte[] o2) {
        if (o1 == null) {
            if (o2 == null)
                return 0;
            return -1;
        }

        if (o2 == null)
            return 1;

        String o1String = new String(o1, "UTF-8").trim();
        String o2String = new String(o2, "UTF-8").trim();

        final boolean o1Neg = o1String.charAt(0) == '-';
        final boolean o2Neg = o2String.charAt(0) == '-';
        // o1 is negative and o2 is positive
        if (o1Neg && !o2Neg)
            return -1;
        // o1 is positive and o2 is negative
        if (!o1Neg && o2Neg)
            return 1;

        String o1WithoutZeroPadding = leftZeroPadding.matcher(o1String).replaceAll("");
        String o2WithoutZeroPadding = leftZeroPadding.matcher(o2String).replaceAll("");
        // We're the same thing
        if (o1WithoutZeroPadding.equals(o2WithoutZeroPadding))
            return 0;

        int o1Dec = o1WithoutZeroPadding.indexOf('.');
        int o2Dec = o2WithoutZeroPadding.indexOf('.');

        final int o1LeftLength;
        final int o2LeftLength;
        final String o1Left;
        final String o2Left;
        final String o1Right;
        final String o2Right;

        if (o1Dec == -1) {
            o1LeftLength = o1WithoutZeroPadding.length();
            o1Left = o1WithoutZeroPadding;
            o1Right = "";
        } else {
            o1LeftLength = o1Dec;
            if (o1LeftLength == 0)
                o1Left = "";
            else
                o1Left = o1WithoutZeroPadding.substring(0, o1Dec);
            if (o1Dec + 1 == o1LeftLength) {
                o1Right = "";
            } else {
                o1Right = rightZeroPadding.matcher(o1WithoutZeroPadding.substring(o1Dec + 1)).replaceAll("");
            }
        }
        if (o2Dec == -1) {
            o2LeftLength = o2WithoutZeroPadding.length();
            o2Left = o2WithoutZeroPadding;
            o2Right = "";
        } else {
            o2LeftLength = o2Dec;
            if (o2LeftLength == 0)
                o2Left = "";
            else
                o2Left = o2WithoutZeroPadding.substring(0, o2Dec);
            if (o2Dec + 1 == o2LeftLength) {
                o2Right = "";
            } else {
                o2Right = rightZeroPadding.matcher(o2WithoutZeroPadding.substring(o2Dec + 1)).replaceAll("");
            }
        }

        // If o1 is shorter than o2 (left of the decimal)...
        if (o1LeftLength < o2LeftLength) {
            // and we're negative numbers...
            if (o1Neg)
                // Than o1 is closer to 0
                return 1;
            // Than o1 is farther from 0
            return -1;
        }

        // If o2 is shorter than o1 (left of the decimal)...
        if (o1LeftLength > o2LeftLength) {
            // and we're negative numbers...
            if (o2Neg)
                // Than o2 is closer to 0
                return -1;
            // Than o2 is farther from 0
            return -1;
        }

        // Left of the decimal is the same length...
        // March through the left
        char o1Char;
        char o2Char;
        for (int pos = 0; pos < o1LeftLength; pos++) {
            o1Char = o1Left.charAt(pos);
            o2Char = o2Left.charAt(pos);
            if (o1Char != o2Char) {
                // Lower digits in o1Char make this negative, higher make it positive...
                return o1Char - o2Char;
            }
        }

        // Okay... everything was the same to the left... check the right
        int rightLength = Math.min(o1Right.length(), o2Right.length());
        for (int pos = 0; pos < rightLength; pos++) {
            o1Char = o1Right.charAt(pos);
            o2Char = o2Right.charAt(pos);
            if (o1Char != o2Char) {
                int multiplier = 1;
                if (o1Neg)
                    multiplier = -1;
                // Lower digits in o1Char make this negative, higher make it positive...
                return (o1Char - o2Char) * multiplier;
            }
        }

        // Everything was the same... now it comes down to this... if o1's right side is bigger, it is the bigger of
        // the two numbers
        int multiplier = 1;
        if (o1Neg)
            multiplier = -1;
        return (o1Right.length() - o2Right.length()) * multiplier;
    }
}