이전 내용에 이어서 Collection Framework의 Set과 Map 자료구조에 대해 정리해 보겠다.

이전 글을 읽지 않은 사람은 이전 글을 참고하자.

Map

Map은 키와 값의 한 쌍으로 이루어진다. 순서가 없고 값은 중복을 허용하며 키는 중복을 허용하지 않는 자료구조의 최상위 인터페이스이다.

구현체로는 HashMap, TreeMap, LinkedHashMap 정도가 있다.

1. HashMap

순서를 유지하지 않고 Key와 Value값으로 null을 허용하며, 내부적으로 배열을 이용해서 구현된 구현체이다.

Map의 Key값을 해싱함수를 이용하여 배열의 크기 보다 작은 정수형 데이터로 변환하고 인덱스로 사용한다.

예를 들어 String "첫번째"라는 Key값과 "데이터"라는 Value값을 HashMap에 저장한다면, "첫번째"라는 문자열은 HashMap에서 사용되는 해싱함수를 거치게 된다. ( 자세한 해싱 방법은 검색해 보도록 하자. )

해당 해싱함수를 거치게 되면 HashMap이 갖고 있는 배열의 크기 보다 작은 정수형 데이터가 반환된다. 여기서는 5가 반환되었다고 하자.

그럼 5라는 값은 배열의 index가 되어 "첫번째"라는 Key값을 통해 Map에 접근할 경우 내부적으로 배열 인덱스 5에 해당하는 값을 참조할 수 있도록 한다.

장점

1. 조회, 추가, 삭제가 빠르다.

내부적으로 배열을 이용하여 데이터에 접근하기 때문에, 데이터에 대한 접근 속도가 O(1)이고 추가 삭제도 오래 걸리지 않는다.

단점

1. 오버헤드가 있다.

사실 HashMap에는 문제점이 한 가지 있다.

내부적으로 해싱함수를 사용한다 했는데, 잘 생각해 보면 서로 다른 Key값에 대해 해싱함수가 반환하는 정수가 겹치지 않을 거라는 보장이 없다.

실제로 중복되는 현상이 발생하기도 한다.

Key가 중복되는 경우에 다른 배열의 인덱스에 데이터를 저장하는 건 불가능하다.

해싱함수를 사용하기 때문에 임의로 다른 인덱스에 데이터를 저장하는 건 해당 Key값에 대해 이후 데이터 조회가 불가능해진다.

이러한 문제점을 해결하기 위해 JAVA에서는 여러 가지 대안을 구현해 놓았다.

1. 배열 늘리기

너무 당연하지만, 배열에 데이터가 쌓일 수록 인덱스가 겹칠 확률을 더 높아 진다.

그래서 배열이 75% 이상 차게 되면 HashMap의 배열 크기를 2배 늘리도록 구현하였다.

2. 다음 노드 참조하기

인덱스가 겹치는 경우 같은 인덱스에 여러 데이터를 저장할 수 있도록 방식을 구현해 놓았는데, 저장되는 Value가 다음 Value를 참조하도록 구현하는 것이다.

Map은 데이터를 저장할 때, 기존의 데이터를 그대로 저장하는 게 아니라 Node라는 클래스 형태로 저장한다.

해당 Node에 next라는 변수가 다음 Node를 참조할 수 있도록 구현하여 서로 다른 Key가 같은 인덱스로 해싱되더라도 LinkedList처럼 계속해서 저장되도록하는 것이다.

3. TreeNode로 변경하기

2번에서 다음 노드를 참조하는 방식은 참 좋긴하지만 문제점이 있다. 같은 인덱스에 있는 데이터가 너무 많아질 경우이다.

LinkedList의 데이터 조회 시간은 O(N)이다. 그렇기 때문에 데이터가 많아질 경우 데이터 조회 속도가 느려질 수 있다.

이러한 문제점을 또 해결하기 위해, 비교적 조회속도가 빠른 Tree구조를 사용한다(트리 구조 중에서도 Red-Black Tree를 사용).

