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

Question

У меня возник вопрос из интервью.

Я был дан массив символов, как это:

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

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

Answer 1

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

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

Но интересно, почему архитектор только о том, что, так как есть больше вещей, чтобы улучшить:

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

Так что с моей точки зрения, лучшее исполнение, при использовании 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]++; 
} 

Answer 2

Вы можете написать цикл, как это -

for (char c : characters) {    

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

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

Answer 3

Ваш код является излишним, так как оба 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); 
} 

Answer 4

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

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

как функции получения и содержит делать ту же работу ...

вместо использования как полезного, так и полезного, используя функцию get

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

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

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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 сказал в приведенном выше ответе. Надеемся, что эта разбивка поможет.

Answer 8

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

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

---

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

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

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

Answer 9

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

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)? Практически мало практических различий.

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

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

Answer 10

Другой 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[].

Answer 11

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