Подтвердить что ты не робот

HashMap - содержит и получать методы не следует использовать вместе

Я получил следующий вопрос из интервью.

Мне был присвоен массив символов следующим образом:

char[] characters = {'u', 'a', 'u', 'i', 'o', 'f', 'u'};

Мне нужно было получить разные символы и числа каждого символа:

u = 3
a = 1
i = 1
o = 1
f = 1

Итак, я ответил на Java следующим кодом:

HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int i = 1;
for (char c : characters) {             
    if (map.containsKey(c)) {
        int val = map.get(c);
        map.put(c, ++val);
    } else map.put(c, i);
}

Интервьюер был архитектором решений. Он спросил меня, почему я использовал методы containsKey() и get() здесь и отметил, что использовать оба метода было излишним. В чем его смысл? Что я здесь делал неправильно? Изменит ли мой код проблему с производительностью и т.д.?

4b9b3361

ОТВЕТЫ

Ответ 1

Архитектор означает, что get и containsKey имеют одинаковые затраты и могут накапливаться в одной проверке:

Integer val = map.get(c);
if (val != null) {
  ...
} else {
  ...
}

Но мне интересно, почему архитектора беспокоит только это, поскольку есть еще кое-что для улучшения:

  • Обратитесь к объектам по их интерфейсам (Effective Java 2nd Edition, Item 52)
  • Начиная с Java 1.7 вы можете использовать оператор алмаза < >
  • Аккумулировать операции автобоксинга символов
  • Если вы используете AtomicInteger (или любой другой модифицируемый класс чисел) вместо Integer, вы можете даже объединить get с одним из puts

Итак, с моей точки зрения, наилучшая производительность при использовании HashMap будет предлагать:

Map<Character, AtomicInteger> map = new HashMap<>();
for (Character c : characters) {
    AtomicInteger val = map.get(c);
    if (val != null) {
        val.incrementAndGet();
    } else {
        map.put(c, new AtomicInteger(1));
    }
}

Если диапазон ваших символов мал (и известен заранее), вы можете использовать массив int для подсчета. Это было бы самым быстрым из всех возможных решений:

char firstCharacter = 'a';
char lastCharacter = 'z';
int[] frequency = new int[lastCharacter - firstCharacter + 1];
for (char c : characters) {
  frequency[c - firstCharacter]++;
}

Ответ 2

Ваш код лишний, так как оба get и containsKey выполняют почти ту же работу. Вместо вызова containsKey вы можете проверить, возвращает ли get нулевое значение.

Код может быть сведен к:

HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : characters) {   
    Integer val = map.get(c);          
    if (val == null)
        val = 0;
    map.put(c,++val);
}

Ответ 3

Вы можете написать свой цикл for следующим образом:

for (char c : characters) {             

   Integer val = map.get(c);
   if (null != val){
      map.put(c, ++val);
   } else {
      map.put(c, 1);
   }
}

Примечание: Я изменил int на Integer, чтобы я мог проверить его на null Если карта уже содержит значение, то она возвращает значение, и она будет назначена с помощью объявленную переменную Integer val. В противном случае val будет null. Поэтому я думаю, что вам не нужно использовать метод Map.containsKey().

Ответ 4

Начните с вашего кода и начните его уменьшать.

HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int i = 1;

for (char c : characters)
{             
    if (map.containsKey(c))
    {
        int val = map.get(c);
        map.put(c, ++val);
    }
    else map.put(c, i);
}

Первое, что я сделаю, это использовать оператор алмаза Java 7 и удалить переменную i

Map<Character, Integer> map = new HashMap<>();

for (char c : characters)
{
    if (map.containsKey(c))
        map.put(c, ++map.get(c));
    else
        map.put(c, 1);
}

Это мой первый шаг, мы удалили переменную i, поскольку она всегда постоянна как 1 и не изменяется во время выполнения. Я также сократил это выражение и сделал вызов map.get в вызов map.put. И теперь, когда мы видим, у нас есть три вызова методов карты.

Map<Character, Integer> map = new HashMap<>();

for (char c : characters)
{
    Integer i = map.get(c);

    if (i == null) i = 0;

    map.put(c, ++i);
}

