Map

개요

자바의 Map 인터페이스는 key-value 쌍을 저장하는 자료 구조이다. 즉, 인터페이스이기 때문에 직접 인스턴스를 생성할 수는 없고, 구현한 HashMap, TreeMap, LinkedHashMap 등을 통해 사용할 수 있다.

 

Map vs Set

사실 Map의 key는 Set과 같은 구조이다. Map은 모든 것이 key를 중심으로 동작하며 중복을 허용하지 않고 순서를 보장하지 않는다. 여기에 value는 단순히 key 옆에 붙어 Map이 되는 것이다.

즉, Map과 Set은 거의 같고, value를 가지고 있는가 없는가의 차이만 있는 것이다. 이런 이유로 Set, Map의 구현체는 거의 같으며, 실제로 자바 HashSet의 구현은 대부분 HashMap의 구현을 가져다 사용하여, Map에서 value만 비워두면 Set으로 사용할 수 있다.

Set	Map
HashSet	HashMap
LinkedHashSet	LinkedHashMap
TreeSet	TreeMap

 

1. HashMap

입력한 순서를 보장하지 않는다.

• 구조: key 값은 해시 함수를 통해 해시 코드로 변환되고, 이 해시 코드는 데이터를 저장하고 검색하는 데 사용된다.
• 특징: 삽입, 삭제, 검색 작업은 해시 자료 구조를 사용하므로 O(1)의 시간 복잡도를 가진다.
• 순서: 순서를 보장하지 않는다.

2. LinkedHashMap

키를 기준으로 입력한 순서를 보장한다.

• 구조: HashMap과 유사하지만, 연결 리스트를 사용해서 삽입 순서 또는 최근 접근 순서에 따라 요소를 유지한다.
• 특징: 입력 순서에 따라 순회가 가능하다. 즉, 입력 순서를 링크로 유지해야 한다.
• 성능: HashMap과 유사하게 대부분 O(1)의 시간 복잡도를 가진다.
• 순서: 입력 순서를 보장한다.

3. TreeMap

키 자체의 데이터 값을 기준으로 정렬한다.

• 구조: TreeMap은 Red-Black Tree를 기반으로 구현된 Map이다.
• 특징: 모든 키는 자연 순서 또는 생성자에 제공된 Comparator에 의해 정렬된다.
• 성능: get, put, remove와 같은 주요 작업들은 O(log n)의 시간 복잡도를 가진다.
• 순서: 키는 정렬된 순서로 저장된다.

 

자바의 HashMap 작동 원리

자바의 HashMap은 HashSet과 작동 원리가 같다.

• Key를 사용해서 해시 코드를 생성한다.

하지만 다음과 같은 차이가 있다.

• Key뿐만 아니라 Value를 추가로 저장해야 하기 때문에 Entry를 사용해서 Key, Value를 하나로 묶어서 저장한다.

이렇게 해시를 사용해서 키와 값을 저장하는 자료 구졸를 일반적으로 해시 테이블이라고 한다. 그리고 HashSet은 해시 테이블의 주요 원리를 사용하지만, Key-Value 저장 방식 대신 Key만 저장하는 특수한 형태의 해시 테이블이라고 이해하면 된다.

Map의 Key로 사용되는 객체는 반드시 hashCode(), equals()를 구현해야 한다.