자바의 강력한 도구인 Map에 대해 배우는 시간입니다. 구조와 원리에 대해서는 “Java로 배우는 자료구조” 코스에서 좀 더 깊게 이해를 하실 수 있습니다. 이 강의에서는 어떤 도구들이 있고 어떤 특징이 있는지, 어떻게 사용하는지에 대해서만 알아봅니다.

ㅤ

목차

1. Map<Key, Value>

2. HashMap<Key, Value>

3. TreeMap<Key, Value>

4. LinkedHashMap<Key, Value>

ㅤ

1. Map<Key, Value>

Java에는 Map이라는 도구가 있습니다. Map은 다른 언어에서는 Associated Array, Dictionary, Symbol Table 등으로 부르기도 합니다. 이러한 Map은 Java로 애플리케이션을 만들 때 정말 많이 사용하는 도구중 하나입니다.

기본적으로 Map은 key-value 구조로 구성된 데이터를 저장할 수 있습니다. 이러한 구조를 가진 데이터를 저장하는데 최적화되어있으며 key를 가지고 value를 찾을 수 있습니다.

key를 이용한 데이터 검색에 최적화되어있으나, 주의할 점이 있습니다. 동일한 key로 다른 데이터를 저장 시 기존에 저장된 데이터는 덮어씌워집니다. 중복된 key는 존재할 수 없습니다.

Java의 Map은 인터페이스로 선언되어 있고, Map interface의 구현체로는 HashMap, TreeMap, LinkedHashMap이 존재합니다.

사용 방식에는 큰 차이 없으나, 자료구조에 따라 구현 방식이 다릅니다.

• Hash Table 방식을 사용한 HashMap

• Tree 방식을 사용한 TreeMap

• Linked Hash Table 방식을 사용한 LinkeHashMap

ㅤ

2. HashMap<Key, Value>

HashMap은 Hash Table을 이용하여 만들어졌으므로 간략히 Hash Table에 대해서 알아봅시다. Hash Table의 컨셉은 다음과 같습니다.

Hash Table은 key와 value를 저장하며, key를 이용하여 빠르게 데이터를 찾기 위한 자료구조를 가지고 있습니다.

• 특정 key는 해시 함수를 통하여 bucket에 접근할 수 있는 index로 변환됩니다.

• index를 이용하여 bucket에 접근합니다.

• bucket에 맞는 index에 key와 value를 저장합니다.

ArrayList와 LinkedList는 index를 통해 데이터를 접근한다고 본다면 Hash Table은 key를 index로 변경하여 데이터를 접근한다고 보면 됩니다.

key가 해시 함수를 통해서 key에 대한 index가 만들어지고 index를 통하여 bucket에 접근하기 때문에 저장되는 데이터가 많을수록, bucket의 크기가 적을 수록 index 충돌이 발생할 가능성이 높습니다.

그래서 이러한 충돌이 났을 때 어떻게 저장하냐에 따라 여러 방식이 존재합니다. 이 부분은 이 강의에서 깊게 설명하지는 않습니다. Hash Table은 이러한 자료 구조를 가지고 있다고 일단 가볍게 생각하시는 것이 좋습니다.

ㅤ

특징

• bucket은 배열 기반 구조이다.

• 충분히 큰 데이터를 가지고 있을 경우, 충돌시 entry의 저장방식을 LinkedList -> TreeNode로 변경한다.

ㅤ

장점

• key가 index로 변환되어 bucket에 대응하는 곳에 저장하기 때문에 값을 검색하는 것은 선형적으로 접근하는ArrayList나 LinkedList 대비 더 빠르다.

• key를 null 값으로 할 일은 빈번하지 않지만 null key가 가능하다.

ㅤ

단점

• bucket의 크기가 가득 차서 크기 조정이 필요할 경우 더 큰 해시맵으로 변경되기 때문에 지연시간이 걸릴 수 있다.

• 데이터를 저장하는데 필요한 메모리보다 훨씬 더 많은 메모리를 필요로 한다.

• HashMap에 저장된 key를 추출했을 때, 정렬되어 있지 않다.

ㅤ

사용용도

• index가 아닌 key를 이용하여 데이터 저장과 접근이 필요할 경우 사용한다.

• 데이터의 크기가 어느 정도 예상되는 경우 사용한다.

• 삽입 삭제가 빈번할 경우 사용한다.

ㅤ

주의할점

• 동일한 key로 저장할 경우 기존에 저장된 값이 소멸된다. (값의 중복은 상관없다)

