Проверка существования ключа в HashMap

Всегда ли необходима проверка на наличие ключей в HashMap?

У меня есть HashMap, скажем, 1000 записей, и я смотрю на повышение эффективности. Если к HashMap обращаются очень часто, то проверка существования ключа при каждом доступе приведет к большим издержкам. Вместо этого, если ключ отсутствует и, следовательно, возникает исключение, я могу поймать исключение. (когда я знаю, что это случится редко). Это уменьшит доступ к HashMap вдвое.

Это может быть не очень хорошая практика программирования, но это поможет мне уменьшить количество обращений. Или я что-то здесь упускаю?

[ Обновить ] У меня нет нулевых значений в HashMap.

Вы когда-нибудь хранили нулевое значение? Если нет, вы можете просто сделать:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // No such key
}

В противном случае вы можете просто проверить существование, если получите возвращенное нулевое значение:

Foo value = map.get(key);
if (value != null) {
    ...
} else {
    // Key might be present...
    if (map.containsKey(key)) {
       // Okay, there's a key but the value is null
    } else {
       // Definitely no such key
    }
}

Вы ничего не получите, проверив, что ключ существует. Это код HashMap:

@Override
public boolean containsKey(Object key) {
    Entry<K, V> m = getEntry(key);
    return m != null;
}

@Override
public V get(Object key) {
    Entry<K, V> m = getEntry(key);
    if (m != null) {
        return m.value;
    }
    return null;
}

Просто проверьте, get()отличается ли возвращаемое значение от null.

Это исходный код HashMap.

Ресурсы :

• Исходный код HashMap Bad one
• Хороший исходный код HashMap

Лучше всего использовать containsKeyметод HashMap. Завтра кто-нибудь добавит ноль на карту. Вы должны различать наличие ключа и ключ имеет нулевое значение.

Вы имеете в виду, что у вас есть такой код

if(map.containsKey(key)) doSomethingWith(map.get(key))

повсюду? Тогда вам просто нужно проверить, map.get(key)возвращен ли null и все. Кстати, HashMap не генерирует исключения для отсутствующих ключей, вместо этого он возвращает null. Единственный случай, когда containsKeyэто необходимо, когда вы храните нулевые значения, чтобы различать нулевое значение и пропущенное значение, но это обычно считается плохой практикой.

Просто используйте containsKey()для ясности. Это быстро и сохраняет код чистым и читабельным. Все дело HashMapс в том , что ключ поиска быстро, просто убедитесь , что hashCode()и equals()правильно реализованы.

if(map.get(key) != null || (map.get(key) == null && map.containsKey(key)))

Вы также можете использовать computeIfAbsent()метод в HashMapклассе.

В следующем примере mapхранится список транзакций (целых чисел), которые применены к ключу (имя банковского счета). Для того, чтобы добавить 2 сделки 100и 200до checking_accountвы можете написать:

HashMap<String, ArrayList<Integer>> map = new HashMap<>();
map.computeIfAbsent("checking_account", key -> new ArrayList<>())
   .add(100)
   .add(200);

Таким образом, вам не нужно проверять, checking_accountсуществует ли ключ или нет.

• Если он не существует, он будет создан и возвращен лямбда-выражением.
• Если он существует, то значение для ключа будет возвращено computeIfAbsent().

Действительно элегантно! 👍

Я обычно использую идиому

Object value = map.get(key);
if (value == null) {
    value = createValue(key);
    map.put(key, value);
}

Это означает, что вы попадаете на карту только дважды, если отсутствует ключ

1. Если вам нужен ключевой класс, убедитесь, что реализованы методы hashCode () и equals ().
2. По сути, доступ к HashMap должен быть O (1), но при неправильной реализации метода hashCode он становится O (n), потому что значение с тем же ключом хеш-функции будет храниться в виде связанного списка.

Ответ Джона Скита хорошо обращается к двум сценариям (карта со nullзначением и не nullзначением) эффективным способом.

О количестве записей и проблем эффективности, я хотел бы добавить кое-что.

У меня есть HashMap с, скажем, 1000 записей, и я смотрю на повышение эффективности. Если к HashMap обращаются очень часто, то проверка существования ключа при каждом доступе приведет к большим издержкам.

Карта с 1000 записей не является огромной картой.
А также карта с 5.000 или 10.000 записей.
Mapпредназначены для быстрого поиска с такими размерами.

Теперь предполагается, что hashCode()ключи карты обеспечивают хорошее распределение.

Если вы можете использовать в Integerкачестве типа ключа, сделайте это.
Его hashCode()метод очень эффективен, поскольку столкновения невозможны для уникальных intзначений:

public final class Integer extends Number implements Comparable<Integer> {
    ...
    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

    public static int hashCode(int value) {
        return value;
    }
    ...
}

Если для ключа вам нужно использовать другой встроенный тип, как, Stringнапример, который часто используется в Map, у вас могут быть некоторые коллизии, но от 1 тысячи до нескольких тысяч объектов в Map, у вас должно быть очень мало таких как String.hashCode()метод обеспечивает хорошее распределение.

Если вы используете пользовательский тип, переопределите hashCode()и equals()правильно и убедитесь, что в целом это hashCode()обеспечивает справедливое распределение.
Вы можете обратиться к пункту 9 Java Effectiveссылки.
Вот пост, который подробно описывает путь.