1. Введение
В этом руководстве мы узнаем, как использовать массив байтов в качестве ключа в HashMap. К сожалению, из-за особенностей работы HashMap сделать это напрямую не получится. Мы разберёмся, почему так происходит, и рассмотрим несколько способов решения этой проблемы.
2. Проектирование хорошего ключа для HashMap
2.1. Как работает HashMap
HashMap использует механизм хеширования для хранения и извлечения значений. Когда мы вызываем метод put(key, value), 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() и hashCode()
Методы equals и hashCode должны соблюдать определённый контракт. В контексте HashMap важно следующее: объекты, считающиеся равными, обязаны возвращать одинаковый hashCode. Однако объекты с одинаковым hashCode не обязаны быть равными. Именно поэтому в одной корзине может храниться несколько значений.
2.3. Неизменяемость
hashCode ключа в HashMap не должен изменяться. Хотя это и не обязательно, настоятельно рекомендуется, чтобы ключи были неизменяемыми. Если объект неизменяем, его hashCode не может измениться, независимо от реализации.
Если хочется использовать изменяемый ключ, необходимо переопределить метод hashCode, исключив изменяемые поля из расчёта. Также нужно изменить метод equals, чтобы соблюсти контракт.
2.4. Осмысленное равенство
Чтобы успешно извлекать значения из карты, равенство должно быть осмысленным. В большинстве случаев нужно иметь возможность создать новый ключ, равный уже существующему в карте. Поэтому идентичность объектов здесь мало полезна.
Это также главная причина, по которой использование обычного массива байтов как ключа — неудачная идея. В Java массивы используют идентичность объекта для определения равенства. Если создать HashMap с массивом байтов в качестве ключа, извлечь значение получится только с использованием точно того же объекта массива.
Создадим наивную реализацию с массивом байтов в качестве ключа:
byte[] key1 = {1, 2, 3};
byte[] key2 = {1, 2, 3};
Map<byte[], String> 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. String
Равенство строк основано на содержимом символьного массива:
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;
}
Строки также являются неизменяемыми, и создать строку на основе массива байтов довольно просто. Можно легко кодировать и декодировать строку с использованием схемы Base64:
String key1 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});
String key2 = Base64.getEncoder().encodeToString(new byte[]{1, 2, 3});
Теперь можно создать HashMap, используя строки в качестве ключей вместо массивов байтов. Добавим значения в карту аналогично предыдущему примеру:
Map<String, String> 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. Lists
Аналогично String, метод List#equals проверяет равенство каждого элемента. Если элементы имеют корректную реализацию equals() и являются неизменяемыми, List может корректно работать как ключ HashMap. Нужно только убедиться, что используется неизменяемая реализация списка:
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));
Однако имейте в виду, что список объектов Byte будет занимать гораздо больше памяти, чем массив примитивов byte. Поэтому это решение, хоть и удобное, не подходит для большинства сценариев.
4. Реализация собственного контейнера
Можно также реализовать собственную обёртку, чтобы полностью контролировать вычисление хеш-кода и равенства. Это позволит обеспечить высокую производительность и низкое потребление памяти.
Создадим класс с одним финальным приватным полем — массивом байтов. Сеттеров не будет, а геттер будет возвращать защитную копию для полной неизменяемости:
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<BytesKey, String> 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. Заключение
В этом руководстве мы рассмотрели различные проблемы и решения, связанные с использованием массива байтов в качестве ключа HashMap. Сначала разобрали, почему напрямую использовать массивы нельзя. Затем применили встроенные контейнеры для обхода этой проблемы и, наконец, реализовали собственную обёртку.
Оригинал статьи: https://www.baeldung.com/java-map-key-byte-array