Руководство по Java HashMap

В этой статье рассмотрим, как использовать HashMap в Java, как это работает «под капотом».

Класс, очень похожий на HashMap, называется Hashtable. Подробнее об этом можно узнать в самом классе java.util.Hashtable и различиях между HashMap и Hashtable.

Основное использование

Давайте сначала посмотрим, что означает Map в HashMap. Map – это сопоставление ключ-значение, что означает, что каждый ключ сопоставляется ровно с одним значением и что можно использовать ключ для извлечения соответствующего значения из Map.

Можно спросить, почему бы просто не добавить значение в список. Зачем нам нужен HashMap? Причина проста: производительность. Если хотим найти конкретный элемент в списке, временная сложность будет O(n), а если список отсортирован, то будет O(log n) с использованием, например, бинарного поиска.

Преимущество HashMap заключается в том, что временная сложность вставки и извлечения значения составляет в среднем O(1). Рассмотрим позже, как этого можно достичь. Сначала посмотрим, как использовать HashMap.

Инициализация

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

public class Product {

    private String name;
    private String description;
    private List<String> tags;
    
    // стандартные геттеры/сеттеры/конструкторы

    public Product addTagsOfOtherProduct(Product product) {
        this.tags.addAll(product.getTags());
        return this;
    }
}

Добавление (put)

Теперь мы можем создать 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);

Получение (get)

Можно получить значение из мапы по ключу:

Product nextPurchase = productsByName.get("E-Bike");
assertEquals("A bike with a battery", nextPurchase.getDescription());

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

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());

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());

Значения с одним и тем же ключом

 Кроме того, можно дважды вставить один и тот же объект с другим ключом:

productsByName.put(defaultProduct.getName(), defaultProduct);
assertSame(productsByName.get(null), productsByName.get("Chocolate"));

Удаление значения

Можно удалить сопоставление ключ-значение из HashMap:

productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));

Проверка, существует ли ключ или значение в мапе

Чтобы проверить, присутствует ли ключ в мапе, можно использовать метод containsKey():

productsByName.containsKey("E-Bike");

Чтобы проверить, присутствует ли значение в мапе, можно использовать метод containsValue():

productsByName.containsValue(eBike);

В нашем примере вызовы обоих методов вернут true. Хотя они выглядят очень похожими, между ними есть важная разница в производительности. Сложность проверки существования ключа – O(1), а сложность проверки элемента – O(n), так как необходимо пройтись по всем элементам в мапе.

Итерация по 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());

Ключ

Можно использовать любой класс в качестве ключа в 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() необходимо переопределять только для классов, которые хотим использовать в качестве ключей мапы, а не для классов, которые используются только как значения в мапе. Почему именно так, узнаем чуть позже.

Дополнительные методы начиная с Java 8

Java 8 добавила в HashMap несколько методов функционального стиля.

В этом разделе рассмотрим некоторые из них.

Для каждого метода рассмотрим два примера. В первом примере показано, как использовать новый метод, а во втором примере показано, как добиться того же в более ранних версиях Java. Поскольку эти методы довольно просты, не будем рассматривать более подробные примеры.

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 рассматривается более подробно.

getOrDefault()

Используя метод 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;

putIfAbsent()

С помощью этого метода можно добавить новое сопоставление, но только если для данного ключа еще нет сопоставления:

productsByName.putIfAbsent("E-Bike", chocolate);

До Java 8:

if(productsByName.containsKey("E-Bike")) {
    productsByName.put("E-Bike", chocolate);
}

В статье «Объединение двух мап в Java 8» этот метод рассматривается более подробно.

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

compute()

С помощью метода compute() можно вычислить значение для данного ключа:

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() и compute() очень похожи. Метод compute() принимает два аргумента: key и BiFunction для переназначения. А merge() принимает три параметра: key, default value для добавления к мапе, если ключ еще не существует, и BiFunction для переназначения.

Внутреннее устройство HashMap