• key는 대소문자를 구분한다.

• 다양한 참조 자료형을 key로 사용할 수 있으나 index 생성 시 Object.hashCode() 코드에 의존하므로 논리적으로 동일한 객체라고 하더라도 물리적으로 인스턴스가 다를 경우 Object를 key로 사용하면 원치 않는 결과가 발생할 수 있다. (아래 예시 있음)

ㅤ

HashMap의 생성

import java.util.HashMap;

HashMap<Key, Value> map = new HashMap<>();

ㅤ

HashMap의 데이터 삽입

import java.util.HashMap;

// String key, String value
HashMap<String, String> map = new HashMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

HashMap에서 데이터를 저장하는 기본적인 방법은 put(key, value) 메서드를 통해 저장합니다.

ㅤ

HashMap의 데이터 접근

import java.util.HashMap;

// String key, String value
HashMap<String, String> map = new HashMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

String value1 = map.get("codelatte");
// "코드라떼"

String value2 = map.get("cafe");
// "카페"

String value3 = map.getOrDefault("coffee", "커피");
// hashmap에 "coffee" 키가 존재하지 않을 경우 "커피"를 반환한다.

HashMap에서 데이터를 접근하는 방법은 get(key) 메서드를 통해 접근합니다.

추가로 getOrDefault(key, defaultValue) 메서드는 HashMap에 해당 key값이 존재하지 않을 시 defaultValue를 반환합니다.

ㅤ

HashMap의 key 삭제

import java.util.HashMap;

// String key, String value
HashMap<String, String> map = new HashMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

// key 값을 이용하여 삭제
map.remove(“kantata”);

Map은 기본적으로 key 값을 이용하여 값에 접근하므로, HashMap도 key 값을 이용하여 저장된 값을 삭제할 수 있습니다.

ㅤ

HashMap의 key 출력

import java.util.HashMap;

// String key, String value
HashMap<String, String> map = new HashMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

// key 값을 출력
for (String key : map.keySet()) {
    System.out.println(key);
}

HashMap은 key 출력시 정렬되어 있지 않습니다.

ㅤ

HashMap의 value 출력

import java.util.HashMap;

// String key, String value
HashMap<String, String> map = new HashMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

// value 값을 출력
for (String value : map.values()) {
    System.out.println(value);
}

HashMap은 value 출력시 정렬되어 있지 않습니다.

ㅤ

HashMap에서 동일한 key를 사용하여 저장한 경우

import java.util.HashMap;

// String key, String value
HashMap<String, String> map = new HashMap<>();

// 데이터 삽입
map.put("coffee", "아메리카노");
map.put("coffee", "카페라떼");

String value1 = map.get("coffee");
// "카페라떼"

동일한 key로 값을 저장하는 경우 기존에 저장된 값이 덮어쓰기가 됩니다.

ㅤ

HashMap의 key로 Object를 사용할 시 주의해야 할 점

class Address {
    private String city;
    private String street;

    public Address(String city, String street) {
        this.city = city;
        this.street = street;
    }
}

import java.util.HashMap;

// String key, String value
HashMap<Address, String> map = new HashMap<>();

// 데이터 삽입
map.put(new Address("서울시", "강남서로 20"), "서울시 강남서로 20");
map.put(new Address("서울시", "강남서로 20"), "서울시 강남서로 20");

System.out.println(map);
// Address@610455d6=서울시 강남서로 20, Address@511d50c0=서울시 강남서로 20

의미상으로는 동일한 객체로 보일 수 있어도, 서로 다른 인스턴스이기 때문에 인스턴스의 hashcode가 다릅니다. 그러므로 두 객체는 HashMap에 중복 없이 저장됩니다.

"모든 클래스는 Object 클래스를 상속받는다" 강의에서 같은 의미의 객체로 만들고 싶으면 Object.equals() 메서드와 Object.hashCode() 메서드를 재정의 해야 한다고 했었습니다.

HashMap은 내부적으로 해당 메서드들을 사용하기 때문에 같은 key로 만들고 싶다면 Object.equals() 메서드와 Object.hashCode() 메서드를 재정의 해야 합니다.

ㅤ

Map 인터페이스를 구현하는 HashMap

import java.util.HashMap;
import java.util.Map;

// String key, String value
Map<String, String> map = new HashMap<>();

