Java Map의 내부 구현은 어떻게 이루어져 있을지 추측해보실 수 있을까요?

Java 에는 Map 이라는 인터페이스 도구가 있다.

대표적으로 Map, HashMap, TreeMap, LinkedHashMap이 있다.

 

각 Map 인터페이스들의 구조에 대해 정리해보자.

 

---

 

Map<Key, Value>

기본적으로 Map은 key-value 구조로 구성되어 데이터를 저장할 수 있다.

key를 가지고 저장된 value를 찾을 수 있다.

 

key를 이용하여 데이터 검색에 최적화되어있으나, 동일한 key 에 다른 데이터 value가 저장되어 있을 경우 기존에 저장된 데이터는 덮어씌워져 사라진다.

따라서, 중복된 key는 존재할 수 없다.

 

 

HashMap<Key, Value>

HashMap은 Hash Table 을 이용하여 만들어졌다.

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

• 특정 key는 해시 함수를 통하여 bucket에 접근할 수 있는 index로 변환한다.
• index를 통하여 bucket에 접근한다.
• bucket에 맞는 index에 key와 value를 저장한다.

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

 

[HashMap 사용 예시]

import java.util.HashMap;

// 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" 키가 존재하지 않을 경우 "커피"를 반환한다.

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


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

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

 

 

TreeMap<Key, Value>

TreeMap은 Node들의 연결로 이루어져 있으며, LinkedList 와 유사하다고 볼 수 있다.

• 루트라는 최상위 Node가 존재한다.
• 부모 Node 와 자식 Node 로 구성되어 있다.
• 자식 노드가 없는 경우는 Leaf Node 라고 부른다.

Node 에는 key 와 value 가 같이 저장되며, key 값을 기준으로 좌측 우측으로 구분하여 저장된다.

위의 사진에서 5의 key 값을 가진 Node를 기준으로 봤을 때 5보다 작은 키(2)는 좌측 자식 Node, 큰 키(6)는 우측 자식 Node로 저장되어 연결한다.

 

 

[TreeMap 사용 예시]

import java.util.TreeMap;

// 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" 키가 존재하지 않을 경우 "커피"를 반환한다.

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


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


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

 

 

LinkedHashMap<Key, Value>

LinkedHashMap은 HashMap을 상속하여 만들어진 클래스다.

따라서 HashMap의 특징을 가지고 있다.

다른 점이라고 한다면, Node 객체를 Entry 객체로 감싸서 저장된 키의 순서를 보존하고 있다는 점이다.