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. Нуль как ключ
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");
Или, чтобы проверить, присутствует ли значение на карте, мы можем использовать метод 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 — это функциональный способ перебора всех элементов карты:
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. поставитьеслиотсутствует()
С помощью этого метода мы можем добавить новое сопоставление, но только если для данного ключа еще нет сопоставления:
productsByName.putIfAbsent("E-Bike", chocolate);
До Java 8:
if(productsByName.containsKey("E-Bike")) {
productsByName.put("E-Bike", chocolate);
}
В нашей статье « Объединение двух карт с Java 8 » этот метод рассматривается более подробно.
4.4. объединить()
И с помощью 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. вычислить()
С помощью метода 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() очень похожи. Метод 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));
Как мы видим, мы больше не можем получить соответствующее значение после изменения ключа, вместо этого возвращается null . Это связано с тем, что HashMap ищет не в том сегменте.
Приведенный выше тестовый пример может показаться неожиданным, если у нас нет хорошего понимания того, как HashMap работает внутри.
5.3. Столкновения
Чтобы это работало правильно, одинаковые ключи должны иметь одинаковый хеш, однако разные ключи могут иметь один и тот же хэш . Если два разных ключа имеют одинаковый хэш, два принадлежащих им значения будут храниться в одном сегменте. Внутри ведра значения хранятся в списке и извлекаются путем циклического перебора всех элементов. Стоимость этого O(n) .
Начиная с Java 8 (см. JEP 180 ), структура данных, в которой хранятся значения внутри одного сегмента, изменяется со списка на сбалансированное дерево, если сегмент содержит 8 или более значений, и обратно на список, если в момент в какой-то момент в ведре осталось только 6 значений. Это повышает производительность до O(log n) .
5.4. Вместимость и коэффициент нагрузки
Чтобы избежать большого количества сегментов с несколькими значениями, емкость удваивается, если 75% (коэффициент загрузки) сегментов становятся непустыми. Значение по умолчанию для коэффициента загрузки составляет 75%, а начальная мощность по умолчанию — 16. Оба параметра можно установить в конструкторе.
5.5. Сводка по операциям размещения и получения
Подытожим, как работают операции put и get .
Когда мы добавляем элемент на карту, HashMap вычисляет корзину. Если ведро уже содержит значение, оно добавляется в список (или дерево), принадлежащее этому ведру. Если коэффициент загрузки становится больше, чем максимальный коэффициент загрузки карты, вместимость удваивается.
Когда мы хотим получить значение из карты, HashMap вычисляет корзину и получает значение с тем же ключом из списка (или дерева).
6. Заключение
В этой статье мы увидели, как использовать HashMap и как он работает внутри. Наряду с ArrayList , HashMap является одной из наиболее часто используемых структур данных в Java, поэтому очень полезно хорошо знать, как ее использовать и как она работает «внутри». Наша статья The Java HashMap Under the Hood более подробно описывает внутренности HashMap .
Как обычно, полный исходный код доступен на Github .