[자바] 컬렉션(Collection) 2 - Map

안녕하세요!

자바의 컬렉션 2탄! 오늘은 Map에 대해서 알아보겠습니다.

 

자료구조? 컬렉션?

---

컬렉션을 알아보기 전에 자료구조라는 단어를 들어보셨을 텐데요 이는 프로그래밍 과정에서 데이터를 효율적으로 사용하기 위해 만들어진 것으로 배열, 리스트, 스택 등이 있습니다. 이 자료구조들을 사용하려 할 때 우리가 직접 구현해서 사용하기는 어렵고 귀찮기 때문에 자바에서 이 자료구조들을 구현하고 인터페이스화 시켜 개발자들이 사용할 수 있도록 제공하는 프레임워크를 컬렉션 이라고 합니다.

 

Map

Map은 키-값의 쌍으로 데이터를 저장하고 관리하는 자료구조입니다. 기본적으로 값의 순서를 유지하지 않으며 키의 중복값은 허용하지 않으나 값은 중복될 수 있습니다.

 

HashMap

---

HashMap은 해시 테이블을 기반으로 한 Map 구현체 입니다. HashMap은 배열, 연결 리스트, 트리의 혼합 구조로 이루어져 있습니다. 기본적으로는 해쉬코드를 통해 배열에 키-값 버킷을 저장하여 참조하게 되는데 해쉬 충돌이 발생할 경우 연결리스트로 버킷들을 관리하게 됩니다. 이후 연결리스트가 특정 크기를 넘어설 때 트리 형태로 변환되어 동작하게 됩니다.

 

장점

1. 빠른 데이터 접근이 가능하다

 - 키를 통해 1:1 매칭되는 값을 가지고 있기에 빠른 데이터 검색이 가능합니다.

 

단점

1. 순서를 보장하지 않는다.

 - 저장하는 순서를 관리하지 않습니다.

2. 해시 충돌이 발생할 수 있다.

 - 해시코드의 특성 상 해쉬 충돌이 발생할 경우 성능이 저하될 수 있다.

 

HashMap은 데이터의 순서에 상관없이 빠르게 검색이나 데이터를 저장할 경우 사용하는 것이 좋습니다.

 

LinkedHashMap

---

LinkedHashMap은 HashMap을 상속한 클래스 인데요 HashMap과 거의 동일하지만 데이터의 입력순서를 보장한다는것이 특징입니다. 이중 연결 리스트로 만들어져 내부 노드에 앞, 뒤 노드의 위치값을 참조하는 형태로 입력 순서를 유지할 수 있습니다.

 

HashMap보다는 약간 느리지만 입력 순서를 보장해야할 경우 사용할 수 있습니다.

 

TreeMap

---

TreeMap은 이름에서도 알 수있듯 Tree를 기반으로 만들어진 Map입니다. TreeMap의 주요 특징은 키를 기준으로 오름차순 정렬되어 저장한다는 것입니다.

 

장점

1. 정렬이 가능하다.

 - 키를 기준으로 오름차순 또는 사용자 지정 순서로 정렬이 가능합니다.

 

단점

1. 성능

 - Hash함수를 이용하는 Map에 비해 비교적 느린 성능을 보입니다.

 

내부구조

TreeMap에서 Tree는 이진 탐색 트리 기반의 레드-블랙 트리를 사용하는데요 노드에 키-값 쌍을 저장하는 형태입니다.

 

이진탐색트리

먼저 이진 탐색 트리는 각 노드가 최대 2개의 자식노드를 가지는 '이진 트리'와 데이터를 정렬된 순서로 유지하는 '탐색 트리'로서 데이터를 효율적으로 저장,검색,삽입,삭제 할 수 있습니다.

레드-블랙 트리

이진 탐색 트리의 일종이며 각 노드가 빨강 혹은 검정으로 색칠되어 레드-블랙 트리로 불립니다. 항상 균형을 유지하는 균형 트리로서 O(log n)의 시간복잡도를 보장함

 

Hashtable

---

 

Hashtable은 이름 그대로 해시 테이블을 기반으로 한 Map의 구현체인데요 스레드 안전(동기화)을 지원하는 것이 특징입니다. Hashtable도 HashMap과 비슷한 동작을 하지만 멀티스레드 환경에서의 안전성을 위해 스레드 안전을 지원합니다.

ConcurrentHashMap

---

ConcurrentHashMap은 Hashtable과 같이 스레드 안전을 지원하는 Map의 구현체입니다. 다만 성능적으로 더 우수한 Map인데요 메서드 전체에 락이 걸려있는 Hashtable에 비해 버킷 수준의 락을 통해 성능적으로 우수하며 해시충돌이 발생했을 때 연결리스트로 변환되는 Hashtable에 비해 리스트가 커졌을 때 Tree형태로 변환하여 성능적으로 우수합니다.

 

오늘은 자바 컬렉션중 Map과 구현체들에 대해 알아봤습니다.

감사합니다!