Using a Byte Array as Map Key in Java

1. Introduction

In this tutorial, we’ll learn how to use a byte array as a key in HashMap. Because of how HashMap works, we, unfortunately, can’t do that directly. We’ll investigate why is that and look at several ways to solve that problem.

2. Designing a Good Key for HashMap

2.1. How HashMap Works

HashMap uses the mechanism of hashing for storing and retrieving values from itself. When we invoke the put(key, value) method, HashMap calculates the hash code based on the key’s hashCode() method. This hash is used to identify a bucket in which the value is finally stored:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

When we retrieve a value using the get(key) method, a similar process is involved. The key is used to compute the hash code and then to find the bucket. Then each entry in the bucket is checked for equality using the equals() method. Finally, the value of the matching entry is returned:

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

2.2. Contract Between equals() and hashCode()

Both equals and hashCode methods have contracts that should be observed. In the context of HashMaps, one aspect is especially important: objects that are equal to each other must return the same hashCode. However, objects that return the same hashCode don’t need to be equal to each other. That’s why we can store several values in one bucket.

2.3. Immutability

The hashCode of the key in HashMap should not change. While it’s not mandatory, it’s highly recommended for keys to be immutable. If an object is immutable, its hashCode won’t have an opportunity to change, regardless of the implementation of the hashCode method.

By default, the hash is computed based on all fields of the object. If we would like to have a mutable key, we’d need to override the hashCode method to ensure that mutable fields aren’t used in its computation. To maintain the contract, we would also need to change the equals method.

2.4. Meaningful Equality

To be able to successfully retrieve values from the map, equality must be meaningful. In most cases, we need to be able to create a new key object that will be equal to some existing key in the map. For that reason, object identity isn’t very useful in this context.

This is also the main reason why using a primitive byte array isn’t really an option. Arrays in Java use object identity to determine equality. If we create HashMap with byte array as the key, we’ll be able to retrieve a value only using exactly the same array object.

Let’s create a naive implementation with a byte array as a key:

byte[] key1 = {1, 2, 3};
byte[] key2 = {1, 2, 3};
Map<byte[], String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

Not only do we have two entries with virtually the same key, but also, we can’t retrieve anything using a newly created array with the same values:

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);
String retrievedValue3 = map.get(new byte[]{1, 2, 3});

assertThat(retrievedValue1).isEqualTo("value1");
assertThat(retrievedValue2).isEqualTo("value2");
assertThat(retrievedValue3).isNull();

3. Using Existing Containers

Instead of the byte array, we can use existing classes whose equality implementation is based on content, not object identity.

3.1. String

String equality is based on the content of the character array:

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                   return false;
            }
            return true;
        }
    }
    return false;
}

Strings are also immutable, and creating a String based on a byte array is fairly straightforward. We can easily encode and decode a String using the Base64 scheme:

String key1 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});
String key2 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});

Now we can create a HashMap with String as keys instead of byte arrays. We’ll put values into the Map in a manner similar to the previous example:

Map<String, String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

Then we can retrieve a value from the map. For both keys, we’ll get the same, second value. We can also check that the keys are truly equal to each other:

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);

assertThat(key1).isEqualTo(key2);
assertThat(retrievedValue1).isEqualTo("value2");
assertThat(retrievedValue2).isEqualTo("value2");

3.2. Lists

Similarly to String, the List#equals method will check for equality of each of its elements. If these elements have a sensible equals() method and are immutable, List will work correctly as the HashMap key. We only need to make sure we’re using an immutable List implementation:

List<Byte> key1 = ImmutableList.of((byte)1, (byte)2, (byte)3);
List<Byte> key2 = ImmutableList.of((byte)1, (byte)2, (byte)3);
Map<List<Byte>, String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

assertThat(map.get(key1)).isEqualTo(map.get(key2));

Mind that the List of the Byte object will take a lot more memory than the array of byte primitives. So that solution, while convenient, isn’t viable for most scenarios.

4. Implementing Custom Container

We can also implement our own wrapper to take full control of hash code computation and equality. That way we can make sure the solution is fast and doesn’t have a big memory footprint.

Let’s make a class with one final, private byte array field. It’ll have no setter, and its getter will make a defensive copy to ensure full immutability:

public final class BytesKey {
    private final byte[] array;

    public BytesKey(byte[] array) {
        this.array = array;
    }

    public byte[] getArray() {
        return array.clone();
    }
}

We also need to implement our own equals and hashCode methods. Fortunately, we can use the Arrays utility class for both of these tasks:

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    BytesKey bytesKey = (BytesKey) o;
    return Arrays.equals(array, bytesKey.array);
}

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

Finally, we can use our wrapper as a key in a HashMap:

BytesKey key1 = new BytesKey(new byte[]{1, 2, 3});
BytesKey key2 = new BytesKey(new byte[]{1, 2, 3});
Map<BytesKey, String> map = new HashMap<>();
map.put(key1, "value1");
map.put(key2, "value2");

Then, we can retrieve the second value using either of the declared keys or we may use one created on the fly:

String retrievedValue1 = map.get(key1);
String retrievedValue2 = map.get(key2);
String retrievedValue3 = map.get(new BytesKey(new byte[]{1, 2, 3}));

assertThat(retrievedValue1).isEqualTo("value2");
assertThat(retrievedValue2).isEqualTo("value2");
assertThat(retrievedValue3).isEqualTo("value2");

5. Conclusion

In this tutorial, we looked at different problems and solutions for using a byte array as a key in HashMap. First, we investigated why we can’t use arrays as keys. Then we used some built-in containers to mitigate that problem and, finally, implemented our own wrapper.

As usual, the source code for this tutorial can be found over on GitHub.