[Java]Collection(5) -Map

 

안녕하세요. NOX입니다.

지난 포스팅에 이어 오늘은 `Map Collection`에 대해 알아보겠습니다.

지난 포스팅 링크 두고 시작하겠습니다.

[Java]Collection(4) - Set

 

 

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

책 '이것이 자바다'