Map 인터페이스
위 그림을 참고해보면 Map 인터페이스에는 HashMap, LinkedHashMap, HashTabel, TreeMap 등 다양한 구현체들이 있습니다.
이러한 구현체들의 특징을 간단히 살펴보겠습니다!
- 키와 값의 쌍으로 연관지어 이루어진 데이터의 집합
- 값(value)은 중복돼서 저장될 수 있지만, 키(key)는 해당 Map에서 고유해야만 한다.
- 만일 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.
- 저장된 순서가 유지되지 않는다.
HashMap
HashMap이란 키-값 쌍으로 데이터를 저장하는 자료구조 중 하나입니다. 이는 HashTable이라는 자료 구조를 기반으로 하며, 데이터의 조회, 삽입, 삭제 등의 작업을 평균적으로 상수 시간(O(1))에 처리할 수 있기에 자주 사용되는 자료구조입니다.
이러한 HashMap의 핵심 원리는 Hashing입니다
해싱이란, 데이터를 고유한 숫자값인 해시 값으로 변환하는 작업으로, 결괏값인 해시 값은 해시 맵의 인덱스로 사용되며, 이를 통해 해당 데이터를 빠르게 조회할 수 있습니다. 이러한 성능을 내려면 우선 해시 함수는 같은 키에 대해 같은 해시값을 반환해야겠죠??
혹시 hash나 hash Collison등에 대한 개념이 생소하시다면
https://wookjongbackend.tistory.com/15
이 글을 먼저 읽고 오시는 것을 추천드립니다. 해시, 해시함수, 해시 충돌 및 해결 방안들을 아주 상세히 다루고 있으니 차근차근 읽어보신 후 다시 오시면 이후의 글을 이해하시기 좋을 거예요 :)
해시 충돌(두개의 키가 동일한 해시 값을 생성하는 경우)을 해결하는 방법에는 무엇이 있었죠??
개방 주소법(Open Addressing)과 분리 연결법(Seperate Chaining)이 있습니다.
자바 Collection내 HashMap, HashTable, HashSet 등의 클래스들은 내부적으로 해시 충돌을 해결하기 위해 체이닝 방법을 사용합니다
체이닝 방식이란 명칭에서 잘 표현되듯, 각 버킷에서 연결리스트를 사용하여 키-값 쌍이나 요소를 저장하는 방식입니다.
Load Factor(부하 계수)는 혹시 무엇인지 아시나요???
이는 현재 테이블(or 맵)이 얼마나 가득 찼는지를 나타내는 지표입니다. 예를 들어, 해시 테이블의 버킷수가 16개이고, 현재 8칸에 키-값 쌍이 들어있다면 부하 계수는 0.5입니다.
저는 이에 대해 공부하면서, 처음에는 16개의 버킷중 예를 들어 3번 버킷에 8개의 키-값 데이터가 체이닝 형식으로 들어가도 load factor가 0.5인 건가? 하는 의문이 있었습니다. 하지만 이에 대해 알아보니 이 경우의 load factor는 1/16입니다.
여러분은 이런 부분에 대해 헷갈리지 않으셨음 해서 간단히 적어보았습니다 ^^
위와 같은 경우 특정 버킷이 가득차도 전체 해시 테이블의 공간 효율성에는 크게 영향을 미치지 않지만, 해당 버킷에 대한 검색 성능은 저하될 수 있겠죠??
그럼 이러한 부하 계수를 왜 다루었느냐?? HashMap은 부하 계수가 특정 임계값(ex:0.75)을 넘으면, HashMap은 재해싱을 수행합니다.(기본값은 0.75이지만 인스턴스 생성 시 지정 가능)
재해싱이란 해시 테이블의 버킷 수를 늘리고, 모든 키-값 쌍을 새로운 버킷 위치에 재배치하는 과정입니다. 이러한 과정을 통해 HashMap은 효율적인 성능을 유지할 수 있습니다!
이러한 여러 장점을 가지고 있는 HashMap을 사용할때는 주의해야 할 점이 있습니다!
기본적인 HashMap은 여러 스레드에 의해 동시에 접근될때 안전하지 않습니다. 따라서 멀티스레드 환경에서는 HashTable, ConCurrentHashMap을 사용하거나, Collections.synchronizedMap 메서드를 사용하여 동기화를 제공해야 합니다.
여러 스레드에 의해 동시 접근될때 안전하지 않다...? 이 말 되게 애매하시지 않나요?? 저는 처음에 그렇더라고요...
그래서 간단한 예시를 한 개 다루어보겠습니다!
스레드 A와 스레드 B가 동일한 HashMap에 접근하여 값을 변경하려고 한다고 가정해 봅시다. 스레드 A는 key1에 대한 값을 value1으로 설정하려 하고, 스레드 B는 key1의 값을 value2로 설정하려고 합니다.
이 경우 두 스레드가 거의 동시에 실행되면, key1의 최종 값이 무엇인지 예측하기 어렵습니다. 즉 스레드 B가 먼저 실행된다면 key1의 값은 value1이 될 것이고, 스레드 A가 먼저 실행된다면 key1의 값은 value2가 되겠죠?
이를 보면서 괜히 테스트 코드가 생각나더라고요
또한 두 스레드가 동시에 같은 키에 put 연산을 수행한다면 한 스레드의 변경 사항이 덮어씌워질 수 있겠죠?? 이러한 불상사를 막기 위해 동기화 처리를 해주거나, 멀티 스레드 환경에서 동기화된 클래스(ex:ConcurrentHashMap)를 사용하는 것이 좋습니다. 이러한 맵은 동시에 맵에 접근하는 스레드 사이에 동기화를 보장하여 위와 같은 문제를 방지합니다.
요약하자면 HashMap은 구조와 동작 원리 때문에 데이터를 빠르게 저장하고 조회하는 데 사용되는 중요한 자료구조입니다. 다만 충돌처리, 부하 계수와 재해싱, 동시성 등의 문제를 적절히 처리해야만 이들 성능 특성을 제대로 활용할 수 있습니다!
LinkedHashMap
앞선 HashMap은 키-값 쌍을 저장할 때 저장 순서를 보장하지 않습니다. 즉 원소들이 추가된 순서나, 키/값의 자연스러운 순서와 무관하게 원소들이 저장됩니다.
왜냐하면 HashMap은 내부적으로 해시 함수를 사용하여 값들을 버킷에 분배하기 때문입니다. 따라서 순차적으로 접근할 경우 예상한 순서대로 원소를 얻지 못할 수 있습니다!
반면 LinkedHashMap은 HashMap을 확장하여 원소들이 저장된 순서를 유지합니다. 따라서 순차적으로 접근하면 원소가 추가된 순서대로 접근할 수 있습니다.
이는 LinkedHashMap이 각 원소를 이중 연결 리스트로 연결하여 순서를 유지하기 때문입니다. 이러한 특성 덕분에 최근에 접근한 원소나 가장 오래전에 접근한 원소에 빠르게 접근하는 것이 가능합니다.
물론 HashMap과의 공통점도 많겠죠?
이 두 클래스는 모두 키의 중복을 허용하지 않고, 값의 중복을 허용합니다. 또한 둘 다 null키와 null값을 허용합니다.
그러나 HashMap이 성능 측면에서 조금 더 효율적이겠죠???
왜냐하면 LinkedHashMap은 추가적인 공간을 사용하여 원소의 순서를 유지하기 때문입니다. 따라서 원소의 순서가 중요한 경우 LinkedHashMap, 순서가 중요하지 않고 성능이 중요하다면 HashMap을 사용하면 좋습니다!
HashTable
해시 테이블 또한 모두 키-값 쌍을 저장하는 해시 기반 자료구조이지만, 동기화 지원 여부와 null값 허용 여부의 차이가 있습니다.
HashMap은 키와 값의 null을 허용하지만 HashTable은 null키나 값이 있으면 NullPointException을 던집니다.
HashMap은 일반적으로 동기화되지 않은 자료구조로 앞서 설명했다시피 멀티 스레드 환경에서 사용할 때 안전하지 않습니다.(Thread Safe X)
반면 HashTable은 자체적으로 동기화 기능을 제공하기 때문에, 멀티스레드 환경에서 안정적으로 사용할 수 있습니다.
하지만 단일스레드 환경에서 HashMap이 HashTable보다 더 빠른 성능을 제공합니다. HashTable은 동기화를 위한 많은 오버헤드가 발생하지만, HashMap은 이러한 오버헤드가 없어 일반적으로 성능이 더 좋은 편입니다.
또한 자바 8부터는 HashMap의 성능을 개선하기 위해 링크드 리스트를 밸런스 트리로 바꾸는 변경사항이 있었습니다. 이는 특정 조건(LinkedList의 크기가 임계값을 넘을 경우)에서 발생하며, 이러한 변경사항은 성능향상에 크게 기여하였습니다.
그렇다면 멀티스레드 환경이면 무조건 HashTable을 사용해야 할까요??
자바 1.5부터는 ConcurrentHashMap이라는 클래스가 제공되는데, 이는 HashMap의 Thread Safety를 보장하면서도 높은 성능을 유지하는 방법을 제공합니다.
HashTable, ConcurrentHashMap 모두 자바 동시성 환경에서 Thread-safe 하게 사용할 수 있습니다.
하지만 성능적인 측면에서 큰 차이를 보입니다.
HashTable은 메서드가 동기화되어있으므로, 한 번에 하나의 스레드만이 HashTable 메서드를 사용할 수 있습니다. 이는 공유 자원에 대한 동시 액세스를 방지하지만 성능에 약간의 오버헤드를 추가합니다.
반면 ConcurrentHashMap은 HashTable과 달리 데이터의 특정 부분(segment or bucket)만을 잠글 수 있는 동시성 레벨을 제공합니다. 이는 여러 스레드가 동시에 ConcurrentHashMap의 서로 다른 버킷에 엑세스 할 수 있음을 의미합니다.
따라서 동시성 환경이라면 HashTable보다 ConcurrentHashMap을 사용하는 것이 성능적으로 더 좋습니다.
TreeMap
TreeMap이란 Red-Black 트리를 기반으로 한 Map 구현체입니다. TreeSet과의 차이점을 보자면 TreeSet은 그냥 값만을 저장한다면, TreeMap은 키와 값이 저장된 Map.Entry를 저장한다는 점입니다.
이러한 TreeMap에 객체를 저장하면 자동으로 정렬이 되는데, 키는 저장과 동시에 오름차순으로 정렬됩니다.
예를 들어 숫자 타입의 경우엔 값으로, 문자열 타입의 경우엔 유니코드로 정렬을 하게 됩니다.
정렬 순서는 기본적으로 부모 키 값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에, 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장합니다.
이러한 TreeMap은 일반적으로 Map 구현체들에 비해 성능이 떨어집니다.
HashMap, HashTable, ConcurrentHashMap은 삽입, 조회, 삭제에 O(1)의 상수 시간 복잡도를 제공하는 것과는 대조적으로 Tree Map은 O(log N)의 시간복잡도를 가집니다.(3개의 클래스가 무조건 삽입,조회,삭제에 O(1) 시간 복잡도는 아니겠죠?? 해시 충돌이 나타나는 경우 O(N)의 시간 복잡도를 가집니다)
왜냐하면 이는 Red-Black Tree라는 자료구조를 기반으로 하기 때문입니다.
Red-Black 트리는 이진 탐색 트리의 일종으로, 트리를 균형 잡힌 상태로 유지하는 특별한 규칙을 가집니다. 이러한 규칙 덕분에 트리의 높이가 로그 적으로 증가하게 되어, 삽입, 삭제, 조회 작업을 수행할 때 모든 요소를 탐색할 필요 없이 로그 시간에 해당 작업을 수행할 수 있습니다. 따라서 TreeMap은 정렬된 상태를 유지해야 하는 상황에서 유용하게 사용될 수 있는 것입니다. 하지만 요소들 사이의 순서는 유지되지 않는 점 유의하세요!
또한 HashTable과 ConcurrentHashMap과 달리 동기화가 되어있지 않다는 점도 유의해야 합니다!
결론적으로 키에 따라 자동으로 정렬되는 Map이 필요하다면 TreeMap을 사용하는 것이 좋습니다. 그러나 성능이 중요한 요소이거나, 동시성 환경에서 Map을 사용한다면 HashMap이나 ConcurrentHashMap이 더 좋은 선택일 수 있습니다.
참고
지금까지 컬렉션 프레임워크의 여러 인터페이스와 인터페이스를 총 6편에 걸쳐서 다루어보았습니다 :)
긴 글 읽어주셔서 감사합니다. 틀린 내용이 있다면 지적부탁드립니다!!
https://inpa.tistory.com/entry/JCF-🧱-Collections-Framework-종류-총정리#priorityqueue_클래스
https://coding-factory.tistory.com/556
https://lealea.tistory.com/m/251
https://preamtree.tistory.com/20
https://coding-factory.tistory.com/557
'JAVA' 카테고리의 다른 글
| JVM(Java Virtual Machine) 한눈에 알아보기 (0) | 2023.05.31 |
|---|---|
| JDK, JRE, JVM이란 무엇일까? (0) | 2023.05.30 |
| Collection Framework 완전 정복 5탄 - Set인터페이스 (HashSet, LinkedHashSet) (0) | 2023.05.28 |
| Hash, HashFunction, HashCollision 완벽 정복하기! (0) | 2023.05.26 |
| Collection Framework 정복 4탄 - Heap, PriorityQueue, Deque (0) | 2023.05.26 |