다형성의 특징으로 HashMap의 참조 값을 Map 참조 자료형에 저장할 수 있습니다. 다만 Map의 공통적인 인터페이스만 선언되어 있기 때문에 HashMap의 모든 메서드를 사용할 수는 없습니다.

ㅤ

3. TreeMap<Key, Value>

TreeMap은 Red-Black Tree를 이용하여 만들어졌으므로 간략히 Tree 구조에 대해서 알아봅시다. 논리적인 Tree 구조는 다음과 같으며, 나뭇가지를 거꾸로 회전시킨 모양입니다.

Tree는 Node들의 연결로 이루어져 있으며 Node안에 데이터가 저장되는 LinkedList와 유사하다고 볼 수 있습니다.

• 루트라는 특별한 Node가 있습니다.

• 부모 Node와 자식 Node로 구성되어 있습니다.

• 자식 노드가 없는 경우는 Leaf Node라고 부릅니다.

이러한 Tree의 특징은

• 가계 족보와 비슷합니다.

• 기업의 직위에 대한 계층구조와 비슷합니다.

*Tree, Red-Black Tree 자료구조는 이 강의에서 깊게 설명하지는 않습니다.

Tree 자료구조에는 다양한 Tree가 존재합니다. 그중에서 TreeMap은 Red-Black Tree라는 자료구조를 사용하여 만들어졌습니다.

Node에는 key와 value가 같이 저장되며, key 값을 기준으로 좌측 우측으로 구분하여 저장됩니다. 5라는 key 가진 Node를 기준으로 봤을 때 5보다 작은 키(2)는 좌측 자식 Node, 큰 키(6)는 우측 자식 Node로 저장되어 연결됩니다.

그리고 Red-Black Tree의 특성상 새로운 데이터가 저장되거나 삭제될 때마다 Node의 위치를 재배치하는 연산이 발생합니다.

ㅤ

특징

• Tree구조 기반이다.

ㅤ

장점

• key가 Red-Black Tree에 규정에 맞춰 Node의 위치를 재배치하며 저장하기 때문에 값을 검색하는 것은 선형적으로 접근하는 ArrayList나 LinkedList 대비 더 빠르다.

• key 값을 기준으로 오름차순으로 정렬된 key를 반환받을 수 있다.

• HashMap 대비 필요한 메모리 양만 사용하므로 상대적으로 메모리를 절약할 수 있다.

ㅤ

단점

• 삽입이나 삭제 시 Node를 재배치하는 연산이 발생할 수 있다.

• (삽입 삭제가 빈번할 경우 HashMap보단 느리다)

• HashMap보다 검색 속도가 상대적으로 느리다.

• null key가 불가능하다.

ㅤ

사용용도

• 저장되는 데이터의 개수가 몇 개인지 예상되지 않는 경우 사용한다.

• 삽입과 삭제가 빈번하지 않을 때 사용한다.

• 정렬된 key가 필요할 때 사용한다.

ㅤ

주의할점 (HashMap과 동일)

• 동일한 key로 저장할 경우 기존에 저장된 값이 소멸된다. (값의 중복은 상관없다)

• key는 대소문자를 구분한다.

• 다양한 참조 자료형을 key로 사용할 수 있으나 index 생성 시 Object.hashCode() 코드에 의존하므로 논리적으로 동일한 객체라고 하더라도 물리적으로 인스턴스가 다를 경우 Object를 key로 사용하면 원치 않는 결과가 발생할 수 있다. (HashMap과 동일)

ㅤ

TreeMap의 생성

import java.util.TreeMap;

TreeMap<Key, Value> map = new TreeMap<>();

ㅤ

TreeMap의 데이터 삽입

import java.util.TreeMap;

// String key, String value
TreeMap<String, String> map = new TreeMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

TreeMap에서 데이터를 저장하는 기본적인 방법은 put(key, value) 메서드를 통해 저장합니다.

ㅤ

TreeMap의 데이터 접근

import java.util.TreeMap;

// String key, String value
TreeMap<String, String> map = new TreeMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

String value1 = map.get("codelatte");
// "코드라떼"

String value2 = map.get("cafe");
// "카페"

String value3 = map.getOrDefault("coffee", "커피");
// treemap에 "coffee" 키가 존재하지 않을 경우 "커피"를 반환한다.

TreeMap에서 데이터를 접근하는 방법은 get(key) 메서드를 통해 접근합니다.

추가로 getOrDefault(key, defaultValue) 메서드는 TreeMap에 해당 key값이 존재하지 않을 시 defaultValue를 반환합니다.

