Map 그리고 merge()

Java의 자료구조 중 Map에 대해 이야기 해보려합니다. HashMap, TreeMap 두가지에 모두 적용되는 이야기입니다.

간단히 두 맵에 대해 알아보고, 알아두면 좋을 내용들 그리고 마지막으로 merge에 대해 살펴보겠습니다.

 

 

Map

Key, Value로 내부 데이터를 구성하고 Key는 중복이 불가능하지만, Value 값은 중복 가능합니다.

중복이 가능하고 불가능 여부는 아래와 같습니다.

Map<String, Integer> map 로 선언한 경우

i) key 중복
map.put("apple", 1);
map.put("apple", 2);
=> map.get("apple"); 호출 시 2의 값을 반환합니다.

ii) value 중복
map.put("apple", 1);
map.put("banana", 1);
=> map.get("apple") == 1, map.get("banana") == 1

 

HashMap

말 그대로 Hash function을 이용해 만든 Map 입니다.

데이터를 받는 순서와 상관 없이 내부적으로 순서를 보장하지 못합니다.

Hash function 관련 내용은 아래 포스팅 참고 부탁드립니다.

11. Hash

 

 

TreeMap

Red-Black Tree로 구성된 Map 입니다.

내부적으로 key 값을 기준으로 데이터를 정렬합니다. Comparator 구현체를 이용해 정렬 기준을 변경도 가능합니다.

시간이 되면 Red-Black 트리 관련 내용도 정리해보도록 하겠습니다.

 

 

오늘은 map을 전반적으로 사용하는 방법을 보기 위함이니, 대략적인 활용만 보겠습니다.

TreeMap 인터페이스로 맵을 구현하면, pollFirst/LastEntry(), higherKey(), first/lastKey() 등 다양한 기능을 사용해 볼 수 있습니다.

관련 내용은 필요하실 때 개인적으로 찾아보시길 권장드립니다.

 

 

Map에 저장된 데이터를 꺼내쓰는 다양한 방법

각각 꺼내쓰기

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        Map<String, Integer> map = new HashMap<>();

        map.put("apple", 2);
        map.put("banana", 1);
        map.put("grape", 3);

        for(String key: map.keySet()) {     // 모든 key 출력 ... 1
            System.out.println(key);
        }

        for(int value: map.values()) {      // 모든 값 출력 ... 2
            System.out.println(value);
        }

        for(String key: map.keySet()) {     // 모든 값 출력, 2와 동일 ... 3
            System.out.println(map.get(key));
        }
    }
}

key만 또는 value만 필요한 경우 위와 같이 꺼내 쓸 수 있습니다.

근데, 두개 모두 동시에 필요한 즉, 엔트리 전체가 pair로 필요한 경우도 있습니다.

 

 

Entry 전체 꺼내쓰기

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        Map<String, Integer> map = new HashMap<>();

        map.put("apple", 2);
        map.put("banana", 1);
        map.put("grape", 3);

        for(String key: map.keySet()) {     // key를 통한 entry 접근 ... 1
            System.out.println(key + " " + map.get(key));
        }

        for(Map.Entry<String, Integer> entry: map.entrySet()) {      // entry 자체 접근 ... 2
            System.out.println(entry);
        }
    }
}

결과는 똑같이 출력되지만, 성능 자체는 아래 코드가 훨씬 좋습니다.

제가 생각하는 이유는 아래와 같습니다.

두 방법을 요약해보면, 이렇게 정리할 수 있습니다.
1. entry를 한번에 가져오는 방법
2. key를 찾고, 찾은 key를 통해 다시 map 내부에서 value를 찾는 방법

이미 묶여 연관되어있는 애들을 한 번에 뽑아오면 될 것을 굳이 여러번 걸쳐 연산할 필요는 없겠죠.

Stack Overflow에도 동일한 질문에 저와 같은 답변을 한 내용이 있어 아래 참고 자료로 링크 공유드립니다.

추가로, toString()도 구현되어있어 상당히 편리하다는 이야기도 쓰여있습니다.

 

 

merge()

드디어 주인공 등장 두괄식이 아니라 죄송합니다..

merge()는 격동의 시기 자바 1.8에 등장한 친구입니다. 그도 그럴것이 아래와 같이 구현되어있습니다.

default V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)

이렇게 인자 2개를 받아 결과를 리턴하는 BiFunction 파라미터를 받습니다.

 

 

merge! 정의는 무엇이고, 어떤 경우에 유용하게 쓸 수 있을지 살펴보겠습니다.

머지가 머지? 죄송합니다. ㅎㅎ

 

용도부터 보겠습니다. 뭔지 알아야 필요성을 느끼고 흥미가 생기겠죠?

