
안녕하세요. NOX입니다.
지난 포스팅에 이어 오늘은 Map Collection
에 대해 알아보겠습니다.
지난 포스팅 링크 두고 시작하겠습니다.
[Java]Collection(4) - Set
안녕하세요. NOX입니다. Queue 컬렉션에 이어서 Set 컬렉션에 대해 알아보겠습니다. [Java]Collection(3) - Queue, Deque안녕하세요. List 컬렉션에 이어 Queue 컬렉션에 대해 알아보겠습니다. [Java] Collection(2)
lumos-maxima-nox.tistory.com
Map Collection
Map Collection
은 List
, Set
, Queue
컬렉션들과 달리 Collections
의 상속을 직접적으로 받지 않습니다.
Key
와 Value
로 구성된 Entry
객체를 저장하는 것이 Map Collection
의 특징입니다.
특징은 다음과 같습니다.
Key
와Value
모두 객체Key
는 중복저장 불가능, 기존 저장되어 있는Key
와 동일한Key
를 저장하면, 새로운 값으로 대치Value
는 중복저장 가능- 저장 순서가 유지되지 않음
null
저장 가능
Map
인터페이스를 구현한 클래스들은 다음과 같습니다.
- HashMap
- Hashtable
- LinkedHashMap
- TreeMap
Map 컬렉션의 주요 메서드
주로 키와 값을 관리하는 메서드들이 많습니다.
기능 | 메소드 | 설명 |
객체추가 | V put(K key, V value) | 주어진 키와 값을 추가. 저장이 되면 값을 리턴 |
객체 검색 | boolean containsKey(Object key) | 주어진 키가 있는지 여부 |
boolean containsValue(Object value) | 주어진 값이 있는지 여부 | |
Set<Map.Entry<K,V>> entrySet() | 키와 값의 쌍으로 구성된 모든 Map.Entry 객체를 Set에 담아서 리턴 | |
V get(Object key) | 주어진 키의 값을 리턴 | |
boolean isEmpty() | 컬렉션이 비어있는지 여부 | |
set<K> keySet() | 모든 키를 Set 객체에 담아서 리턴 | |
int size() | 저장된 키의 총 수를 리턴 | |
Collection<V> values() | 저장된 모든 값 Collection에 담아서 리턴 | |
객체 삭제 | void clear() | 모든 Map.Entry(키와 값)을 삭제 |
V remove(Object key) | 주어진 키와 일치하는 Map.Entry 삭제. 삭제 되면 값을 리턴 |
HashMap
Key-Value
쌍으로 저장되며, 순서를 보장하지 않고 Key
,Value
값에 null
을 허용합니다.
HashMap
은 HashSet
의 데이터 중복방지의 기반이 됩니다.
Hashtable
구조를 이용하여 해싱이라는 과정을 통해 저장 위치를 결정합니다.

시간 복잡도
- 검색/삽입/삭제 : O(1)
- 해시 충돌 시 삽입 최악 시간 복잡도 : O(n)
💡 Big O 시간복잡도
-> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
Hashtable
Hahstable
은 HashMap
과 동일한 내부 구조를 가지고 있습니다.
Hashtable
은 동기화(Synchronized)된 메서드로 구성되어 있는 멀티스레드 환경에서 안전한 클래스입니다.
이 역시 Concurrent Collection이 등장하면서 사용을 지양하고 있습니다.

