使用字节数组作为Map键

Question

您认为使用字节数组作为Map键存在问题吗？我也可以使用new String(byte[])并通过String进行哈希，但使用byte[]更加直接。

- shikhar

Answer 1

只要您只需要键的引用相等性，那么就没有问题——数组不以您想要的方式实现“值相等性”。例如：

byte[] array1 = new byte[1];
byte[] array2 = new byte[1];

System.out.println(array1.equals(array2));
System.out.println(array1.hashCode());
System.out.println(array2.hashCode());

打印出类似以下内容：

false
1671711
11394033

（实际数字并不重要，它们不同的事实很重要。）

假设您真正想要平等，我建议您创建自己的包装器，其中包含一个byte[]并适当实现相等性和哈希码生成：

public final class ByteArrayWrapper
{
    private final byte[] data;

    public ByteArrayWrapper(byte[] data)
    {
        if (data == null)
        {
            throw new NullPointerException();
        }
        this.data = data;
    }

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

    @Override
    public int hashCode()
    {
        return Arrays.hashCode(data);
    }
}

请注意，如果您在使用ByteArrayWrapper作为HashMap等中的键后更改了字节数组中的值，则在查找键时会出现问题...如果您知道您不会更改字节数组的内容，那么您可以在ByteArrayWrapper构造函数中复制数据，但显然这将浪费性能。

编辑：如评论中所述，您也可以使用ByteBuffer（特别是其ByteBuffer#wrap(byte[])方法）。我不知道是否真的是正确的做法，因为ByteBuffer具有您不需要的所有额外功能，但这是一种选择。

- Jon Skeet

---

@dfa： "instanceof"测试处理空值情况。 - Jon Skeet

可以将以下内容添加到包装器实现中：

1. 在构造函数中复制byte[]，确保该对象是不可变的，这意味着您的密钥哈希码不会随时间而改变，从而避免了潜在的危险。
2. 预先计算并存储哈希码一次（假设速度比存储开销更重要）。

- Adamski

@Adamski：我在答案的结尾提到了复制的可能性。在某些情况下，这是正确的做法，但在其他情况下则不然。我可能会想把它作为一个选项（可能是静态方法而不是构造函数——copyOf和wrapperAround）。请注意，没有复制，您可以在第一次获取哈希并检查相等之前更改基础数组，这在某些情况下可能很有用。 - Jon Skeet

抱歉 - 对不起Jon；我错过了你回复的那部分。 - Adamski

只是想指出，java.nio.ByteBuffer类基本上可以完成您的包装器所做的一切，尽管有一个相同的警告，即只有在字节数组的内容不会更改时才应使用它。您可能希望修改您的答案以提及它。 - Ed Anuff

Answer 2

问题在于byte[]使用对象标识符来进行equals和hashCode比较。

byte[] b1 = {1, 2, 3}
byte[] b2 = {1, 2, 3}

在 HashMap 中无法匹配。我看到三个选项：

1. 将其包装在一个 String 中，但是你必须小心编码问题（你需要确保字节 -> 字符串 -> 字节给出相同的字节）。
2. 使用 List<Byte>（可能会占用大量内存）。
3. 编写自己的包装类，并编写 hashCode 和 equals 方法来使用字节数组的内容。

- Kathy Van Stone

---

我通过使用十六进制编码解决了字符串包装问题。您也可以选择使用Base64编码。 - metadaddy

包装/处理类选项很简单，应该非常易读。 - ZX9

Answer 3

我们可以使用 ByteBuffer 来实现这个（它基本上是带有比较器的 byte[] 包装器）。

HashMap<ByteBuffer, byte[]> kvs = new HashMap<ByteBuffer, byte[]>();
byte[] k1 = new byte[]{1,2 ,3};
byte[] k2 = new byte[]{1,2 ,3};
byte[] val = new byte[]{12,23,43,4};

kvs.put(ByteBuffer.wrap(k1), val);
System.out.println(kvs.containsKey(ByteBuffer.wrap(k2)));

将打印

true

- byte_array

---

+1 给最轻量级的字节数组包装器（我想是这样...） - Nicholas