Это лучший способ, и это то, что сказал @Eran в приведенном выше ответе. Надеемся, что этот отказ поможет.

Ответ 5

for (char c : characters) {   
     Integer val = map.get(c);
     if(val != null){
        map.put(c, ++val); 
     }else{
        map.put(c, 1);
     }
 }

Это может быть лучший способ, как

и функция get и contains выполняет ту же работу...

вместо того, чтобы использовать оба своих преимущества, используя функцию get

проверьте значение null здесь, когда вы используете функцию get. избегая двух вызовов, это улучшит производительность.

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

Ответ 6

Так как Java 8 вы можете сделать что-то вроде этого:

final Map<Character, Integer> map = new HashMap<>();
for (char c : characters)
    map.merge(c, 1, Integer::sum);

Обратите внимание, что вы делаете много бокса и unboxing с этим решением. Это не должно быть проблемой, но хорошо знать об этом.

Что делает этот код на самом деле (т.е. с ручным боксом и распаковкой):

for (char c : characters)
    map.merge(
        Character.valueOf(c),
        Integer.valueOf(1),
        (a, b) -> Integer.valueOf(Integer.sum(a.intValue(), b.intValue())));

Ответ 7

Что я обычно делаю для этого, если вы хотите поместить подсчет символов в Map.

Map<Character, Integer> map = new HashMap();
for (char c: cs) {
    Integer iCnt = map.get(c);
    if (iCnt ==  null) {
        map.put(c, 1);                
    } else {
        map.put(c, ++iCnt);
    }
}

Map.containsKey(ключ) проверяет указанный ключ на карте, которая очень похожа на Map.get(key). В вашем коде вы вызываете методы "containsKey" и "get", что означает, что вы будете проходить через два раза, что может вызвать проблемы с производительностью.

Ответ 8

Ну, я также системный архитектор, и я не вижу ничего плохого в вашем коде, кроме, возможно, отсутствия фигурных скобок - вы обычно должны их всегда использовать. Это было бы хорошо, на мой взгляд:

for (char c : characters) {             
    if (map.containsKey(c)) {
        int val = map.get(c);
        map.put(c, ++val);
    } else {
        map.put(c, 1);
    }
}

Лично я бы написал это так, что очень похоже на вашу собственную версию:

for (char c : characters) {
    int val = map.containsKey(c) ? map.get(c) : 0;
    map.put(c, ++val);
}

Зачем использовать как containsKey(), так и get()? Ну, если вы собираетесь использовать get(), вам нужно сделать нулевую проверку. Что более понятно кому-то, кто читает код, if (map.containsKey(c)) или if (val != null)? Практически мало практических различий.

Поисковые запросы хэширования O(log N), поэтому вызов get() и containsKey() вызывает два поиска, а не 1. Если вы тогда говорили об эффектных последствиях этого и о том, как он может работать с чрезвычайно большим набором данных то это было бы актуально.

Наконец, без проверки containtsKey(), int val = map.get(c); выдает npe в первый раз, поэтому вам нужно будет использовать Integer val = map.get(c);. Что более понятно и безопаснее - int val или Integer val? Я не вижу ничего плохого в том, чтобы позволить autoboxing делать это и использовать int val, и я обычно использую примитивные типы над объектами, где это возможно, хотя, вероятно, существует много разных мнений по int vs Integer.

Ответ 9

Еще одно решение Java 8, которое я еще не видел:

Character[] characters = {'u', 'a', 'u', 'i', 'o', 'f', 'u'};
Map<Character, Integer> result = Arrays.asList(characters)
        .stream()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.summingInt(c -> 1)));

Для этого требуется использование символа в штучной упаковке, однако - Arrays.asList не работает с char[], а Arrays.stream() не имеет перегрузки для char[].

Ответ 10

Проблема заключается в том, что containsskey должен проходить через все записи Карты, чтобы получить ключ (Iteration 1). Код для containsKey ниже.

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Теперь get ('') должен повторить итерацию, чтобы получить значение, отображаемое ключом (Итерация 2). Код для get также вызывает getEntry, как показано ниже.

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

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

Ответ 11

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