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 имеют контракты , которые следует соблюдать. В контексте HashMaps особенно важен один аспект: объекты, которые равны друг другу, должны возвращать один и тот же hashCode . Однако объекты, возвращающие один и тот же хэш -код , не обязательно должны быть равны друг другу. Вот почему мы можем хранить несколько значений в одном сегменте.
2.3. неизменность
Хэш - код ключа в HashMap не должен меняться. Хотя это не обязательно, настоятельно рекомендуется, чтобы ключи были неизменяемыми. Если объект неизменяем, его hashCode не будет иметь возможности измениться, независимо от реализации метода 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. Нить
Строковое равенство основано на содержимом массива символов:
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 также являются неизменяемыми, и создание String на основе массива байтов довольно просто. Мы можем легко кодировать и декодировать строку , используя схему 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. Списки
Аналогично String метод List#equals будет проверять равенство каждого из его элементов. Если эти элементы имеют разумный метод equals() и являются неизменяемыми, List будет корректно работать как ключ HashMap . Нам нужно только убедиться, что мы используем неизменяемую реализацию List :
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));
Имейте в виду, что объект List of the 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 . Во-первых, мы выяснили, почему мы не можем использовать массивы в качестве ключей. Затем мы использовали несколько встроенных контейнеров, чтобы смягчить эту проблему, и, наконец, реализовали собственную оболочку.
Как обычно, исходный код этого руководства можно найти на GitHub .