[면접을 위한 CS 전공지식 노트][자료구조] Map

0. 개요

 이번 글에서는 키를 통해 검색할 경우에 자주쓰는 Map에 대해서 공부한 내용을 정리하고자 한다. 나 같은 경우에는 JAVA 코딩을 할 때에 map을 사용한다고 하면 HashMap만을 그냥 사용해왔는데, 공부해보니 그 외에도 코딩할 때 사용하면 유용할만한 자바에서 제공해주는 유용한 Map들이 존재했다. 이 글에서는 그것들에 대해서 기록해놓고 계속해서 볼 수 있도록 하려고 한다.

1. Map이란?

  프로그래밍을 한번이라도 접해 본 사람이라면 각각의 언어마다 부르는 이름은 조금 다를 수도 있지만, Map 형식의 데이터를 이미 다뤄봤을 것이다.

 Python에서는 Dictionary라는 데이터타입으로 불리우기도 하고, API를 이용해본 사람들이라면 JSON(JavaScript Object Notation)이라는 이름을 한번 쯤은 들어봤을 것이다.

 이렇듯 각각 다른 이름으로 불리긴 하지만 모두 Map이다. 그리고 Map은 프로그래밍을 하면서 많은 곳에서 접하는 자료구조 이기 때문에 필수로 알아야 하는 자료구조이기도 하다.

 

Map은 Key와 Value의 쌍을 저장하고 관리할 수 있는 자료구조이다. Key는 Unique한 값으로 각 키는 값(Value)을 가리키게 된다. Map은 이러한 키-값 쌍을 저장하고, 키를 이용하여 검색하거나, 값을 수정하는데 사용한다.

 

맵의 주요한 특징은 아래와 같다.

1) 유일한 키: 맵 내에 동일한 키를 저장할 수 없다. 키를 통해 값을 찾는 구조이기 때문에 각 키는 유일해야한다.

2) 검색속도가 빠르다: 맵은 키를 사용하여 값을 찾는 속도가 매우 빠르다. 키를 해시함수를 통해 변환해서 인덱스로 저장하기 때문에, 평균적으로 O(1)의 시간 복잡도로 검색이 가능하다. (그러나 배열의 인덱스로 접근하는 랜덤액세스보다는 속도가 느리다.)

3) 다양한 구현체가 존재한다: Java에서는 Map이라는 인터페이스를 구현한 구현체가 여러가지가 존재한다.

 - HashTable 자료구조를 이용하여 구현한 HashMap

 - 키 값을 정렬된 순서로 저장하는 TreeMap

 - 요소를 삽입한 순서를 유지시켜주는 LinkedHashMap

등이 존재한다.

2. JAVA에서 제공하는 Map

1) HashMap

  HashMap은 해시 테이블을 기반으로 한 Map 구현체이다. HashMap은 매우 빠른 검색, 삽입, 삭제 연산을 제공하며 평균적으로 O(1)의 시간복잡도를 가지게 됨.

 

HashMap의 주요 특징

 - 해시함수 이용: HashMap은 해시함수를 이용해서 키를 해시코드로 변환하고 이를 기반으로 인덱스를 결정한다. 이를 통해 매우 빠른 검색과 삽입,삭제가 가능.

- 순서를 보장하지 않는다: HashMap은 삽입 및 키 값의 순서를 보장하지 않는다.

- 동시성 처리: HashMap은 스레드 safe하지 않음. 멀티스레드 환경에서 사용한다면 동기화를 지원하는 HashTable 사용을 고려해보아야 한다.

- null 허용: 키와 값으로 null을 허용함.

- capacity와 load factor: HashMap에서는 초기 용량과 로드 팩터를 설정할 수 있다. (default 값은 16과 0.75) 초기용량설정은 버킷의 수를 설정해주는 것이고, 로드 팩터는 버킷이 어느만큼 차야 리사이징하느냐를 결정함. 즉 디폴트로 버킷은 16개의 버킷이 제공되고, 버킷의 75퍼센트가 채워지면 해시맵을 리사이징 한다.

-  주요메서드

put(key, value): 맵에 데이터를 삽입

get(key): key로 value를 가져옴

remove(key): key로 해당데이터를 삭제

containsKey(key): 해당 키가 존재하는지 확인

 

2) TreeMap

 TreeMap은 이진 탐색 트리를 기반으로 한 Map 구현체이다. TreeMap의 Key들은 정렬된 순서로 유지되며, 검색, 범위 검색, 정렬된 순회 등의 작업을 효율적으로 수행 할 수 있다.

 

