python에서 defaultdict는 아래와 같습니다.
- 키 값이 없을 때 자동으로 default factory를 호출해서 value로 넣는다.
- default factory에는 list, dictionary 등이 들어갈 수 있다.
저는 키 값이 없을 때 자동으로 대응되는 값을 넣어주기에 자주 쓰는 편입니다. java에서 비슷하게 할 수 없을까요? java computeifabsent 함수랑 wrap class를 이용하면 비슷하게 구현할 수 있습니다. 이 방법을 이 글에서 알아봅시다.
java computeifabsent 함수 내부 보기
먼저, 이 함수의 설명을 보겠습니다.
인자로 2개를 받음을 알 수 있어요.
- key
- mapping function
설명을 보면, 키가 없으면 mapping function 을 적용한 결과를 value로 하여 새롭게 엔트리에 넣는다. 정도로 설명하고 있는데요. 내부를 보도록 합시다.
복잡해 보이는데요. 1652번째 줄에 걸린 if문이 중요합니다. 먼저, get 함수로 key가 있는지 없는지를 조사합니다. 만약에 없으면, if문 내부가 실행됩니다. 그렇지 않으면 key에 대응되는 값을 돌려줍니다.
예를 들어 key값이 2이고 value가 [2, 3]인 것과, key 값이 3이고 value가 [3]인 것이 map에 저장되어 있다고 해 보겠습니다. 이 상태에서, key 값으로 2를 받았다면 value 값인 [2, 3]을 돌려줍니다. 만약에, key 값으로 4를 받았다면 어떻게 될까요?
- 맵에 key 4는 존재하지 않습니다.
- 그래서 새로운 value’를 만들고 key값이 4이고 value가 value’인 것을 map에 추가합니다.
고로, 이 함수에 key 값이 4가 넘어왔다면, 아래와 같이 실행될 겁니다.
이 value’가 어떻게 생성되는 것일까요? 1054번째 줄을 보면 아래와 같은 코드가 있습니다.
- newValue = mappingFunction.apply(key)
이 말은 2번째 인자로 넘어온 mappingFunction에 key를 집어넣어서 나온 결과를 newValue로 취한다는 것입니다.
이 mapping function은 k -> 2*k와 같이 함수 비슷한 문법으로 씁니다. 예를 들어 k -> 2*k는 k를 넣으면 2*k가 나오게 됩니다. k -> new ArrayList<>();는 k를 넣으면 새로운 ArrayList가 나오게 됩니다. 그러면 java computeIfAbsent 함수의 시간복잡도는 어떻게 될까요?
- get으로 찾는 O(1)
- put으로 넣는 O(1)
- applyFunction 복잡도
O(1)이지만, 최악의 경우 로그의 복잡도로 해결이 가능합니다. 이제 예제를 봅시다.
예제
파이썬의 defaultdict와 비슷하게 만든 예제입니다. 여기에서는 builder를 HashMap으로 한 것이 차이입니다. 이 클래스는 하나의 key에 여러 개의 value를 저장할 수 있습니다.
먼저, String을 key로 받고, Map<String, String>을 value로 받는 맵을 field로 선언하였습니다.
compute 함수는 이 클래스 내부에서만 쓸 것이기에 private로 선언해 주었습니다. 여기에서 이 글에서 나온 함수를 호출하는데요. mappingFunction을 보세요. k -> new HashMap() 이라고 되어 있어요. 이것은 무엇을 의미하는가? 아래와 같습니다.
- k 값에 상관없이
- 무조건 새로운 HashMap을 돌려준다.
즉, key가 없으면, value로 새로운 빈 HashMap을 만들어서 put을 하게 됩니다. 그림으로 그리자면, 아래와 같은 상황입니다. 아래와 같은 맵에서 compute의 인자로 “a”를 넘겨주었다 해 볼게요.
키 “a”가 없네요? 고로, 아래와 같은 일이 일어납니다. 새로운 해시 맵이 생성되고, “a”를 키로, 값을 새로운 해시맵으로 하는 데이터가 추가됩니다.
이제, 우리는 없는 키에 대해서도 접근을 하고 조작을 할 수 있어요.
이제 get과 put을 이용할 때, compute를 호출하면 되어요. 공통적으로 키가 없을 때 처리가 필요하기 때문입니다. get을 할 때, 원본이 아닌 복제본을 리턴하는 게 더 좋긴 하나, 여기에서는 따로 언급하진 않겠습니다.
하나의 키에 여러 값을 대응시키는 것은 put 함수를 보면 알 수 있어요. value가 단일 값이 아니라, 맵입니다. 따라서 여러 값을 넣을 수 있어요.
이제 main 함수를 볼게요. 보면, 처음에 빈 맵을 생성해 놓고, “a”에 무엇이 있나 조회합니다. 다음에, 키 값 “a”에 “c”와 “d”라는 value 값을 추가해요. 다음에, “b”라는 키 값에는 “d”라는 데이터를 추가해요. 다음에 키 값 “c”와 “d”에 걸린 value를 출력해요.
실행 결과는 위와 같아요. 하나의 키에 여러 value가 대응되는 경우 많이 구현되는 방식이니 참고하셔도 좋겠습니다.