일정 충돌횟수(같은 인덱스에 저장되는 횟수)를 넘어갈 경우 기존의 Node들을 TreeNode라는 것으로 전부 교체하는 작업이 일어난다.

이 TreeNode는 Tree의 자료구조 형태를 띄도록 구현되어 있기 때문에, 조회 속도가 O(logN)으로 기존의 O(N)보다 빠르다.

이처럼 HashMap의 인덱스 충돌 문제를 해결하기 위해 여러 대안을 마련했고, 그로 인해 실제 동작은 약간의 오버헤드가 발생하는 단점이 있다.

Key 중복 확인

위의 단점을 읽어 보았다면 Key의 중복 체크 과정도 이해할 수 있다.

Key값을 해싱해서 나온 인덱스에 저장된 모든 Node들을 탐색하며 새 데이터의 Key값과 기존 Node들의 Key값을 equals()메소드로 비교한다.

그 과정에서 true를 반환하는 경우의 수가 생기면 Key가 중복인 것으로 판단하여 예외를 발생시키는 것이다.

위처럼 중복체크 과정에서 모든 Node를 순회하지 않고 해싱을 이용하여 같은 인덱스의 Node들만 순회하기 때문에 효율적이다.

사용

일반적으로 Map을 사용한다면 대부분 HashMap을 사용하게 된다.

2. TreeMap

TreeMap은 Map에서 Key값을 이진 탐색 트리(정확히는 Red-Black Tree) 형식으로 저장하여 특정 정렬 기준에 따른 정렬을 지원한다. 정렬을 해야 하기 때문에 Key값으로 null을 허용하지 않지만, Comparator를 커스텀하는 경우 null을 고려하여 작성한다면 허용할 수 있다.

장점

1. Key에 정렬기준을 부여할 수 있다.

정렬 기준을 커스텀하여 지정할 수가 있다.

단점

1. 일반적인 조회, 추가, 삭제가 비교적 느리다

데이터가 추가되면 정렬이 일어나기 때문에 정렬 비용이 있고, 배열을 사용하는 HashMap과는 비교적 데이터 처리 속도가 느리다.

사용

Key값을 특정 정렬 기준에 따라 정렬을 유지하거나, 범위 검색이나 범위 순회가 필요하다면 유용하다.

3. LinkedHashMap

HashMap을 상속받아 기존의 HashMap과 같은 동작을 하면서도, 내부적으로 HashMap의 Node클래스를 상속받는 Entry클래스 라는 것을 만들어, 데이터가 삽입된 순서대로 연결리스트의 형태를 유지하도록 하는 구현체이다.

기존의 HashMap과 똑같지만, 삽입된 순서만 유지된다는 차이가 있다.

장점

1. 삽입된 순서대로 정렬된다.

데이터가 삽입된 순서를 유지한다.

단점

1. HashMap에 비해 메모리, 성능 효율이 약간 떨어진다.

데이터를 연결하기 위한 메모리 공간이 더 필요하고, 성능이 조금 떨어진다. 큰 차이는 아니다.

사용

HashMap의 성능과 입력 순서를 유지하는 장점을 모두 갖기 때문에 순서가 중요한 상황에서 사용 가능하다.

Set

Set은 순서가 없고 중복을 허용하지 않는 형태를 갖는 자료구조의 최상위 인터페이스이다.

Set은 위의 Map을 이해했다면 사실 설명할 것이 없다.

Map의 Key값의 특징을 그대로 사용한 것이 Set이고 실제로 Set의 구현체들은 Map을 이용해서 구현하였기 때문이다.

구현체에는 HashSet, TreeSet, LinkedHashSet이 있고, 모두 위의 HashMap, TreeMap, LinkedHashMap에서 Value를 빼고 Key만 이용한 형태라고 생각하면 된다.

정리

Collection Framework를 정리하다 보니 이해가 확실히 부족했었다는 것이 느껴졌다.

이제는 어떤 상황에서 어떤 자료구조를 사용하면 좋을지, 그리고 내부적으로 어떤 원리로 돌아가는지 이해했으니 더 실용적으로 활용할 수 있을 것 같다.