Portfolio

Map 이란?0️⃣ 맵의 계층 구조 1️⃣ HashMap - O(1) 해싱이란? 해시충돌이란?HashMap은 어떤걸 사용할까?해시 버킷의 확장 2️⃣ TreeMap - O(log N)RedBlack Tree?3️⃣ LinkedHashMap - O(1)🧑🏻‍⚖️ 결론 📚 REF

🔥

각 Map 시간복잡도, 공간복잡도 찾아서 추가하기 !

Map 이란?

Map은 데이터를 모아서 관리할 수 있는 컬렉션입니다.

컬렉션은 그 타입에 따라 내부 데이터를 저장하는 구조와 처리 방법이 다릅니다. 내부에서 처리하는 방법에 따라 데이터의 탐색이 빠른 경우가 있고, 추가/제거가 빠른 경우가 있습니다.

사용하는 컬렉션의 특성을 잘 알고 사용해야 불필요한 성능 저하를 피할 수 있습니다.

0️⃣ 맵의 계층 구조

1️⃣ HashMap - O(1)

가장 흔하게 사용되는 Map으로 내부적으로는 Entry 배열으 만들어서 관리한다.

map.put() 메서드를 이용해서 앤트리를 추가하면 key 값으로 넘겨준 객체의 해시코드를 계산하여 앤트리 배열의 접근 인덱스로 사용합니다.

key1 이라는 문자열의 해시코드를 계산했을 때 10이라는 값이 나오면 배열의 10번째 항목으로 value를 저장하는 방법입니다.

HashMap의 해시값 계산은 자바 버전에 따라 다르지만 기본적으로 객체의 hashCode() 메서드의 리턴값을 기반으로 동작하게 됩니다. 또한 해시충돌(Hash Coliision)의 경우를 대비해 equals() 메서드까지 사용해서 key값이 정말 같은 경우에만 Value를 리턴해줍니다.

따라서 키 값으로 사용할 클래스의 특성에 따라 필요한 경우 hashCode() 메서드와 equals() 메서드를 오버라이드 해야 할 수도 있습니다.


Map<String, String> Map = new HashMap<>();

map.put("key1","value1");
map.put("key1","value1");

System.out.println(map.get("key1")); // value1

HashMap으로 관리되는 데이터 전체를 뽑을 때에는 순서가 뒤섞이게 됩니다. HashCode를 계산해서 사용하기 때문입니다.


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

map.put("Google","USA");
map.put("Naver","Korea");
map.put("Facebook","USA");

for(Map.Entry<String, String> entry : map.entrySet()) {
	System.out.println(entry.getKey() + " : " + entry.getValue());
}

입력된 순서나 Key 값의 정렬 순서는 지켜지지 않고 다 섞이게 됩니다. 다만 다른 Map에 비해 빠른 탐색시간을 갖습니다.

해시 함수를 사용하기 때문에 O(1)의 시간복잡도를 가지게 됩니다.

해싱이란?

해싱은 산술적인 연산을 이용해서 키가 있는 위치를 계산하여 찾아가는 검색 방법입니다. 키 값을 원소 위치로 변환하는 함수를 해시 함수(Hash Function)이라고 합니다.

해시 함수에 의해 계산된 주소에 저장할 값은 해시 테이블(Hash Table)에 저장합니다.

해시 테이블은 빠른 검색 속도를 제공하는데 그 이유는 내부적으로 버킷(배열)을 사용하여 데이터를 저장하기 때문입니다. 그리고 각각의 key 값에 해시 함수를 적용해 배열의 고유한 인덱스를 생성한 후 인덱스를 이용해 값을 저장하며 실제 값이 저장되는 장소를 버킷이라고 합니다.

🤔

10명만 상영할 수 있는 영화관을 만들었는데 좌석은 핸드폰 번호 뒷자리를 통해서 랜덤으로 좌석 배정이 된다고 가정해보자. 이때 랜덤으로 좌석 배정을 해주는 기능을 해싱함수가 해주게 된다.

해시충돌이란?

🤔

영화관이 장사가 잘 되서 좌석수늘 늘렸는데 핸드폰 번호 뒷자리가 같은 사람이 존재한다면? 이러한 경우를 해시 충돌이라고 말할 수 있다.

해시 충돌을 해결하는 방법으로 크게 두가지가 존재한다.

Open Addressing : 이미 자리에 누군가가 있으면 다른 곳으로 배정하는 방식으로 다른곳에 배정하는 방식에 따라 Linear Probing과 Quadratic Probing 등의 방법이 있다.
Separate Chaining : 해시 테이블의 구조를 변경하여 하나 이상의 키값을 저장할 수 있도록 하는 방법으로 이때 주로 사용하는 연결리스트를 사용한다.

HashMap은 어떤걸 사용할까?

HashMap에서 사용하는 충돌기법 방식은 Separate Chaining이다. 자바8 이전은 단순히 연결리스트를 사용하였지만 자바8 이후엔 데이터의 개수가 많아지면 연결리스트가 아닌 트리 자료구조를 사용한다.(트리 종류는 레드 블랙 트리)

데이터의 개수가 많아지는 기준은 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 연결리스트를 트리 구조로 변경하게 된다. 또한 데이터를 삭제해서 6개가 된다면 다시 연결리스트로 변경한다.

7을 기준으로 잡지 않은 이유는 차이가 1개밖에 나지 않을 경우엔 삽입/삭제가 반복되어 일어날 때 불필요하게 트리와 연결리스트로 변경하는 일이 발생하기 때문이다.

하지만 특정 버킷의 노드 개수가 8개면 트리로 바로 변환이 되는 줄 알았지만 실제로 보면 해시 맵의 크기가 64보다 작다면 트리로 변환시켜주지 않습니다.

