java에서 STL의 multimap 구조를 구현해 봅시다.

 C++의 STL에서 multimap은 상당히 유용하게 쓰입니다. Java에서는 그렇게 쓸 수 없을까요? 저는 Key값이 중복되는 경우에도, Map 계열에 저장하고 싶습니다. 어떻게 하면 좋을까요?

 

---

 그 전에 Java의 Map 계열이 어떻게 동작하는지 간단하게 정리하고 가겠습니다. map.find(K)를 호출했을 때 개략적인 흐름을 보겠습니다. 먼저, map 계열이 키가 K인 값을 찾는 구조입니다.

 

  그러면, 자료구조에서 Key가 K인 것을 찾는데, 이 작업을 하기 위해 내부적으로 호출되는 메서드가 equals입니다.

 

 

 put(K,V')가 호출되었을 때, Key가 K인 것이 존재했다면, 데이터 <K, V>를 <K, V'>으로 덮어씁니다. 즉, <K, V>, <K, V'>가 같이 저장될 수 없습니다. 예를 들어, K가 가수이고, V가 발매한 앨범이라고 해 보겠습니다. Key duplicate를 허용하지 않는 구조라면, a라는 가수가 b1과 b2를 발매했다고 했을 때, 이 정보를 map에 저장하면, a가 b2를 발매했다는 정보밖에 저장이 안 됩니다.

 

---

 그러면 어떻게 해야 할까요? Value 부분에 여러 값들을 저장할 수 있게 해야합니다. 예를 들자면, arrayList와 같은 것들이 이에 속합니다.

 

 이것을 코드로 구현하면 아래와 같습니다.

 

 

 String을 Key값으로, String을 모아놓은 ArrayList를 Value로 잡은 TreeMap tm을 선언했습니다. 만약에 Key값이 중복되는 경우가 들어오면 어떻게 될까요? Value에 추가하기만 하면 됩니다. 예를 들어, <K, b3>이 추가되었다고 한다면 아래와 같습니다.

 

 

 단지 value에 b3을 add 한 것 뿐입니다. 이것을 코드로 보여보겠습니다.

 

 

 K라는 key가 없는 경우에는, 새로운 ArrayList를 추가합니다. 있는 경우에는 tm.put을 할 필요가 없습니다. 단지 기존에 있는, Value가 품고 있는 자료구조에 V를 add를 하면 됩니다. 없는 경우에, 새로운 ArrayList를 만들어야 합니다. 이를 36번째 줄에서 처리하고 있습니다.

 

 

 이것을 computeIfAbsent와 람다식을 이용하면 매우 간단하게 해결할 수 있습니다. 이것은 레퍼런스나 자바 카데고리에서 언급할 일이 있을 겁니다.

 

---

 문제는 이런 상황입니다.

 

 가수 하나가 수백, 수천개의 앨범에 참여한 경우에는 어떻게 하면 좋을까요? 특정 앨범들은 수천명의 가수가 참여한 경우에는? 일단, 문제 상황에서 주어진 것은 가수 이름을 1차 기준으로 찾겠다는 것입니다. 그러면 당연하게도 Key를 가지고 Value인, 특정한 사람이나 그룹이 발매한 앨범의 목록은 쉽게 가져올 수 있을 겁니다.

 

 

  그런데, 정렬이 되어 있지 않은 ArrayList에서, 특정한 Value를 찾는 작업은 최악의 경우에 O(List에 있는 원소 갯수)만큼 걸립니다. 처음부터 끝까지 찾아봐야 하기 때문입니다. 이 부분을 개선하려면, 어떠한 Value 찾는 작업을 O(1)이나, O(log(원소 갯수))에 하면 됩니다. 답은 바로 나왔습니다. TreeMap이나 HashMap입니다.

 

 단순히 K값을 찾기 위한 용도로 쓰기 위해서는, TreeMap 보다는 HashMap을 쓰시는 게 좋습니다. Hash는 키값을 찾는 연산에 특화된 구조이기 때문입니다.

 

 tm을 이렇게 바꿔 보겠습니다. Key는 String이고, Value는 TreeSet <String>입니다. 발매한 앨범을 저장하는데, 그것을 TreeSet에다가 저장하는 셈입니다.

 

 

 당연하게도, data를 add 할 때는 이런 식으로 작성하시면 됩니다.

 

 

 가수 K가 V라는 앨범을 발매했는지 빠르게 찾기 위해서는 어떻게 하면 될까요? TreeMap에서 K가 있는지 먼저 알아야 합니다. 그러기 위해서는 containsKey 메서드를 이용하면 됩니다. 만약에 K가 있다면, Value에 V가 있는지만 판단하면 됩니다. 44번째 줄이 그러한 일을 수행합니다.