java map find key in value : 2개의 맵을 씁시다.

 java에서 hash나 tree 계열 (흔히 rb로 구현된) map은 key 값이 주어졌을 때, value를 빠르게 찾는 자료구조입니다.

 

 예를 들어, hash 계열의 map은 key 값을 가지고 계산된 hash 값을 가지고, 특정한 버킷에서 값을 찾아버립니다.

 

 

 Treemap이나 set은 정렬이 되어 있습니다. key값의 대소에 따라 정렬이 되어 있다면, 적절한 연산을 통해 O(log(size))의 복잡도로 찾기 연산을 수행할 수 있습니다. 문제는, 이런 경우입니다. 값을 기준으로 키도 빠르게 찾아내려면 어떻게 해야 할까요?

 

 

---

 TreeMap이나 HashMap이 Key값을 토대로 Value를 빠르게 찾아낸다고 했습니다. 반대로 생각하면 어떨까요? Value 값을 토대로 대응되는 키 값을 빠르게 찾아내려면, 키를 Value로, 벨류를 Key, 혹은 (K, V)를 저장하고 있는 객체로 하면 어떨까요?

 

 

 이렇게요. 단, v가 comparable하다면, tree 계열을 썼을 때 효율적으로 v에 대응되는 key 값을 찾을 수 있습니다. 당연하게도, 비교 함수나 equals 같은 것은 정의가 되어 있어야 할 거고, equal이 재정의되어 있다면 hashcode도 재정의를 해야 합니다.

 

 

 이 경우에는 두 말할 것도 없이, equals랑 hashcode가 재정의 되어 있어야 합니다. 저는 이것을 Value - Key 트릭이라 부릅니다. 이제, 어떻게 이것을 구현하는지, 예제 프로그램을 보도록 합시다.

 

 

---

 맵에는 (k, v)꼴로 들어옵니다. 추가되는 pair 중에서, 임의로 pair를 2개 골랐다고 해 봅시다. p1과 p2 이렇게요. p1의 k값과, p2의 k값이 같고, p1의 v값과 p2의 v값이 같은 경우가 없습니다. 그리고 pair가 삭제되는 쿼리가 들어왔을 때, 맵에 있는 것만 삭제가 된다고 해 봅시다.

 

 예를 들어, 추가되는 pair가 (1, 1), (2, 3), (4, 7)일 수는 있지만, (1, 1), (2, 2), (1, 1)일 수는 없습니다. p1과 p3의 k값과 v값이 같기 때문입니다.

 

 

 한 키에 여러 value가 들어오는 경우를 처리하기 위해서, ori와 rev의 Value 부분 역시 Map으로 선언하였습니다. 이제 (k, v) 쌍을 추가하는 코드를 보겠습니다. 당연하게도, 두 개의 맵에 정보가 업데이트 되어야 합니다.

 

 

 computeIfAbsent 메서드로 처리하였습니다. 10번째 줄은, 키값 k가 없을 때에 람다 식을 수행하게 됩니다. 해당 람다식은, 단순히 새로운 해시맵을 리턴해 줍니다. 즉, 10번째 줄은, k가 없을 때, 새롭게 해시맵을 만듭니다. 있으면 당연하게도, 기존에 있는 값을 쓸 거고요.

 

 dp 배열을 채울 때도 왕왕 이용되는 트릭이라고 스택 오버플로우 질답 글에도 나와 있습니다. 다음에 getbyKey와 getbyValue입니다. 이 둘은 각각 Key 값이 k인 v값, Value가 v인 k를 빠르게 찾습니다.

 

 

 여기서 하나 더 나온 것은 ArrayList 생성자입니다. 이 안에, getOrDefault 메서드가 들어갔는데요. 이것은 키가 있으면, 키에 대응되는 value를, 없으면 2번째 인자인 default 값을 리턴합니다. 보통 get 함수는 키가 없을 때에는 null을 리턴합니다. 그런데, 생각보다 널 처리는 까다롭습니다. 그래서 저는 빈 컬렉션을 반환하였습니다. 이펙티브 3편의 54에서도 언급된 부분입니다.

 

 이러한 일을 get만 가지고 하려면, get을 한 결과가 null이면 빈 배열을 리턴하라는 3항 연산자나, if 문이 추가 되어야 합니다. 그런데, 저 메서드 하나면 간단하게 처리되는 일입니다.

 

 

 getbyValue도 마찬가지입니다. 중요한 것은 rev에서 찾는다는 것입니다.

 

 

 제거는 어떻게 할까요? 이것 역시 getOrDefault를 이용하면 생각보다 간단하게 처리할 수 있습니다. 먼저, ori에서 key값이 k인 것을 찾고, 없으면 빈 hashmap을 반환합니다. 반환된 컬렉션을 향상된 for 문으로 루핑을 하고 있습니다. 단순히 키 값이 key인 value 값들, 혹은 value 값이 value인 key값만을 가지고 오려면, 24 ~ 25번째 줄만 처리해도 됩니다. ori에서 (k, v)쌍을 삭제하고, rev에서 (v, k)쌍에 대한 정보만 삭제하면 되기 때문입니다.

 

 

 이제 테스트를 해 봅시다.

 

 

 

 제대로 나오는군요.