<C++> 14. 탐색

MAP

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

• key에 대응하는 value도 같이 저장하는 컨테이너

• #include < map >

• 중복 저장 X

• 전체 조회 시 정렬된 상태로 출력 됨

• 추가, 탐색, 삭제 시간 복잡도는 O(log n)

 

 

레드블랙트리

 

Θ(1)-시간 작업을 원한다

해시테이블

• 다른 탐색 방법들은 키 값 비교하여 항목에 접근
• 해시테이블은 키 값의 연산에 의해 직접 접근이 가능한 구조

 

해싱 VS 배열

해싱은 특정 데이터가 들어온 순서 상관 없이 삽입, 삭제, 검색이
자주 발생하는 경우에 사용하기에 좋다.

배열의 강력한 특징은
index기반으로 데이터간의 순서가 확실하게 매겨져 있다!

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

 

해시 함수Hash Functions

 

• 장난감 수준의 함수
      자릿수를 선택: h(001364825) = 35
      접기Folding
          h(001364825) = 1190
• 나누기 방법에 의한 함수Division Method
      h(x) = x % m ← m: 해시 테이블 사이즈, %: 나머지 연산
      m은 소수를 권장
• 곱하기 방법에 의한 함수Multiplication Method
      h(x) = (xA mod 1) * m
      A: (0, 1) 범위의 상수
      m이 굳이 소수일 필요 없음. 보통 2^p(p는 양의 정수).

충돌과 오버플로우

• 충돌(collision): 어떤 킷값으로 도출된 주소에 이미 다른 키가 자리함
• 오버플로우 : 충돌이 슬롯 수보다 많이 발생하는 것

충돌

• 해시 충돌이 일어나면 데이터의 삽입/삭제/검색을 원하는 대로
  바로 할 수 없다. 시간이 걸림
• 충돌 수를 줄이기 위해 해시 테이블은 일반적으로 들어갈 최대
  데이터의 3~4배 정도의 크기로 설정한다.

충돌 해결 방법

체이닝Chaining

Unordered_map

• 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조
• key에 대응하는 value도 같이 저장하는 컨테이너
• #include < unordered_map >
• 중복 저장 X
• 전체 조회 시 정렬 안된 상태로 출력 됨
• 추가, 탐색, 삭제 시간 복잡도는 O(1)
  -> 해시테이블로 구현

set

• Key라 불리는 원소의 집합으로 이루어짐
• #include
• 균형 이진 트리(레드블렉트리)로 구현됨.
  -> 중복 삽입 불가, 데이터 정렬, 연산 시간 복잡도 O(logn)

unorderd_set

• #include <unordered_set>
• 해시테이블로 구현됨. -> 정렬 X, 시간 복잡도 O(1)