예를들어 어떤 문자열에서 등장하는 각 알파벳의 개수를 센다고 가정하겠습니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        Map<Character, Integer> map = new HashMap<>();
        String alphabets = "sadadwcqwdbvcicbkwaaazcsw";

        char[] inputs = alphabets.toCharArray();
        for(char input: inputs) {
            if(map.containsKey(input)) {
                map.put(input, map.get(input) + 1);
                continue;
            }

            map.put(input, 1);
        }
    }
}

이렇게 구성할 수 있겠죠.

맵에 해당 key가 존재하지 않는 경우엔 put으로 초기화해주지 않으면 NPE가 발생하니까요.

코드가 좀 복잡하고.. 불편해집니다. 하지만, merge를 사용하면 아래와 같이 바꿀 수 있습니다.

 

merge()

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        Map<Character, Integer> map = new HashMap<>();
        String alphabets = "sadadwcqwdbvcicbkwaaazcsw";

        char[] inputs = alphabets.toCharArray();
        for(char input: inputs) {
            map.merge(input, 1, Integer::sum);
        }
    }
}

진짜 간단하고.. 기가막히죠.

3번째 파라미터는 Integer wrapper 클래스에 구현된 sum 메서드를 호출한건데, 아래와 같이 구현되어있습니다.

 

class Integer sum()

/**
* Adds two integers together as per the + operator.
*
* @param a the first operand
* @param b the second operand
* @return the sum of {@code a} and {@code b}
* @see java.util.function.BinaryOperator
* @since 1.8
*/
public static int sum(int a, int b) {
    return a + b;
}

뭐.. 사실 뻔합니다. 대충 어떻게 동작하는지 파악은 하셨겠죠.

이제 정확한 정의부터 알아봅시다.

 

merge()

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is null. This method may be of use when combining multiple mapped values for a key.

key가 연관된 값이 없거나, null과 연관된 경우 non-null value를 연관시켜준다. 그렇지 않으면, 연관된 값을 remapping function 결과 값으로 대체하거나, 그 결과 값도 null인 경우 제거한다. 해당 메서드는 key에 대한 다수의 value를 결합할 때 사용될 수 있다.

 

정의가 살짝 복잡한데, pseudo 코드를 보면 이해가 좀 더 쉽습니다.

 V oldValue = map.get(key);
 V newValue = (oldValue == null) ? value :
              remappingFunction.apply(oldValue, value);
 if (newValue == null)
     map.remove(key);
 else
     map.put(key, newValue);

 

 

이렇게만 하면 이해가 안되는 분들도 많겠죠. 그래서 각 경우에 따라 어떻게 진행되는지 살펴보려합니다.

1. oldValue == null, newValue == null
2. oldValue == null, newValue != null
3. oldValue != null, newValue == null
4. oldValue != null, newValue != null

 

1. oldValue == null, newValue == null

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Character, Integer> map = new HashMap<>();
        String alphabets = "sadadwcqwdbvcicbkwaaazcsw";

        char[] inputs = alphabets.toCharArray();
        // 첫 input 즉 's'가 들어온 경우

        map.merge('s', Nullable.getNull(), Integer::sum);
        // 1. map.get('s'); => null
        // 2. newValue = (oldValue == null) ? value: remappingFunction();
        // 3. newValue = value, value도 null인 경우 NPE
    }
}

class Nullable {
    private Integer value;

    public Nullable(Integer value) {
        this.value = value;
    }

    public Integer getValue() {
        return value;
    }

    public static Integer getNull() {
        return null;
    }
}

HashMap.class merge() Override

    @Override
    public V merge(K key, V value,
                   BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        if (value == null)
            throw new NullPointerException();
        if (remappingFunction == null)
            throw new NullPointerException();
        int hash = hash(key);
        
        ... 생략
        
        return value;
    }

value에 강제 null을 리턴하도록 호출했습니다. map.remove()가 발생하도록 유도한 것입니다.

그런데, HashMap 내부 merge 구현의 코드를 보시면, value가 null인경우 NPE를 던지도록 재정의 되어있어 해당 방법으론 접근이 어려웠습니다.

초기 키/값도 존재하지 않는데, 대체할 값도 null이니, NPE가 발생하는게 자연스럽긴합니다.

 

2. oldValue == null, newValue != null

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Character, Integer> map = new HashMap<>();
        String alphabets = "sadadwcqwdbvcicbkwaaazcsw";

        char[] inputs = alphabets.toCharArray();
        
        // 첫 input 즉 's'가 들어온 경우

        map.merge('s', 1, Integer::sum);
        // 1. map.get('s'); => null
        // 2. newValue = (oldValue == null) ? value: remappingFunction();
        // 3. newValue = value 즉, value == 1로 초기화, Integer::sum 함수 작동 (이후 해당 key는 1씩 계속 증가)
    }
}

이렇게 진행한 경우 일반적인 merge 용도 중 초기화로 보시면 되겠습니다.

map에 없던 key가 merge 입력으로 들어온 경우, value 파라미터를 기본 값으로 설정해줍니다.

 