使用ByteBuffer.wrap()方法可以正常运行，但是请注意，如果ByteBuffer的内容是通过多次put()调用创建的组合键字节数组，则需要小心。在这种情况下，最后一个put()调用必须跟着一个rewind()调用-否则，即使基础字节数组包含不同的数据，equals()方法也会返回true。 - RenniePet

这是一个不错的解决方案，但如果你想序列化地图（就像我的情况一样），你不能使用这种方法。 - 501 - not implemented

请注意：由于缓冲区哈希码是内容相关的，除非知道它们的内容不会更改，否则不建议将缓冲区用作哈希映射或类似数据结构中的键。 - Luatic

你应该使用ByteBuffer.wrap(k1.clone())来获取数组的防御性副本。否则，如果有人更改了数组，将会发生糟糕的事情。在调试器中查看，与字符串相比，ByteBuffer具有许多内部状态，因此从内存开销的角度来看，这似乎并不是一种轻量级的解决方案。 - simbo1905

Answer 4

您可以使用 java.math.BigInteger。它具有BigInteger(byte[] val)构造函数。它是一个引用类型，因此可以用作hashtable的键。而且，.equals()和.hashCode()的定义与相应的整数数字相同，这意味着BigInteger具有与byte[]数组一致的equals语义。

- Artem Oboturov

---

听起来挺吸引人，但是这是错误的。因为两个仅在前导零元素上有所不同的数组（比如 {0,100} 和 {100}）将会给出相同的 BigInteger。 - leonbloy

@leonbloy 说得好。可能有一个解决方法：通过添加一些固定的非空前导字节常量，但这将需要在 BigInteger 构造函数周围编写一个包装器，并将我们带回到 Jon 的响应。 - Artem Oboturov

@vinchan的回复更为恰当，因为这样就不会出现零前导字节问题。 - Artem Oboturov

Answer 5

我很惊讶答案没有指出最简单的替代方案。

是的，无法使用HashMap，但你可以使用SortedMap作为替代方案。唯一需要做的是编写一个比较器来比较数组。它不像HashMap那样高效，但如果你需要一个简单的替代方案，这里有一个（如果你想隐藏实现，可以将SortedMap替换为Map）：

 private SortedMap<int[], String>  testMap = new TreeMap<>(new ArrayComparator());

 private class ArrayComparator implements Comparator<int[]> {
    @Override
    public int compare(int[] o1, int[] o2) {
      int result = 0;
      int maxLength = Math.max(o1.length, o2.length);
      for (int index = 0; index < maxLength; index++) {
        int o1Value = index < o1.length ? o1[index] : 0;
        int o2Value = index < o2.length ? o2[index] : 0;
        int cmp     = Integer.compare(o1Value, o2Value);
        if (cmp != 0) {
          result = cmp;
          break;
        }
      }
      return result;
    }
  }

这个实现可以调整适用于其他数组，唯一需要注意的是相等的数组（长度相等，并且成员相等）必须返回0，并且有一个确定的顺序。

- Thorsten S.

---

很好的解决方案，巨大的好处是不会创建额外的对象。如果数组长度不同但最长的只有0在短的后面，则存在非常小的错误。此外，管理顺序可能有助于加快树遍历速度。+1！ - jmspaggi

Answer 6

这里有一个使用TreeMap、Comparator接口和java方法java.util.Arrays.equals(byte[], byte[])的解决方案;

注意：使用此方法时，映射中的排序顺序不相关。

SortedMap<byte[], String> testMap = new TreeMap<>(new ArrayComparator());

static class ArrayComparator implements Comparator<byte[]> {
    @Override
    public int compare(byte[] byteArray1, byte[] byteArray2) {

        int result = 0;

        boolean areEquals = Arrays.equals(byteArray1, byteArray2);

        if (!areEquals) {
            result = -1;
        }

        return result;
    }
}

- matdev

Answer 7

你应该创建一个类，例如ByteArrKey，并重载hashcode和equal方法，记住它们之间的合同。这样可以让你更加灵活，因为你可以跳过在字节数组末尾添加的0条目，特别是如果你只复制了另一个字节缓冲区的一部分。这样，你就可以决定两个对象应该如何相等。

- Milind Patil

Answer 8

我认为在Java中，数组并不一定直观地实现了hashCode()和equals(Object)方法。也就是说，两个相同的字节数组不一定共享相同的哈希码，并且它们也不一定声称相等。如果没有这两个特性，你的HashMap将会表现出意外的行为。

