Do you see any problem with using a byte array as Map key? I could also do new String(byte[])
and hash by String
but it is more straightforward to use byte[]
.
13 Answers
It's okay so long as you only want reference equality for your key - arrays don't implement "value equality" in the way that you'd probably want. For example:
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());
prints something like:
false
1671711
11394033
(The actual numbers are irrelevant; the fact that they're different is important.)
Assuming you actually want equality, I suggest you create your own wrapper which contains a byte[]
and implements equality and hash code generation appropriately:
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);
}
}
Note that if you change the values within the byte array after using the ByteArrayWrapper
, as a key in a HashMap
(etc) you'll have problems looking up the key again... you could take a copy of the data in the ByteArrayWrapper
constructor if you want, but obviously that will be a waste of performance if you know you won't be changing the contents of the byte array.
EDIT: As mentioned in the comments, you could also use ByteBuffer
for this (in particular, its ByteBuffer#wrap(byte[])
method). I don't know whether it's really the right thing, given all the extra abilities that ByteBuffer
s have which you don't need, but it's an option.
-
-
4A couple of other things you could add to the wrapper implementation: 1. Take a copy of the byte[] on construction therefore guaranteeing that the object is immutable, meaning there's no danger your key's hash code will change over time. 2. Pre-compute and store the hash code once (assuming speed is more important than storage overhead).– AdamskiCommented Jun 29, 2009 at 13:35
-
2@Adamski: I mention the possibility of copying at the end of the answer. In some cases it's the right thing to do, but not in others. I'd probably want to make it an option (possibly static methods instead of constructors - copyOf and wrapperAround). Note that without copying, you can change the underlying array until you first take the hash and check for equality, which could be useful in some situations. Commented Jun 29, 2009 at 13:41
-
-
3Just wanted to point out that the java.nio.ByteBuffer class essentially does everything your wrapper does, although with the same caveat that you should only use it if the contents of the byte array won't be changing. You might want to amend your answer to make mention of it.– Ed AnuffCommented Nov 28, 2010 at 19:41
The problem is that byte[]
uses object identity for equals
and hashCode
, so that
byte[] b1 = {1, 2, 3}
byte[] b2 = {1, 2, 3}
will not match in a HashMap
. I see three options:
- Wrapping in a
String
, but then you have to be careful about encoding issues (you need to make certain that the byte -> String -> byte gives you the same bytes). - Use
List<Byte>
(can be expensive in memory). - Do your own wrapping class, writing
hashCode
andequals
to use the contents of the byte array.
-
4I solved the string-wrapping problem by using hex-encoding. You could alternatively use base64 encoding. Commented Apr 8, 2012 at 8:52
-
1The wrapping/handling class option is straightforward and should be very readable.– ZX9Commented Mar 7, 2016 at 19:51
We can use ByteBuffer for this (This is basically the byte[] wrapper with a comparator)
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)));
will print
true
-
2
-
8This works OK with ByteBuffer.wrap(), but be careful if the ByteBuffer's contents have been created using a couple of put() calls to create a composite key byte array. In this case the last put() call must be followed by a rewind() call - otherwise equals() returns true even when the underlying byte arrays contain different data. Commented May 30, 2015 at 8:46
-
This would be a nice solution, but if you want to serialize the map (like in my case) you can't use this approach. Commented May 18, 2016 at 16:15
-
Note that : "Because buffer hash codes are content-dependent, it is inadvisable to use buffers as keys in hash maps or similar data structures unless it is known that their contents will not change. " (docs.oracle.com/javase/7/docs/api/java/nio/…)– LuaticCommented May 12, 2019 at 9:23
-
You should
ByteBuffer.wrap(k1.clone())
to take a defensive copy of the array. If not if anyone does change the array bad things will happen. Looking in a debugger a ByteBuffer has lots of internal state compared to a String so it looks like this isn't really a lightweight solution in terms of memory overhead. Commented Nov 18, 2019 at 21:25
You could use java.math.BigInteger
. It has a BigInteger(byte[] val)
constructor. It's a reference type, so could be used as a key for hashtable. And .equals()
and .hashCode()
are defined as for respective integer numbers, which means BigInteger has consistent equals semantics as byte[] array.
-
19Sounds atractive, but it's wrong, as two arrays that differ only in leading zero elements (say,
{0,100}
and{100}
) will give the same BigInteger– leonbloyCommented Nov 14, 2013 at 23:55 -
Good point @leonbloy. There could be a workaround: by adding a some fixed non-null leading byte constant to it, but it will require to write a wrapper around the BigInteger constructor and will return us back to to Jon's response. Commented Nov 15, 2013 at 6:08
-
@vinchan's response would be more appropriate as there would no zero-leading byte problem. Commented Nov 15, 2013 at 6:33
I am very surprised that the answers are not pointing out the most simple alternative.
Yes, it is not possible to use a HashMap, but nobody prevents you from using a SortedMap as alternative. The only thing is to write a Comparator which needs to compare the arrays. It is not as performant as a HashMap, but if you want a simple alternative, here you go (you can replace SortedMap with Map if you want to hide the implementation):
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;
}
}
This implementation can be adjusted for other arrays, the only thing you must be aware of is that equal arrays (= equal length with equal members) must return 0 and that you have a determistic order
-
Nice solution with the huge benefit of not creating additional objects. Very small bug if arrays are not the same length but longest one only have 0 after shorter one length. Also, managing the order probably helps to speed up on the tree traversal. +1!– jmspaggiCommented Apr 8, 2019 at 1:05
I believe that arrays in Java do not necessarily implement the hashCode()
and equals(Object)
methods intuitively. That is, two identical byte arrays will not necessarily share the same hash code and they will not necessarily claim to be equal. Without these two traits, your HashMap will behave unexpectedly.
Therefore, I recommend against using byte[]
as keys in a HashMap.
-
I suppose my wording was a bit off. I was accounting for the situation where THE SAME byte array is being used both for insertion into the hash map AND for retrieval from the hash map. In that case, "both" byte arrays are identical AND share the same hash code. Commented Jun 29, 2009 at 13:58
You should use create a class somthing like ByteArrKey and overload hashcode and equal methods, remember the contract between them.
This will give you greater flexibility as you can skip 0 entries that are appended at the end of byte array, specially if you copy only some part form the other byte buffer.
This way you will decide how both objects SHOULD be equal.
Here is a solution using TreeMap, Comparator interface and java method java.util.Arrays.equals(byte[], byte[]);
NOTE: The ordering in the map is not relevant with this method
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;
}
}
I see problems since you should use Arrays.equals and Array.hashCode, in place of default array implementations
Arrays.toString(bytes)
-
1Could be used, but not very efficient. If you want to go this way you may want to use base64 encoding instead. Commented Mar 5, 2015 at 1:23
You could also convert the byte[] to a 'safe' string using Base32 or Base64, for example:
byte[] keyValue = new byte[] {…};
String key = javax.xml.bind.DatatypeConverter.printBase64Binary(keyValue);
of course there are many variants of the above, like:
String key = org.apache.commons.codec.binary.Base64.encodeBase64(keyValue);
Also, We can create own custom ByteHashMap like this,
ByteHashMap byteMap = new ByteHashMap();
byteMap.put(keybyteArray,valueByteArray);
Here is the complete implementation
public class ByteHashMap implements Map<byte[], byte[]>, Cloneable,
Serializable {
private Map<ByteArrayWrapper, byte[]> internalMap = new HashMap<ByteArrayWrapper, byte[]>();
public void clear() {
internalMap.clear();
}
public boolean containsKey(Object key) {
if (key instanceof byte[])
return internalMap.containsKey(new ByteArrayWrapper((byte[]) key));
return internalMap.containsKey(key);
}
public boolean containsValue(Object value) {
return internalMap.containsValue(value);
}
public Set<java.util.Map.Entry<byte[], byte[]>> entrySet() {
Iterator<java.util.Map.Entry<ByteArrayWrapper, byte[]>> iterator = internalMap
.entrySet().iterator();
HashSet<Entry<byte[], byte[]>> hashSet = new HashSet<java.util.Map.Entry<byte[], byte[]>>();
while (iterator.hasNext()) {
Entry<ByteArrayWrapper, byte[]> entry = iterator.next();
hashSet.add(new ByteEntry(entry.getKey().data, entry
.getValue()));
}
return hashSet;
}
public byte[] get(Object key) {
if (key instanceof byte[])
return internalMap.get(new ByteArrayWrapper((byte[]) key));
return internalMap.get(key);
}
public boolean isEmpty() {
return internalMap.isEmpty();
}
public Set<byte[]> keySet() {
Set<byte[]> keySet = new HashSet<byte[]>();
Iterator<ByteArrayWrapper> iterator = internalMap.keySet().iterator();
while (iterator.hasNext()) {
keySet.add(iterator.next().data);
}
return keySet;
}
public byte[] put(byte[] key, byte[] value) {
return internalMap.put(new ByteArrayWrapper(key), value);
}
@SuppressWarnings("unchecked")
public void putAll(Map<? extends byte[], ? extends byte[]> m) {
Iterator<?> iterator = m.entrySet().iterator();
while (iterator.hasNext()) {
Entry<? extends byte[], ? extends byte[]> next = (Entry<? extends byte[], ? extends byte[]>) iterator
.next();
internalMap.put(new ByteArrayWrapper(next.getKey()), next
.getValue());
}
}
public byte[] remove(Object key) {
if (key instanceof byte[])
return internalMap.remove(new ByteArrayWrapper((byte[]) key));
return internalMap.remove(key);
}
public int size() {
return internalMap.size();
}
public Collection<byte[]> values() {
return internalMap.values();
}
private final class ByteArrayWrapper {
private final byte[] data;
public ByteArrayWrapper(byte[] data) {
if (data == null) {
throw new NullPointerException();
}
this.data = data;
}
public boolean equals(Object other) {
if (!(other instanceof ByteArrayWrapper)) {
return false;
}
return Arrays.equals(data, ((ByteArrayWrapper) other).data);
}
public int hashCode() {
return Arrays.hashCode(data);
}
}
private final class ByteEntry implements Entry<byte[], byte[]> {
private byte[] value;
private byte[] key;
public ByteEntry(byte[] key, byte[] value) {
this.key = key;
this.value = value;
}
public byte[] getKey() {
return this.key;
}
public byte[] getValue() {
return this.value;
}
public byte[] setValue(byte[] value) {
this.value = value;
return value;
}
}
}
Other answers have not pointed out that not all byte[]
covert into unique String
. I fell into this trap doing new String(byteArray)
as keys to a map only to find that many negative bytes are mapped to the same string. Here is a test that demonstrates that problem:
@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());
}
It will throw:
java.lang.AssertionError: Expected :255 Actual :128
It does that because a String
is a sequence of character code points and any conversion from a byte[]
is based on some byte encoding. In the above case, the platform default encoding happens to map many negative bytes to the same character. Another fact about String
is that it always takes and gives a copy of its internal state. If the original bytes came from a String
that was a copy, then wrapping it as a String
to use it as the key to a map takes a second copy. That may generate a lot of garbage that might be avoidable.
There is a good answer here that suggests using java.nio.ByteBuffer
with ByteBuffer.wrap(b)
. The problem with that is that byte[]
is mutable and it doesn't take a copy so you must be careful to take a defensive copy of any the arrays passed to you with ByteBuffer.wrap(b.clone())
else the keys of your map will be corrupted. If you look at the result of a map with ByteBuffer
keys in a debugger you will see that the buffers have a lot of internal references designed to track reading to and writing from each buffer. So the objects are much more heavyweight than wrapping in a simple String
. Finally, even a string holds more state than needed. Looking at it in my debugger it stores characters as a two-byte UTF16 array and also stores a four-byte hashcode.
My preferred approach is to have Lombok generate at compile time the boilerplate to make a lightweight byte array wrapper that doesn't store additional state:
import lombok.Data;
import lombok.EqualsAndHashCode;
import lombok.ToString;
@ToString
@EqualsAndHashCode
@Data(staticConstructor="of")
class ByteSequence {
final byte[] bytes;
}
This then passes the test that checks that all possible bytes map to a unique string:
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)));
}
You then don't have to worry about getting the equals and hashcode logic correct as it is supplied by Lombok where it does Arrays.deepEquals
which is documented at https://projectlombok.org/features/EqualsAndHashCode Note that lombok isn't a runtime dependency only a compile-time dependency and you can install an opensource plugin to your IDE so that your IDE "sees" all the generated boilerplate methods.
With this implementation, you still have to worry about above the mutability of the byte. If someone passes you a byte[]
that might be mutated, you should take a defensive copy using clone()
:
kvs.put(ByteSequence.of(key.clone()), value);