3. oldValue != null, newValue == null

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        Map<Character, Integer> map = new HashMap<>();
        String alphabets = "sadadwcqwdbvcicbkwaaazcsw";

        char[] inputs = alphabets.toCharArray();
        // 's'가 이미 map에 존재하는 경우
        map.put('s', 13);

        map.merge('s', -1, Nullable::getNull);
        // 1. map.get('s'); => not null, 13
        // 2. newValue = (oldValue == null) ? value: remappingFunction();
        // 3. newValue = remappingFunction, null return

        System.out.println(map.containsKey('s'));
        // 4. false 출력
    }
}

class Nullable {
    private Integer oldValue;
    private Integer value;

    public Nullable(Integer oldValue, Integer value) {
        this.oldValue = oldValue;
        this.value = value;
    }

    public static Integer getNull(Integer int1, Integer int2) {
        return null;
    }

    public Integer getOldValue() {
        return oldValue;
    }

    public Integer getValue() {
        return value;
    }
}

이미 map에 key와 value가 존재하는 경우 코드를 구성해봤습니다.

이후 merge를 호출하며 remappingFunction에서 null을 반환하도록 유도했는데, 놀랍게도 key가 사라졌습니다.

의도한 대로 결과가 이루어졌는데, 약간 의문이 생기죠... 왜 굳이 key를 지워버릴까요?

위와 같은 경우 key를 지우지않고, 이전에 map에 저장한 's'와 13을 엔트리로 갖고있으면 안될까요?

우선, 마지막 케이스를 진행해 보고 이에 대해 고민해 봅시다.

 

4. oldValue != null, newValue != null

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws Exception {
        Map<Character, Integer> map = new HashMap<>();
        String alphabets = "sadadwcqwdbvcicbkwaaazcsw";

        char[] inputs = alphabets.toCharArray();
        // 's'가 이미 map에 존재하는 경우
        map.put('s', 13);

        map.merge('s', -1, Integer::sum);
        // 1. map.get('s'); => not null, 13
        // 2. newValue = (oldValue == null) ? value: remappingFunction();
        // 3. newValue = remappingFunction => Integer::sum, 13 - 1 = 12

        System.out.println(map.get('s'));
        // 4. 12 출력
    }
}

이번 케이스는 일반적인 merge 용도 중 함수를 통한 연산 진행으로 보시면 되겠습니다.

둘다 not null 상태이므로, 함수를 통해 값 연산이 연쇄적으로 진행됩니다.

예를들어 앞서 2번에선 초기화를 1로 진행했고, 이번 연산에선 초기화한 값 1을 계속 ++ 해주는 방식으로 등장하는 key의 개수를  counting 해줄 수 있겠죠.

 

 

 

아래 구간은 개인적인 생각입니다.

---

4번 케이스를 보니 3번 케이스가 더 이상해 보이는데.. 하나씩 파헤쳐볼게요.

3번 케이스의 결과는 remappingFunction 결과에 의존하죠. Java docs에서 remappingFunction은 'the function to recompute a value if present'로 정의합니다.

 

값이 존재하면, 다시 계산하는 함수.

 

즉, key에 대한 값이 존재하면 다시 계산하는 함수입니다.

3, 4 모두 이미 key에 대한 값이 존재했었는데, 이때 다시 계산 즉, 기존 값에 어떤 연산을 진행해 덮어쓴다는 의미로 해석됩니다.

4번 케이스에서 13의 값과 -1을 remappingFunction을 통해 연산 후 새로운 값으로 대체하기도 했구요.

또한, remappingFunction(oldValue, value);로 표기되어있는데, 두 값을 이용해 처리한 결과로 value의 값을 갱신해주어야하는데, 그 값이 null이니, map에 저장할 필요성이 없어진 것이죠.

 

특히, 해시맵의 경우 hash를 통해 데이터를 저장하기에, 비둘기집 원리에 의해 많은 데이터를 저장할 수록 해시 충돌의 가능성이 높아질텐데, 데이터를 굳이 저장할 필요는 더욱 없어보입니다.

그게 아니더라도 공간 낭비겠죠. 단순 unique 데이터 체크를 위한 처리라면 Set 자료구조를 쓰는게 맞겠구요.

---

위 내용에 대한 반대/동의 어떤 의견이든 좋으니 댓글로 남겨주시면 다시 한 번 고민해보겠습니다.

 

 

 

 

 

 

 

 

이렇게 Map 그리고 merge의 내용이 끝났습니다. 사용법은 뭐... 각 wrapper 클래스마다 존재하는 메서드 뒤적거려보세요. ㅎㅎ

이외에도 다른 내용에 대한 이야기들 댓글로 남겨주시면 함께 이야기해보면 좋을 듯 합니다. 감사합니다.

 

 

 

 

참고 자료

Stack Overflow - keySet vs entrySet

Java docs - Map merge