因此，我建议不要在HashMap中使用byte[]作为键。

- Adam Paynter

---

我想我的措辞有些不准确。我考虑的是同一个字节数组既用于插入哈希表，又用于从哈希表检索的情况。在这种情况下，“两个”字节数组是相同的，并且共享相同的哈希码。 - Adam Paynter

Answer 9

你也可以将 byte[] 转换为“安全”的字符串，例如 Base32 或 Base64：

byte[] keyValue = new byte[] {…};
String key = javax.xml.bind.DatatypeConverter.printBase64Binary(keyValue);

当然，以上还有许多变体，例如：

String key = org.apache.commons.codec.binary.Base64.encodeBase64(keyValue);

- Christof R

Answer 10

其他答案没有指出并非所有的byte[]都可以转换为唯一的String。我曾经陷入这个陷阱，使用new String(byteArray)作为映射的键，结果发现许多负字节被映射到相同的字符串上。以下是一个演示该问题的测试：

    @Test
    public void testByteAsStringMap() throws Exception {
        HashMap<String, byte[]> kvs = new HashMap<>();
        IntStream.range(Byte.MIN_VALUE, Byte.MAX_VALUE).forEach(b->{
            byte[] key = {(byte)b};
            byte[] value = {(byte)b};
            kvs.put(new String(key), value);
        });
        Assert.assertEquals(255, kvs.size());
    }

将会抛出以下异常:

java.lang.AssertionError: Expected :255 Actual :128

这是因为一个 String 是一系列字符代码点，而从 byte[] 进行的任何转换都基于某些字节编码。在上面的情况下，平台默认编码恰好将许多负字节映射到相同的字符。关于 String 的另一个事实是它始终获取并给出其内部状态的副本。如果原始字节来自被复制的 String，那么将其包装为 String 以将其用作映射键将生成第二个副本。这可能会产生很多垃圾，这是可以避免的。

这里有一个很好的答案建议使用java.nio.ByteBuffer和ByteBuffer.wrap(b)。问题在于byte[]是可变的，它不会复制，因此您必须小心地使用ByteBuffer.wrap(b.clone())来获取传递给您的任何数组的防御性副本，否则您的映射键将被破坏。如果您在调试器中查看具有ByteBuffer键的映射的结果，则会发现缓冲区具有许多内部引用，旨在跟踪从每个缓冲区读取和写入。因此，这些对象比简单的String包装要重得多。最后，即使字符串保存了更多状态，但也不需要。在我的调试器中查看它时，它将字符存储为两个字节的UTF16数组，并且还存储了四个字节的哈希码。

我首选的方法是让Lombok在编译时生成样板代码，以创建轻量级的字节数组包装器，不存储其他状态：

import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.ToString;

@ToString
@EqualsAndHashCode
@Data(staticConstructor="of")
class ByteSequence {
    final byte[] bytes;
}

接下来进行的测试检查所有可能的字节是否映射到唯一的字符串：

    byte[] bytes(int b){
        return new byte[]{(byte)b};
    }

    @Test
    public void testByteSequenceAsMapKey() {
        HashMap<ByteSequence, byte[]> kvs = new HashMap<>();
        IntStream.range(Byte.MIN_VALUE, Byte.MAX_VALUE).forEach(b->{
            byte[] key = {(byte)b};
            byte[] value = {(byte)b};
            kvs.put(ByteSequence.of(key), value);
        });
        Assert.assertEquals(255, kvs.size());
        byte[] empty = {};
        kvs.put(ByteSequence.of(empty), bytes(1));
        Assert.assertArrayEquals(bytes(1), kvs.get(ByteSequence.of(empty)));
    }

你不必担心获取等式和哈希码逻辑是否正确，因为它由Lombok提供，其中使用了Arrays.deepEquals，该方法在https://projectlombok.org/features/EqualsAndHashCode中有记录。请注意，Lombok不是运行时依赖项，只是编译时依赖项，您可以安装开源插件到您的IDE中，以便您的IDE“看到”所有生成的样板方法。

使用此实现，您仍然需要考虑字节的可变性。如果有人传递给您可能被改变的byte[]，您应该使用clone()进行防御性复制：

kvs.put(ByteSequence.of(key.clone()), value);

- simbo1905