TreeMap의 주요 특징

 - 정렬된 키: TreeMap은 키들을 정렬된 순서로 관리함. 기본적으로 키의 자연순서(Comparable 인터페이스에 의한) 또는 사용자 정의 비교자(Comparator)를 이용하여 정렬한다.

올림차순: new TreeMap<>();

내림차순: new TreeMap<>(Comparator.reverseOrder());

- 검색 및 범위 검색: TreeMap은 이진 탐색 트리 구조를 사용하기 때문에 특정 키를 검색하거나, 특정 범위의 키를 검색하는 작업을 빠르게 수행 가능.

- 삽입과 삭제: 트리의 구조를 유지하기 위해 삽입과 삭제작업이 필요. 평균적으로 O(logn)의 시간복잡도가 발생.

- 동시성 처리: TreeMap은 스레드 safe하지 않음. 멀티스레드 환경에서 사용시 동기화에 대한 고민이 필요하다.

- null 불허: HashMap과 다르게 key값에는 null을 사용할 수 없다. (값에는 가능.) -> (아마 키를 기반으로 이진 탐색 트리를 만들기 때문에일듯 하다.)

-  주요메서드

put(key, value): 맵에 데이터를 삽입

get(key): key로 value를 가져옴

remove(key): key로 해당데이터를 삭제

containsKey(key): 해당 키가 존재하는지 확인

 

+ 하위타입으로 선언해서 사용할 경우

ceilingEntry(key): 제공된 키보다 크거나 같은 값 중 가장 작은 Entry를 반환(즉, 자기자신 Entry 반환)

ceilingKey(key): 제공된 키보다 크거나 같은 값 중 가장 작은 Key를 반환(즉, 자기자신 Key 반환)

floorEntry(key):제공된 키보다 작거나 같은 값 중 가장 큰 Entry를 반환(즉, 자기자신 Entry 반환)

floorKey(key): 제공된 키보다 작거나 같은 값 중 가장 큰 Key를 반환(즉, 자기자신 Key 반환)

 

higherEntry(): 제공된 키보다 큰 값 중 가장 작은 Entry를 반환(즉, 자기자신 다음에 있는 Entry 반환)

higherKey(); 제공된 키보다 큰 값 중 가장 작은 Key를 반환(즉, 자기자신 다음에 있는 Key 반환)

lowerEntry(): 제공된 키보다 작은 값 중 가장 큰 Entry를 반환(즉, 자기자신 이전에 있는 Entry 반환)

lowerKey(): 제공된 키보다 작은 값 중 가장 큰 Key를 반환(즉, 자기자신 이전에 있는 Key 반환)

 

3) LinkedHashMap

 LinkedHashMap은 해시맵과 연결리스트의 특성을 결합한 자료구조를 기반으로 한 Map 구현체이다. LinkedHashMap은 삽입순서를 유지하는 동시에 검색 및 반복 순회 작업에서 높은 성능을 제공 함.

 

LinkedHashMap의 주요 특징

 - 삽입 순서 유지: LinkedHashMap은 요소를 추가한 순서를 유지한다.

 - 해시맵 기반: 내부적으로는 해시맵을 사용하여 데이터를 저장하고 검색한다. 이를 통해 빠른 검색 및 삽입이 가능.

 - 연결 리스트: 각 해시버킷마다 연결리스트를 유지하여 해시 충돌이 발생했을 때 충돌된 요소들을 연결 하여 저장.

 - 동시성 처리: LinkedHashMap은 스레드에 safe하지 않음. 멀티스레드 사용시 동기화 고려해야함.

 - null 허용: HashMap과 마찬가지로 key와 value 둘다 null 허용

 - capacity와 load factor: HashMap과 마찬가지로 초기 capacity와 로드팩터를 설정해 줄 수 있다.

-  주요메서드

put(key, value): 맵에 데이터를 삽입

get(key): key로 value를 가져옴

remove(key): key로 해당데이터를 삭제

containsKey(key): 해당 키가 존재하는지 확인

3. 정리

1. Map은 Key와 Value의 쌍을 저장하고 관리할 수 있는 자료구조이며, 키를 이용하여 검색하거나, 값을 수정하는데 사용. (해시함수를 이용)

2. Java에서 제공해주는 여러가지 Map 구현체들은 각각의 특성이 있음.

 HashMap: 해시테이블을 기반으로 만들어진 구현체, 해시함수를 이용하여 인덱스 저장한다. 순서보장x

 TreeMap: 이진탐색트리를 기반으로 만들어진 구현체이며, 키를 정렬하여 관리한다.

 LinkedHashMap: 해시맵과 연결리스트의 특성을 결합한 자료구조를 기반으로 한 Map 구현체. 삽입 순서를 보장

 

참조

면접을 위한 CS 전공지식 노트