자료구조_14.탐색(2)

MAP

---

Map은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조 입니다.

key에 대응하는 value도 같이 저장하는 컨테이너입니다.

#include<map>에 들어있습니다.

 

중복저장을 되지 않고 전체 조회시 정렬된 상태로 출력이 됩니다.

추가, 탐색, 삭제 시간 복잡도는 O(log n)입니다.

 

그 이유는 검색트리의 작업들은 트리의 높이(깊이)와 밀접한 관련이 있습니다.

Worst balanced

균형 이진 검색 트리는 O(log n)-시간 검색,  삽입, 삭제를 보장해줍니다.

 

 

 

해시테이블

---

다른 탐색 방법들은 키 값 비교하여 항목에 접근하고
키 값의 연산에 의해 직접 접근이 가능한 구조입니다.

 

해시테이블은 배열과 비슷하게 여러 자료를 담을 수 있는 메모리 공간 할당입니다.

 

하지만 다른점은 인덱스가 아닌 키를 사용하여 메모리에 접근

해시 함수를 통해서 키가 인덱스로 변환됩니다.

키는 숫자,문자열 모두 가능합니다.

 

해싱 VS 배열

---

해싱은 특정 데이터가 들어온 순서 상관없이 삽입, 삭제, 검색이

자주 발생하는 경우에 사용하기 좋습니다.

 

배열의 강력한 특징은

Index기반으로 데이터간의 순서가 확실하게 매겨져 있다 라는 점이 있습니다.

 

즉 순서 상관없이 각각의 데이터가 자주 들어오고 나가는 경우에 해싱이 꼭 필요합니다.

 

 

충돌과 오버플로우

---

충돌이란 어떤키값으로 도출된 주소에 이미 다른키가 자리하고 있는걸 의미합니다.

해시 충돌이 일어나면 데이터의 삽입, 삭제, 검색을 원하는대로 바로 할 수 없고 시간이 걸립니다.

충돌 수를 줄이기 위해 해시테이블은 일반적으로 들어갈 최대 데이터의 3~4배 정도의 크기로 설정합니다.

 

오버플로우는 충돌이 슬롯 수보다 많이 발생하는 것입니다.

 

충돌 해결 방법

---

충돌 해결 방법으로는 체이닝과 개방 주소 방법이 있습니다.

 

체이닝은 같은 자리에서 충돌이 일어난 원소들은 하나씩의 연결리스트로 관리합니다.

테이블의 각 원소는 연결리스트 하나씩을 링크하게 됩니다.

 

개방 주소 방법은 주어진 배열 안에서 해결하는 방법입니다.(선형탐색, 이차원 탐색, 더블헤싱)

 

Unordered_map

---

자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료 구조입니다.

key에 대응하는 value도 같이 저장하는 컨테이너입니다.

#include<unordered_map>을 해야 사용 가능합니다.

중복저장이 안되고 전체 조회시 정렬이 안된 상태로 출력됩니다.

추가, 탐색, 삭제 시간 복잡도는 O(1)입니다.(해시테이블이 구현되있기 때문입니다.

 

Set

---

key라 불리는 원소의 집합으로 이루어져있습니다.

#include<set>을 해야 사용 가능합니다.

균형 이진 트리(레드블랙트리)로 구현되었습니다.

중복 삽입이 불가하고 데이터는 정렬되있습니다.

연산 시간 복잡도는 O(log n)입니다.

 

Unordered_set

---

#include<unordered_set>을 해야 사용 가능합니다.

해시테이블로 구현되어있고 정렬이 되어있지 않습니다.

시간복잡도는 O(1)입니다.

 

 

정리

---

	Key	Value	Key 정렬 여부	탐색 시간 복잡도
map	O	O	O	O(log n)
unordered_map	O	O	X	O(1)
set	O	X	O	O(log n)
unordered_set	O	X	X	O(1)