위 그림은 Hashtable의 구조입니다.
특정 Key
는 해시함수를 통하여 버킷에 접근할 수 있는 index
로 변환됩니다.
Index
를 통하여 버킷에 접근하게되고, 버킷에 맞는 index
에 key
와 value
를 저장합니다.
💡Bucket은 배열 기반 구조라 index
가 있습니다!
Hashtable 예제
import java.util.*;
public class HashtableExample {
public static void main(String[] args) {
//Hashtable 컬렉션 생성
Map<String, Integer> map = new Hashtable<>(); // 총 엔트리 수 : 2000
//Map<String, Integer> map = new HashMap<>(); //총 엔트리 수 : 1954
//작업 스레드 객체 생성
Thread threadA = new Thread(){
@Override
public void run(){
//엔트리 1000개 추가
for(int i=1; i <= 1000; i++){
map.put(String.valueOf(i), i);
}
}
};
//작업 스레드 객체 생성
Thread threadB = new Thread(){
@Override
public void run(){
//엔트리 1000개 추가
for(int i=1001; i <= 2000; i++){
map.put(String.valueOf(i), i);
}
}
};
//작업 스레드 실행
threadA.start();
threadB.start();
// 작업 스레드들이 모두 종료 될 때까지 메인 스레드를 기다리게 함
try{
threadA.join();
threadB.join();
} catch (Exception e) {
}
// 저장된 총 엔트리 수 얻기
int size = map.size();
System.out.println("총 엔트리 수: "+ size);
System.out.println();
}
}
HashMap
과 Hashtable
에 각각 스레드 객체를 만들고, 값을 동시에 추가했을 때 HashMap
에서는 메서드 경합이 일어나 총 엔트리 수가 달라지는 것을 확인할 수 있습니다.
시간 복잡도
- 검색/삽입/삭제 : O(1)
- 해시 충돌 시 삽입 최악 시간 복잡도 : O(n)
💡 Big O 시간복잡도
-> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
LinkedHashMap
LinkedHashMap
은 삽입 순서를 유지하는 Hashtable기반 Map
입니다. 해시테이블과 이중 연결리스트의 특징이 더해져 있습니다.
Node
객체를 Entry
객체로 감싸 저장된 키의 순서를 보존합니다.
다른 Map
인터페이스들과 마찬가지로 Key-Value
쌍으로 저장되며, 순서를 보장하지 않고 Key
,Value
값에 null
을 허용합니다.
HashMap
과 거의 유사하므로 바로 시간복잡도에 대해 알아보겠습니다.
시간 복잡도
- 검색/삽입/삭제 : O(1) (순서 유지로 조금 느릴 수 있음)
💡 Big O 시간복잡도
-> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
TreeMap
TreeMap
은 TreeSet
과 같이 이진 트리 (레드 블랙 트리) 기반 Map
컬렉션입니다.
TreeSet
과 다른 점은 Entry(K,V)
객체를 저장합니다. 키를 기준으로 자동으로 오름차순 정렬하여 객체를 저장합니다.
💡 부모 노드와 비교하여 낮은 것은 왼쪽, 높은 것은 오른쪽에 Entry
객체로 저장합니다.
null
값인 Key
저장이 불가능 합니다.
값을 저장하거나 삭제할 때 Node의 위치를 재배치하기 때문에 값을 검색하는 것이 선형리스트 보다 더 바릅니다.
하지만 HashMap
보다는 속도가 상대적으로 느립니다.
TreeMap의 주요 메서드
리턴 타입 | 메서드 | 설명 |
Map.Entry<K,V> | firstEntry() | 제일 낮은 Map.Entry를 리턴 |
Map.Entry<K,V> | lastEntry() | 제일 높은 Map.Entry를 리턴 |
Map.Entry<K,V> | lowerEntry(K key) | 주어진 키보다 바로 아래 Map.Entry를 리턴 |
Map.Entry<K,V> | higherEntry(K key) | 주어진 키보다 바로 위 Map.Entry를 리턴 |
Map.Entry<K,V> | floorEntry(K key) | 주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 바로 아래 Map.Entry를 리턴 |
Map.Entry<K,V> | ceilingEntry(K key) | 주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 바로 위 Map.Entry를 리턴 |
Map.Entry<K,V> | pollFirstEntry() | 제일 낮은 Map.Entry를 꺼내오고 컬렉션에서 제거함 |
Map.Entry<K,V> | pollLastEntry() | 제일 높은 Map.Entry를 꺼내오고 컬렉션에서 제거함 |
NavigableMap<K,V> | descendingKeySet() | 내림차순으로 정렬된 키의 NavigableSet을 리턴 |
NavigableMap<K,V> | descendingMap() | 내림차순으로 정렬된 Map.Entry의 NavigableMap을 리턴 |
NavigableMap<K,V> | headMap( K toKey, boolean inclusive ) |
주어진 키보다 낮은 Map.Entry들을 NavigableMap으로 리턴. 주어진 키의 Map.Entry 포함 여부는 두 번째 매개값에 따라 달라짐 |
NavigableMap<K,V> | tailMap( K fromKey, boolean Inclusive ) |
주어진 객체보다 높은 Map.Entry들을 NavigableMap으로 리턴. 주어진 객체 포함 여부는 두번 째 매개값에 따라 달라짐 |
NavigableMap<K,V> | subMap( K fromKey, boolean formInclusive, K toKey, boolean toInclusive ) |
시작과 끝으로 주어진 키 사이 Map.Entry들을 NavigableMap 컬렉션으로 반환. 시작과 끝 키의 Map.Entry 포함 여부는 두번째, 네 번째 매개값에 다라 달라짐 |
시간 복잡도
- 검색/삽입/삭제 : O(logN)
💡 Big O 시간복잡도
-> 알고리즘의 성능을 나타내는 표기법
성능이 좋은 순서대로 O(1) - O(log N) - O(N) - O(NlogN) - O(n²) - O(n³) - O(2ⁿ)입니다
이렇게 Map Collection에 대해 알아보았습니다.
도움이 되셨다면 공감 한 번 부탁드리며 잘못된 정보가 있다면 언제든 댓글 달아주세요!🪄
⬇️ 참고 URL
https://www.codelatte.io/courses/java_programming_basic/KW7N6AHSIJ00UUS4
책 '이것이 자바다'
'프로그래밍언어 > Java' 카테고리의 다른 글
[Java]Collection(4) - Set (0) | 2024.11.06 |
---|---|
[Java]Collection(3) - Queue, Deque (0) | 2024.11.05 |
[Java] Collection(2) - List (2) | 2024.11.04 |
[Java] Collection(1) - 컬렉션 프레임워크 (0) | 2024.11.01 |