[Java]Collection(5) -Map

2024. 11. 7. 11:20·프로그래밍언어/Java
목차
  1. Map Collection
  2. HashMap
  3. Hashtable
  4. LinkedHashMap
  5. TreeMap

 

안녕하세요. 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
  1. Map Collection
  2. HashMap
  3. Hashtable
  4. LinkedHashMap
  5. TreeMap
'프로그래밍언어/Java' 카테고리의 다른 글
  • [Java]Collection(4) - Set
  • [Java]Collection(3) - Queue, Deque
  • [Java] Collection(2) - List
  • [Java] Collection(1) - 컬렉션 프레임워크
N0X
N0X
해리포터를 좋아하는 개발자의 기록
  • N0X
    루모스코드🪄Lumos Code
    N0X
  • 전체
    오늘
    어제
    • 전체 글 (10)
      • 프로그래밍언어 (5)
        • Java (5)
      • SQL (0)
        • Oracle (0)
      • 자료구조 (0)
      • Life Hack (5)
        • 각종 후기 (2)
        • 툴팁쓰 (3)
  • 인기 글

  • 최근 글

  • 태그

    oracle 18c
    자바 컬렉션
    티스토리챌린지
    컬렉션
    오블완
    Collection
    자바
    java
    Java Collection
    sts run on server
  • hELLO· Designed By정상우.v4.10.1
N0X
[Java]Collection(5) -Map

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.