Java Collections Framework(JCF)란? - Map (JAVA)

안녕하세요? 제이온입니다.

 

오늘은 JCF의 마지막 시간으로, Map 인터페이스를 알아보겠습니다.

 

 

Map Interface

Key와 Value를 쌍으로 저장하는 자료구조로, Key는 중복될 수 없고 Value는 중복이 가능하다는 특징이 있습니다. Key를 통해 Value에 바로 접근이 가능하므로 상수 시간만에 탐색이 가능하다는 장점이 있습니다. 하지만, 데이터의 순서를 보장하지는 않습니다. 주로 사용하는 메소드는 아래를 참고하시면 됩니다.

 

 

 

 

흥미로운 점은 Map에는 내부 인터페이스인 Entry가 정의되어있습니다. 이 부분도 같이 살펴봅시다.

 

 

Map.Entry Interface

Entry는 Key-Value 쌍을 말합니다. 주로, getKey()나 getValue()를 통해 Key와 Value의 값을 얻어오는 데 많이 사용합니다. 이것은 인터페이스이므로 실제 코드에서 사용하려면 구현 클래스가 필요한데, 직접 Map.Entry를 상속받아서 오버라이드된 메소드를 싹 정의한 클래스를 설계하거나 AbstractMap.SimpleEntry을 이용하면 됩니다. 만약, JAVA 9 버전이상일 경우는 Map.entry()로 쉽게 정의가 가능합니다.

 

 

    Entry<Integer, Integer> entry = new SimpleEntry<>(1, 2);
    Entry<Integer, Integer> entry2 = Map.entry(1, 2);

 

 

버전만 호환된다면 주로 Map.entry()을 사용하는 편입니다.

 

 

Hashtable Class

Map 인터페이스의 구현 클래스이며, 자바 초기 버전에 나온 레거시 클래스입니다. Key와 Value가 null값이면 안 되고, 동기화가 되어있다는 특징이 있습니다.

 

 

 

 

해시 테이블은 Key를 특정 해시 함수를 통해 해싱한 후 나온 결과를 배열의 인덱스로 사용하여 Value를 찾는 방식으로 동작합니다. 여기서, 해시 함수는 Key를 Value가 저장되는 주소 값으로 바꾸기 위한 수식을 의미합니다. 이번 포스팅은 해싱과 관련된 포스팅은 아니므로 해시 함수는 제 임의로 정의하겠습니다.

 

예를 들어, key의 값이 0 ~ 9이 있고, HASHTABLE_SIZE는 10이라고 가정하겠습니다. 해시함수가 'h(x) = x'라고 한다면,  table[0] = 0, ... table[9] = 9로 차곡차곡 Key - Value 쌍을 넣으면 될 것입니다. 하지만, 만약에 HASHTABLE_SIZE가 5라면 어떨까요? 주어진 메모리로는 모든 데이터를 저장할 수 없습니다.

 

기존의 해시함수 대신 'h(x) = x % HASHTABLE_SIZE'를 사용하여 0 % 5, 1 % 5, ... , 9 % 5를 취한다음 그 값을 인덱스로 하여 Key - Value 쌍을 저장할 때도 문제가 생깁니다. 예를 들어, 0과 5는 인덱스 값이 0으로 서로 같습니다. 그렇다면, table[0]에는 key가 0이 들어갈지 5가 들어갈지 알 수 없게 됩니다. 그리고 이러한 현상을 '해시충돌'이라고 부릅니다.

 

해시충돌을 방지하기 위해서는 주로 체이닝 기법이 사용되는데, 체이닝 기법은 LinkedList를 활용하여 저장하려는 해시테이블의 이미 같은 key의 데이터가 있다면, 노드를 추가하여 다음 노드를 가리키도록 구현하는 것을 말합니다.

 

 

 

 

실제 JDK 내부에서도 채택하는 방법이며, 이 기법을 위해서 용량과 load factor를 사용합니다. 참고로, 각 인덱스마다 데이터가 들어가는 공간을 버킷(bucket)라고 부릅니다.

 

 

 

 

그리고 실제로, Hashtable의 생성자를 보면, 용량과 load factor를 설정할 수 있습니다. 인자로 두 개 다 넘기는 것은 생략하였습니다. 여기서, 용량은 '버킷의 개수'와 같으며 load factor는 '저장된 데이터 / 용량'과 같습니다.

 

자, 이제 예를 들어서 20만 개의 데이터를 추가하였고 버킷의 개수는 10개라고 칩시다. 그렇다면, 평균적으로 하나의 버킷에는 20,000개의 노드가 저장되어있으므로 원하는 key를 찾기 위해서 equals() 연산을 20,000만 번 실행해야할 것입니다. 성능이 아주 느려지겠죠. 따라서, 버킷의 개수가 고정되어있고 저장된 데이터만 증가하다가 load factor가 0.75가 되는 순간 해시테이블은 리사이징 작업을 수행합니다.

 

 

 

 

리사이징은 버킷의 개수를 늘려주는 작업으로, 새로운 배열에 기존의 Key를 새롭게 재해싱합니다. 그리고 보통 버킷의 개수를 기존의 개수에 2배 정도 늘립니다.

 

load factor가 작으면 용량의 크기가 커지므로 메모리를 더 많이 차지하지만 검색 속도가 빨라진다는 장점이 있고, load facor가 크면 용량의 크기가 작으므로 메모리를 더 적게 차지하지만 검색 속도가 느려진다는 단점이 있습니다. 용도에 맞게 바꿀 수는 있겠지만, API에서는 이상적인 load facor를 0.75로 정했고 사실 거의 이를 건드릴 일은 없습니다.

 

다만, 저장될 데이터가 많다면 초기 용량정도는 늘려주는 것은 바람직하다고 봅니다.

 

 