В этом разделе рассмотрим внутреннюю работу HashMap и преимущества использования HashMap вместо простого списка.

Можно получить элемент из HashMap по его ключу. Один из подходов – использовать список, перебирать все элементы и возвращаться, когда находим элемент, для которого совпадает ключ. Как временная, так и пространственная сложность этого подхода будут O(n).

С помощью HashMap можно достичь средней временной сложности O(1) для операций ввода и получения и пространственной сложности O(n). Давайте посмотрим, как это работает.

Хэш-код и Equals

Вместо перебора всех своих элементов HashMap пытается вычислить положение значения на основе его ключа.

Простым подходом было бы иметь список, который может содержать столько элементов, сколько возможно ключей. В качестве примера предположим, что наш ключ – это символ нижнего регистра. Тогда достаточно иметь список размером 26. И если хотим получить доступ к элементу с помощью ключа «c», то будем знать, что это элемент в позиции 3, и мы можем получить его напрямую.

Однако этот подход не будет эффективным, если бы было гораздо большее пространство ключей. Например, предположим, что ключ – целое число. В этом случае размер списка должен быть 2147483647. В большинстве случаев было бы гораздо меньше элементов, поэтому большая часть выделенной памяти оставалась бы неиспользованной.

HashMap хранит элементы в так называемых корзинах, а количество корзин называется емкостью.

Когда помещаем значение в мапу, метод hashCode() ключа используется для определения корзины, в которой будет храниться значение. Чтобы получить значение, HashMap вычисляет корзину таким же образом – с помощью hashCode(). Затем перебирает объекты, найденные в этой корзине, и использует метод equals() ключа, чтобы найти точное совпадение.

Неизменяемость ключей

В большинстве случаев необходимо использовать неизменяемые ключи. Или, по крайней мере, нужно знать о последствиях использования изменяемых ключей. Давайте посмотрим, что произойдет, когда ключ изменится после того, как мы использовали его для сохранения значения в мапе. В этом примере создадим 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 работает «под капотом».

Коллизии

Чтобы это работало правильно, одинаковые ключи должны иметь одинаковый хэш, однако разные ключи могут иметь один и тот же хэш. Если два разных ключа имеют одинаковый хэш, два принадлежащих им значения будут храниться в одной корзине. Внутри корзины значения хранятся в списке и извлекаются путем циклического перебора всех элементов. Производительность этого O(n). Начиная с Java 8 (см. JEP 180), структура данных, в которой хранятся значения внутри одной корзины, изменяется со списка на сбалансированное дерево, если корзина содержит 8 или более значений, и обратно возвращается в список, если в какой-то момент в корзине осталось только 6 значений. Это повышает производительность до O(log n).

Вместимость (Capacity) и коэффициент загрузки (Load Factor)

Чтобы избежать большого количества корзин с несколькими значениями, емкость удваивается, если 75% (коэффициент загрузки) корзин становятся непустыми. Значение по умолчанию для коэффициента загрузки составляет 75%, а начальная вместимость по умолчанию – 16. Оба параметра можно установить в конструкторе.

Резюме по операциям get и put

Подытожим, как работают операции put и get. Когда добавляем элемент в мапу, HashMap вычисляет корзину. Если корзина уже содержит значение, оно добавляется в список (или дерево), принадлежащий этой корзине. Если коэффициент загрузки становится больше, чем максимальный коэффициент загрузки мапы, вместимость удваивается.

Если хотим получить значение из мапы, HashMap вычисляет корзину и получает значение с тем же ключом из списка (или дерева).

Заключение

В этой статье рассмотрели, как использовать HashMap и как она работает «под капотом». Наряду с ArrayList, HashMap является одной из наиболее часто используемых структур данных в Java, поэтому очень полезно хорошо знать, как ее использовать и как она работает. Статья The Java HashMap Under the Hood более подробно описывает внутренности HashMap.

Полный исходный код доступен на Github.

Оригинал