64보다 작을 경우에는 resize()가 수행되고 해당 버킷의 개수가 8개 이상 쌓일 시 resize() 메서드를 통해 다른 버킷으로 데이터를 옮겨서 하나의 버킷에 많은 데이터를 관리하지 않도록 분할시켜줍니다.

그 후 해시맵의 크기가 64보다 같거나 클 경우에 그때 버킷 내부를 리스트가 아닌 트리로 변경하여 관리하도록 합니다.

해시 버킷의 확장

버킷은 결국 배열로 구성되어 있으며 HashMap을 사용할 때 따로 이 버킷의 개수를 지정해 주지 않았다면 기본값은 16으로 버킷의 개수가 지정된다.

버킷의 개수가 일정 개수 이상이 되면 버킷의 개수를 2배로 늘리게 되며 버킷을 늘리면 해시 충돌의 가능성도 낮아지기 때문에 충돌 문제를 해결할 수 있지만 두배로 버킷의 개수가 증가할 때마다 새로운 Separate Chaining을 구성해야 하는 문제도 있다.

따라서 데이터의 개수가 예측 가능하다면 지정하여 생성자의 인자로 넣어주면 불필요한 Separate Chaining을 줄일 수 있다.

해시 버킷의 개수가 일정 개수 이상이 되면 그 수를 두배로 늘리는데 그 기준은 기본 값으로 0.75f로 설정되어 있으며 3/4 정도가 찰 경우에 두배로 확장하게 된다.

2️⃣ TreeMap - O(log N)

TreeMap은 HashMap과 달리 입력된 Key-Value 쌍을 내부적으로 RedBlack Tree로 저장하여 관리합니다.따라서 Key 값을 기준으로 정렬된 상태를 유지할 수 있습니다.

이 때, key 값으로 사용할 클래스에 Comparator 인터페이스를 구현하면 사용자가 정렬된 순서를 조정할 수 있습니다.

HashMap에서 사용한 예제를 TreeMap으로만 바꿔서 실행해보면 사전순으로 정렬된 결과를 확인할 수 있습니다.

TreeMap은 데이터를 내부적으로 RB-Tree 형태로 관리하기 때문에 데이터를 탐색하는데 O(log N)의 시간이 걸리게 됩니다. 또한 엘리먼트의 추가/삭제 역시 O(log N) 시간이 걸리며 HashMap 보다는 조금 느린 속도를 가지게 됩니다.


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

map.put("Google","USA");
map.put("Naver","Korea");
map.put("Facebook","USA");

for(Map.Entry<String, String> entry : map.entrySet()) {
	System.out.println(entry.getKey() + " : " + entry.getValue());
}

RedBlack Tree?

자가 균형 이진 탐색 트리로써 대표적으로는 연관 배열을 구현하는데 쓰이는 자료구조 입니다.

특정 key 값에 대해서 삽입, 삭제, 탐색이 가능한 자료구조로 가장 큰 특징은 자신의 왼쪽 서브 트리에는 자신보다 key 값이 작은것 오른쪽 서브 트리에는 key 값이 큰 값으로 들어오게 됩니다.

알고리즘 ) Red-Black Tree

얼른 iOS글도 써야하는데...ㅎ_ㅎ 뭐 연휴는 기니까.... 히유ㅠㅠ강의자료 보다보니까, 이때 생각도 나고 디게 그립네요. 몇달전에 제가 공부하던것들인데 말이에요. 그 중에서도..네..시험에 Red-Black Tree가 나왔는데.. 바닥에 지우개가 떨어져서 줍지도 못하고 그 샤프 뒤에 있는 그 짱쪼끄만 지우개로 지우면서 문제를 풀었던 기억이 있네요ㅎㅎ 그만큼 지우개가 상당히 중요한 Red-Black Tree입니다 ㅎ 간단하게 Red-Black Tree에 대한 글을 써보려고해요 :) 한글로 적흑트리, 적흑나무 라고 말한 책도 있는데...

https://zeddios.tistory.com/237

3️⃣ LinkedHashMap - O(1)

LinkedHashMap은 데이터의 “입력된 순서"를 기억합니다.

LikedHashMap에 저장되는 각 항목은 Map.Entry 클래스를 구현한 Node 클래스로 내부에 before, after 멤버를 갖는 연결리스트 구조를 가지고 있습니다.

동일하게 같은 예제를 LikedHashMap으로 변경해서 실행해보면 입력한 순서대로 나오게 됩니다.


Map<String, String> map = new LikedHashMap<>();

map.put("Google","USA");
map.put("Naver","Korea");
map.put("Facebook","USA");

for(Map.Entry<String, String> entry : map.entrySet()) {
	System.out.println(entry.getKey() + " : " + entry.getValue());
}

🧑🏻‍⚖️ 결론

HashMap은 순서를 보장하지 않지만 탐색 속도가 빠르다.

TreeMap은 Key 값으로 사용된 클래스의 비교 연산을 활용하여 순서를 보장한다.

이때 Key 값으로 사용한 클래스가 Comparator 인터페이스를 구현하면 원하는대로 순서를 조정할 수 있다.

LinkedHashMap은 입력된 순서를 보장한다

각각의 특성이 모두 다르지만, TreeMap이나 LinkedHashMap을 사용해야 하는 특별한 이유가 없다면?

🔥

HashMap을 사용하자 그 이유는 시간 복잡도가 O(1) 이며 해시값을 사용하기 때문이다. RB-Tree를 사용하는 TreeMap의 접근 연산은 O(log N)이지만 정렬된 순서를 얻을 수 있다. LikedHashMap의 경우 O(1)의 시간 복잡도를 갖긴 하지만 불필요하게 Liked-list를 유지하는 비용이 발생할 수 있다.