ㅤ

TreeMap의 key 삭제

import java.util.TreeMap;

// String key, String value
TreeMap<String, String> map = new TreeMap<>();

// 데이터 삽입
map.put("codelatte", "코드라떼");
map.put("kantata", "김철수");
map.put("cafe", "카페");

// key 값을 이용하여 삭제
map.remove(“kantata”);

Map은 기본적으로 key 값을 이용하여 값에 접근하므로, TreeMap도 key 값을 이용하여 저장된 값을 삭제할 수 있습니다.

ㅤ

TreeMap의 key 출력

import java.util.TreeMap;

// String key, String value
TreeMap<String, String> map = new TreeMap<>();

// 데이터 삽입
map.put("2", "2");
map.put("3", "3");
map.put("1", "1");
map.put("4", "4");

// key 값을 출력
for (String key : map.keySet()) {
    System.out.println(key);
}

// "1", "2", "3", "4"

TreeMap은 HashMap과 다르게 key 출력시 오름차순으로 정렬된 상태로 출력됩니다.

ㅤ

TreeMap의 value 출력

import java.util.TreeMap;

// String key, String value
TreeMap<String, String> map = new TreeMap<>();

// 데이터 삽입
map.put("2", "2");
map.put("3", "3");
map.put("1", "1");
map.put("4", "4");

// value 값을 출력
for (String value : map.values()) {
    System.out.println(value);
}
// "1", "2", "3", "4"

TreeMap은 HashMap과 다르게 value 출력시 key 값을 기준으로 오름차순으로 정렬되어 저장된 값을 출력됩니다.

ㅤ

TreeMap에서 동일한 key를 사용하여 저장한 경우

TreeMap도 Map이기에 HashMap과 공통적인 특성을 가지고 있습니다.

ㅤ

TreeMap의 key로 Object를 사용할 시 주의해야 할 점

TreeMap도 Map이기에 HashMap과 공통적인 특성을 가지고 있습니다.

ㅤ

4. Map 인터페이스를 구현하는 TreeMap

import java.util.TreeMap;
import java.util.Map;

// String key, String value
Map<String, String> map = new TreeMap<>();

다형성의 특징으로 TreeMap의 참조값을 Map 참조 자료형에 저장할 수 있습니다.

다만 Map의 공통적인 인터페이스만 선언되어있기 때문에 TreeMap의 모든 메서드를 사용할 수는 없습니다.

ㅤ

LinkedHashMap<Key, Value>

LinkedHashMap은 HashMap을 상속하여 만들어진 클래스입니다. 그러므로 HashMap의 특징을 가지고 있습니다. 다만 HashMap과 다른 점은 Node 객체를 Entry 객체로 감싸서 저장된 키의 순서를 보존한다는 점입니다.

HashMap과 거의 유사하므로 차이점만 설명드리겠습니다.

ㅤ

특징

• HashMap을 상속받고 원리는 같다.

ㅤ

장점

• HashMap의 장점을 그대로 계승한다.

• HashMap은 데이터의 저장 순서와 상관없이 key 또는 value를 출력하나 LinkedHashMap은 key의 저장된 순서를 보존한다.

ㅤ

단점

• HashMap의 단점을 그대로 계승한다.

ㅤ

사용용도

• key또는 값의 저장된 순서가 중요할 때 사용한다.

ㅤ

LinkedHashMap의 key 출력

import java.util.LinkedHashMap;

// String key, String value
LinkedHashMap<String, String> map = new LinkedHashMap<>();

// 데이터 삽입
map.put("2", "2");
map.put("3", "3");
map.put("1", "1");
map.put("4", "4");

// key 값을 출력
for (String key : map.keySet()) {
    System.out.println(key);
}

// "2", "3", "1", "4"

LinkedHashMap은 HashMap과 다르게 key를 저장한 순서로 출력됩니다.

ㅤ

LinkedHashMap의 value 출력

import java.util.LinkedHashMap;

// String key, String value
LinkedHashMap<String, String> map = new LinkedHashMap<>();

// 데이터 삽입
map.put("2", "2");
map.put("3", "3");
map.put("1", "1");
map.put("4", "4");

// value 값을 출력
for (String value : map.values()) {
    System.out.println(value);
}
// "2", "3", "1", "4"

LinkedHashMap은 HashMap과 다르게 value 출력시 key 값을 기준으로 출력하므로, 값도 저장된 순서대로 출력합니다.