Использование массива байтов в качестве ключа карты в Java

Автор оригинала: Michał Dąbrowski.

1. введение

В этом уроке мы узнаем, как использовать массив байтов в качестве ключа в HashMap . Из-за того, как работает HashMap , мы, к сожалению, не можем сделать это напрямую. Мы выясним, почему это так, и рассмотрим несколько способов решения этой проблемы.

2. Разработка хорошего ключа для HashMap

2.1. Как работает HashMap

HashMap использует механизм хеширования для хранения и извлечения значений из самого себя. Когда мы вызываем метод put(ключ, значение) , HashMap вычисляет хэш-код на основе метода hashCode() ключа. Этот хэш используется для идентификации корзины, в которой в конечном итоге хранится значение:

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

Когда мы извлекаем значение с помощью метода get(key) , происходит аналогичный процесс. Ключ используется для вычисления хэш-кода, а затем для поиска корзины. Затем каждая запись в корзине проверяется на равенство с помощью метода equals () . Наконец, возвращается значение соответствующей записи:

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. Контракт между equals() и хэш-кодом()

Оба метода equals и hashCode имеют контракты , которые следует соблюдать. В контексте HashMaps особенно важен один аспект: объекты , равные друг другу, должны возвращать один и тот же хэш-код . Однако объекты, возвращающие один и тот же хэш-код , не обязательно должны быть равны друг другу. Вот почему мы можем хранить несколько значений в одном ведре.

2.3. Неизменность

Хэш-код ключа в HashMap не должен изменяться. Хотя это не обязательно, настоятельно рекомендуется, чтобы ключи были неизменяемыми. Если объект является неизменяемым, его хэш-код не будет иметь возможности измениться, независимо от реализации метода hashCode .

По умолчанию хэш вычисляется на основе всех полей объекта. Если мы хотим иметь изменяемый ключ, нам нужно переопределить метод hashCode , чтобы гарантировать, что изменяемые поля не используются при его вычислении. Чтобы сохранить контракт, нам также нужно будет изменить метод equals .

2.4. Значимое равенство

Чтобы иметь возможность успешно извлекать значения из карты, равенство должно быть значимым. В большинстве случаев нам нужно иметь возможность создать новый ключевой объект, который будет равен некоторому существующему ключу на карте. По этой причине идентификация объекта не очень полезна в этом контексте.

Это также основная причина, по которой использование примитивного массива байтов на самом деле не является вариантом. Массивы в Java используют идентификатор объекта для определения равенства. Если мы создадим HashMap с массивом байтов в качестве ключа, мы сможем получить значение только с использованием точно такого же объекта массива.

Давайте создадим наивную реализацию с массивом байтов в качестве ключа:

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

Мало того, что у нас есть две записи с практически одинаковым ключом, но также мы не можем ничего извлечь, используя вновь созданный массив с одинаковыми значениями:

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. Использование Существующих Контейнеров

Вместо массива байтов мы можем использовать существующие классы, реализация равенства которых основана на содержании, а не на идентичности объекта.

3.1. Строка

Строка равенство основано на содержимом массива символов:

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

String s также неизменяемы, и создание String на основе массива байтов довольно просто. Мы можем легко кодировать и декодировать Строку , используя схему Base64 :

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

Теперь мы можем создать HashMap с String в качестве ключей вместо массивов байтов. Мы поместим значения в Map аналогично предыдущему примеру:

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

Затем мы можем извлечь значение из карты. Для обоих ключей мы получим одно и то же второе значение. Мы также можем проверить, действительно ли ключи равны друг другу:

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

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

3.2. Списки

Аналогично String , метод List#equals будет проверять равенство каждого из его элементов. Если эти элементы имеют разумный метод equals() и являются неизменяемыми, List будет корректно работать в качестве ключа HashMap . Нам нужно только убедиться, что мы используем неизменяемую Список реализацию :

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

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

Имейте в виду, что Список объекта Byte займет намного больше памяти, чем массив примитивов byte . Таким образом, это решение, хотя и удобное, не является жизнеспособным для большинства сценариев.

4. Реализация Пользовательского Контейнера

Мы также можем реализовать нашу собственную оболочку, чтобы полностью контролировать вычисление хэш-кода и равенство. Таким образом, мы можем убедиться, что решение быстрое и не требует большого объема памяти.

Давайте создадим класс с одним последним закрытым полем byte array. У него не будет сеттера, и его геттер сделает защитную копию, чтобы обеспечить полную неизменность:

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

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

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

Нам также необходимо реализовать наши собственные методы equals и hashCode . К счастью, мы можем использовать класс утилиты Arrays для обеих этих задач:

@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);
}

Наконец, мы можем использовать нашу оболочку в качестве ключа в HashMap :

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

Затем мы можем получить второе значение, используя любой из объявленных ключей, или мы можем использовать один, созданный на лету:

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. Заключение

В этом уроке мы рассмотрели различные проблемы и решения для использования массива byte в качестве ключа в HashMap . Во-первых, мы исследовали, почему мы не можем использовать массивы в качестве ключей. Затем мы использовали некоторые встроенные контейнеры, чтобы смягчить эту проблему, и, наконец, реализовали нашу собственную оболочку.

Как обычно, исходный код этого учебника можно найти на GitHub .