«1. Обзор
В этой статье мы увидим, как использовать HashMap в Java, и посмотрим, как это работает внутри.
Класс, очень похожий на HashMap, называется Hashtable. Пожалуйста, обратитесь к паре других наших статей, чтобы узнать больше о самом классе java.util.Hashtable и различиях между HashMap и Hashtable.
2. Основное использование
Давайте сначала посмотрим, что означает, что HashMap является картой. Карта — это сопоставление ключ-значение, что означает, что каждый ключ сопоставляется ровно с одним значением и что мы можем использовать ключ для извлечения соответствующего значения из карты.
Кто-то может спросить, почему бы просто не добавить значение в список. Зачем нам нужен HashMap? Причина проста: производительность. Если мы хотим найти конкретный элемент в списке, временная сложность будет O(n), а если список отсортирован, то будет O(log n) с использованием, например, бинарного поиска.
Преимущество HashMap заключается в том, что временная сложность вставки и извлечения значения составляет в среднем O(1). Мы рассмотрим, как этого можно достичь позже. Давайте сначала посмотрим, как использовать HashMap.
2.1. Настройка
Давайте создадим простой класс, который будем использовать на протяжении всей статьи:
public class Product {
private String name;
private String description;
private List<String> tags;
// standard getters/setters/constructors
public Product addTagsOfOtherProduct(Product product) {
this.tags.addAll(product.getTags());
return this;
}
}
2.2. Поместите
Теперь мы можем создать HashMap с ключом типа String и элементами типа Product:
Map<String, Product> productsByName = new HashMap<>();
И добавить продукты в наш HashMap:
Product eBike = new Product("E-Bike", "A bike with a battery");
Product roadBike = new Product("Road bike", "A bike for competition");
productsByName.put(eBike.getName(), eBike);
productsByName.put(roadBike.getName(), roadBike);
2.3. Получить
Мы можем получить значение из карты по его ключу:
Product nextPurchase = productsByName.get("E-Bike");
assertEquals("A bike with a battery", nextPurchase.getDescription());
Если мы попытаемся найти значение для ключа, которого нет в карте, мы получим нулевое значение: ~ ~~
Product nextPurchase = productsByName.get("Car");
assertNull(nextPurchase);
И если мы вставим второе значение с тем же ключом, мы получим только последнее вставленное значение для этого ключа:
Product newEBike = new Product("E-Bike", "A bike with a better battery");
productsByName.put(newEBike.getName(), newEBike);
assertEquals("A bike with a better battery", productsByName.get("E-Bike").getDescription());
2.4. Null в качестве ключа
HashMap также позволяет использовать null в качестве ключа:
Product defaultProduct = new Product("Chocolate", "At least buy chocolate");
productsByName.put(null, defaultProduct);
Product nextPurchase = productsByName.get(null);
assertEquals("At least buy chocolate", nextPurchase.getDescription());
2.5. Значения с одинаковым ключом
Кроме того, мы можем дважды вставить один и тот же объект с другим ключом:
productsByName.put(defaultProduct.getName(), defaultProduct);
assertSame(productsByName.get(null), productsByName.get("Chocolate"));
2.6. Удаление значения
Мы можем удалить сопоставление ключ-значение из HashMap:
productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));
2.7. Проверка наличия ключа или значения в карте
Чтобы проверить, присутствует ли ключ в карте, мы можем использовать метод containsKey():
productsByName.containsKey("E-Bike");
Или, чтобы проверить, присутствует ли значение в карте map, мы можем использовать метод containsValue():
productsByName.containsValue(eBike);
В нашем примере вызовы обоих методов вернут true. Хотя они выглядят очень похожими, между вызовами этих двух методов есть важная разница в производительности. Сложность проверки существования ключа — O(1), а сложность проверки элемента — O(n), так как необходимо пройтись по всем элементам на карте.
2.8. Итерация по HashMap
Существует три основных способа итерации по всем парам ключ-значение в HashMap.
Мы можем перебрать набор всех ключей:
for(String key : productsByName.keySet()) {
Product product = productsByName.get(key);
}
Или мы можем перебрать набор всех записей:
for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
Product product = entry.getValue();
String key = entry.getKey();
//do something with the key and value
}
Наконец, мы можем перебрать все значения:
List<Product> products = new ArrayList<>(productsByName.values());
~~ ~ 3. Ключ
Мы можем использовать любой класс в качестве ключа в нашей HashMap. Однако, чтобы карта работала правильно, нам нужно предоставить реализацию для equals() и hashCode(). Допустим, мы хотим иметь карту с продуктом в качестве ключа и ценой в качестве значения:
HashMap<Product, Integer> priceByProduct = new HashMap<>();
priceByProduct.put(eBike, 900);
Давайте реализуем методы equals() и hashCode():
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Product product = (Product) o;
return Objects.equals(name, product.name) &&
Objects.equals(description, product.description);
}
@Override
public int hashCode() {
return Objects.hash(name, description);
}
Обратите внимание, что hashCode() и equals() необходимо переопределять только для классов, которые мы хотим использовать в качестве ключей карты, а не для классов, которые используются только как значения в карте. Мы увидим, почему это необходимо, в разделе 5 этой статьи.
4. Дополнительные методы начиная с Java 8
В Java 8 к HashMap добавлено несколько методов функционального стиля. В этом разделе мы рассмотрим некоторые из этих методов.
Для каждого метода мы рассмотрим два примера. В первом примере показано, как использовать новый метод, а во втором примере показано, как добиться того же в более ранних версиях Java.
Так как эти методы довольно просты, мы не будем рассматривать более подробные примеры.
4.1. forEach()
Метод forEach представляет собой функциональный способ перебора всех элементов на карте:
productsByName.forEach( (key, product) -> {
System.out.println("Key: " + key + " Product:" + product.getDescription());
//do something with the key and value
});
До Java 8:
for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
Product product = entry.getValue();
String key = entry.getKey();
//do something with the key and value
}
Наша статья Руководство по Java 8 forEach охватывает цикл forEach более подробно.
4.2. получить или по умолчанию ()
«Используя метод getOrDefault(), мы можем получить значение из карты или вернуть элемент по умолчанию, если для данного ключа нет отображения:
Product chocolate = new Product("chocolate", "something sweet");
Product defaultProduct = productsByName.getOrDefault("horse carriage", chocolate);
Product bike = productsByName.getOrDefault("E-Bike", chocolate);
До Java 8:
Product bike2 = productsByName.containsKey("E-Bike")
? productsByName.get("E-Bike")
: chocolate;
Product defaultProduct2 = productsByName.containsKey("horse carriage")
? productsByName.get("horse carriage")
: chocolate;
4.3. putIfAbsent()
С помощью этого метода мы можем добавить новое сопоставление, но только если для данного ключа еще нет сопоставления:
productsByName.putIfAbsent("E-Bike", chocolate);
До Java 8:
if(productsByName.containsKey("E-Bike")) {
productsByName.put("E-Bike", chocolate);
}
Наша статья Объединение двух карт с Java 8 позволяет более подробно рассмотреть этот метод.
4.4. merge()
А с помощью merge() мы можем изменить значение для данного ключа, если сопоставление существует, или добавить новое значение в противном случае:
Product eBike2 = new Product("E-Bike", "A bike with a battery");
eBike2.getTags().add("sport");
productsByName.merge("E-Bike", eBike2, Product::addTagsOfOtherProduct);
До Java 8:
if(productsByName.containsKey("E-Bike")) {
productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2);
} else {
productsByName.put("E-Bike", eBike2);
}
4.5. Compute()
С помощью метода calculate() мы можем вычислить значение для заданного ключа:
productsByName.compute("E-Bike", (k,v) -> {
if(v != null) {
return v.addTagsOfOtherProduct(eBike2);
} else {
return eBike2;
}
});
До Java 8:
if(productsByName.containsKey("E-Bike")) {
productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2);
} else {
productsByName.put("E-Bike", eBike2);
}
Стоит отметить, что методы merge() и вычисления() очень похожи. Метод calculate() принимает два аргумента: ключ и BiFunction для переназначения. И merge() принимает три параметра: ключ, значение по умолчанию для добавления к карте, если ключ еще не существует, и BiFunction для переназначения.
5. Внутреннее устройство HashMap
В этом разделе мы рассмотрим внутреннюю работу HashMap и преимущества использования HashMap вместо простого списка, например.
Как мы видели, мы можем получить элемент из HashMap по его ключу. Один из подходов — использовать список, перебирать все элементы и возвращаться, когда мы находим элемент, для которого совпадает ключ. Как временная, так и пространственная сложность этого подхода будут O(n).
С помощью HashMap мы можем достичь средней временной сложности O(1) для операций ввода и получения и пространственной сложности O(n). Давайте посмотрим, как это работает.
5.1. Хэш-код и равенство
Вместо того, чтобы перебирать все свои элементы, HashMap пытается вычислить позицию значения на основе его ключа.
Наивным подходом было бы иметь список, который может содержать столько элементов, сколько возможно ключей. В качестве примера предположим, что наш ключ — это символ нижнего регистра. Тогда достаточно иметь список размером 26, и если мы хотим получить доступ к элементу с помощью ключа «c», мы будем знать, что это элемент в позиции 3, и мы можем получить его напрямую.
Однако этот подход не будет очень эффективным, если у нас будет гораздо большее пространство ключей. Например, предположим, что наш ключ был целым числом. В этом случае размер списка должен быть 2 147 483 647. В большинстве случаев у нас также было бы гораздо меньше элементов, поэтому большая часть выделенной памяти оставалась бы неиспользованной.
HashMap хранит элементы в так называемых сегментах, а количество сегментов называется емкостью.
Когда мы помещаем значение на карту, метод hashCode() ключа используется для определения корзины, в которой будет храниться значение.
Чтобы получить значение, HashMap вычисляет корзину таким же образом — используя hashCode(). Затем он перебирает объекты, найденные в этом сегменте, и использует метод equals() ключа, чтобы найти точное совпадение.
5.2. Неизменность ключей
В большинстве случаев мы должны использовать неизменяемые ключи. Или, по крайней мере, мы должны знать о последствиях использования изменяемых ключей.
Давайте посмотрим, что произойдет, когда наш ключ изменится после того, как мы использовали его для сохранения значения на карте.
Для этого примера мы создадим MutableKey:
public class MutableKey {
private String name;
// standard constructor, getter and setter
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
MutableKey that = (MutableKey) o;
return Objects.equals(name, that.name);
}
@Override
public int hashCode() {
return Objects.hash(name);
}
}
А вот и тест:
MutableKey key = new MutableKey("initial");
Map<MutableKey, String> items = new HashMap<>();
items.put(key, "success");
key.setName("changed");
assertNull(items.get(key));
Как мы видим, мы больше не можем получить соответствующее значение после того, как ключ изменился, вместо этого возвращается ноль. Это связано с тем, что HashMap ищет не в том сегменте.
Приведенный выше тестовый пример может удивить, если у нас нет хорошего понимания того, как HashMap работает внутри.
5.3. Коллизии
Чтобы это работало правильно, одинаковые ключи должны иметь одинаковый хеш, однако разные ключи могут иметь один и тот же хэш. Если два разных ключа имеют одинаковый хэш, два принадлежащих им значения будут храниться в одном сегменте. Внутри ведра значения хранятся в списке и извлекаются путем циклического перебора всех элементов. Стоимость этого O(n).
«Начиная с Java 8 (см. JEP 180), структура данных, в которой хранятся значения внутри одного сегмента, изменяется со списка на сбалансированное дерево, если сегмент содержит 8 или более значений, и обратно на список, если в момент в какой-то момент в ведре осталось только 6 значений. Это повышает производительность до O(log n).
5.4. Емкость и коэффициент загрузки
Чтобы избежать большого количества корзин с несколькими значениями, емкость удваивается, если 75% (коэффициент загрузки) корзин становятся непустыми. Значение по умолчанию для коэффициента загрузки составляет 75%, а начальная мощность по умолчанию — 16. Оба параметра можно установить в конструкторе.
5.5. Обзор операций put и get
Давайте подытожим, как работают операции put и get.
Когда мы добавляем элемент на карту, HashMap вычисляет корзину. Если ведро уже содержит значение, оно добавляется в список (или дерево), принадлежащее этому ведру. Если коэффициент загрузки становится больше, чем максимальный коэффициент загрузки карты, вместимость удваивается.
Когда мы хотим получить значение из карты, HashMap вычисляет корзину и получает значение с тем же ключом из списка (или дерева).
6. Заключение
В этой статье мы увидели, как использовать HashMap и как он работает внутри. Наряду с ArrayList, HashMap является одной из наиболее часто используемых структур данных в Java, поэтому очень полезно хорошо знать, как ее использовать и как она работает «внутри». Наша статья The Java HashMap Under the Hood более подробно описывает внутренности HashMap.
Как обычно, полный исходный код доступен на Github.