HashMap Class

Map 인터페이스의 구현 클래스이며, Hashtable을 보완하였습니다. HashMap은 비동기로 작동하기때문에 멀티 쓰레드 환경에서는 어울리지않지만, 이것도 보완하기 위해서 ConcurrentHashMap이 나왔습니다. 그렇다면, Hashtable과 ConcurrentHashMap의 차이가 궁금할 수 있는데 이 부분은 이곳을 참고하시길 바랍니다.

 

해시맵은 해시테이블과 거의 비슷하나, 비동기적이고 Key와 Value를 null로 설정해도 된다는 차이가 있습니다. 그리고 해시테이블의 초기 용량은 11이었지만, 해시맵은 16입니다.

 

 

 

 

그리고 지금까지 Hashtable과 HashMap을 이해하였으므로 HashSet의 작동 과정도 이해한 것이나 다름없습니다. HashMap을 통해서 HashSet을 구현한 것이기때문이죠.

 

 

LinkedHashMap Class

LinkedHashMap 클래스는 Map 인터페이스의 구현 클래스인 동시에 HashMap을 상속받았습니다. 그리고 데이터의 순서를 보장한다는 특징이 있습니다. (A, 1), (B, 2), (C, 3)을 Entry로 put하고나서 forEach()를 돌리면 이 순서가 그대로 반환됩니다.

 

그렇다면, 어떻게 LinkedHashMap을 순서를 보장하는 것일까요? 간단히 말하면, 이 안에서 LinkedList처럼 동작을 합니다.

 

 

 

 

이렇게 HEAD, TAIL을 설정해 놓고 중간에 노드인 Entry를 연결하여 구현하는 방식입니다. LinkedList는 순서를 유지하는 자료구조라고 하였으므로 그 특성을 이용한 것이죠.

 

우리는 LinkedHashMap을 이해하였기때문에 LinkedHashSet의 작동 방식을 알 수 있게 되었습니다.

 

 

SortedMap Interface

SortedSet 인터페이스와 거의 같습니다. SortedMap 인터페이스도 특정 기준으로 요소를 정렬할 수 있도록 해 줍니다.

 

 

 

 

default 설정은 key를 기준으로 오름차순 정렬이지만, Comparator을 정의해 주거나 Comparable를 상속받아 compareTo를 오버라이드 정의한 객체를 사용해 주어도 괜찮습니다.

 

 

TreeMap Class

TreeMap 클래스는 대표적인 SortedMap 인터페이스의 구현 클래스입니다. Key를 기준으로 원하는 대로 정렬을 할 수 있다는 특징이 있습니다. 이때, TreeMap은 레드-블랙 트리로 구현이 되어있습니다.

 

레드 블랙 트리는 다음과 같은 4가지 성질을 만족해야합니다.

 

 

1. 루트는 블랙이다.

 

2. 모든 리프(NIL)는 블랙이다.

 

3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

 

4. 로트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

 

 

여기서, 리프 노드는 우리가 알던 자식이 없는 노드가 아니고 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프 노드라 부릅니다.

 

 

 

 

위 사진은 레드 블랙 트리의 4가지 성질을 만족한 트리입니다. 이 상태에서 추가나 삭제를 하려면 4가지 성질을 만족하면서 변경을 해야합니다. 자세한 레드 블랙 트리에 대한 설명은 이곳을 참고하시길 바랍니다.

 

 

이렇게 TreeMap이 레드 블랙 트리로 구현되어있다는 것을 알았으니 TreeSet도 레드 블랙 트리를 기반으로 작동한다는 사실도 이해하실 수 있습니다.

 

 

Map 인터페이스는 왜 Collection 인터페이스에게 상속을 받지 않았을까?

Java Collections Framework에서 Map은 Collection 인터페이스에 속하지가 않습니다. 왜 그럴까요?

 

우선, JCF 개발자들은 데이터 저장 방식을 List, Set, Map으로 처음 생각하였습니다. List와 Set은 비슷한 점이 많아서 Collection 인터페이스로 묶을 수 있었지만, Map은 구조상 Collection 인터페이스로 묶을 수가 없었습니다.

 

Collection은 요소들의 집합이라고 생각하면 되는데, Map은 요소라는 것을 정의하기가 어렵습니다. Map은 Key와 Value가 필요한데, 요소로 만드려면 Key-Value 쌍을 생각할 수 밖에 없습니다.

 

예를 들어, Collections.remove(Object o)를 취한다고 합시다. 만약, Map이 Collection에 상속을 받았다면, remove()는 단순히 Key-Value 쌍을 지우게 될 것입니다. 하지만, 실제 Map의 remove()의 인자는 key를 받습니다. 이것은 번거롭게 인자를 Key-Value 쌍 형태의 객체로 받지 않기 위함입니다.

 

이렇듯 요소라는 것의 모호함과 구조상 상응하지 않는 부분이 많아서 Map은 JCF에 포함하되, Collection 인터페이스에게 상속은 받지 않도록 설계한 것입니다.

 

비슷한 맥락으로, Map 인터페이스에는 Iterable 인터페이스를 상속받지 않아서 iterator()가 존재하지않는데, 이것은 iterate할 대상이 key인지 value인지 key-value 쌍인지 알 수 없어서 그런 것입니다.

 

 

정리

지금까지 Map 인터페이스에 대해 전반적인 개념을 다뤄보았습니다. 이것을 끝으로 JCF 포스팅을 마치겠습니다.

 

 

출처

[Java] HashMap의 element 저장 방식(bucket) - Onsil's blog

 

 

해시 테이블(Hash Table)

 

How linkedhashmap maintains insertion order

 

 

Why does Map not extend Collection interface