검색_Search

검색(Search)

검색과 키

• 키(Key) - 데이터의 일부

검색의 종류

• 배열검색
  1. 선형검색 - 무작위로 늘어놓은 데이터 집합에서 검색수행
  2. 이진검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 수행
  3. 해시법 - 추가 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행
     1. 체인법 - 같은 해시값 데이터를 연결리스트로 연결
     2. 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법
• 연결리스트 검색
• 이진 검색 트리 검색

선형 검색(LinearSearch)

• 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을때까지 맨앞부터 스캔하여 순서대로 검색하는 알고리즘
• 선형 검색의 종료조건
  1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 - 검색 실패
  2. 검색할 값과 같은 원소를 찾은 경우 - 검색 성공

보초법(Sentinel Method)

• 선형검색은 반복할 때 마다 2가지 종료조건을 체크한다. 단순하지만 비용(cost)를 무시할 수 없다. 이 비용을 반으로 줄이는 방법.
• 검색하고자 하는 키값을 끝에 추가한다. 이때 저장하는 값을 보초(Sentinel)이라고 한다. 그러면 선형 검색의 종료 조건 1을 체크 하지 않아도 돼서 코스트가 절감된다.

복잡도

• 시간복잡도(Time Complexity) : 실행하는데 필요한 시간을 평가
• 공간복잡도(Space Complexity) : 메모리(기억공간)와 파일공간이 얼마나 필요한지

해시법(hashing)

• ‘데이터를 저장할 위치 = 인덱스’ 간단한 연산으로 구하는 것
• 해시값(hash value) - 해시값은 데이터에 접근할 때 기준이 된다.
• 해시값을 인덱스로 하여 원소를 새로 저장한 배열이 해시테이블(hash table)이 된다. 이렇게 키를 해시값으로 변환하는 과정을 해시함수(hash function) 라고 한다.
• 일반적으로 해시함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.
• 해시테이블에서 만들어진 원소를 버킷(buket)이라고 한다.
• 키와 해시값은 일반적으로 다대1(n:1)이다.

해시충돌

• 저장할 버킷이 중복되는 형상을 충돌(collision)이라고 한다.
• 충돌이 발생한 경우 2가지로 대처한다.
  1. 체인법 - 해시값이 같은 원소를 연결리스트로 관리
  2. 오픈주소법 - 빈 버킷을 찾을 때까지 해시를 반복

체인법(Chaining)

• 해시값이 같은 데이터를 체인(chain) 모양의 연결리스트로 연결하는 방법 오픈 해시법(open-hashing)이라고도 한다.
• 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로 하는 연결리스트의 앞쪽노드를 참조하는것
• 노드(Node)
  • Key - 키
  • Value - 값
  • Next - 뒤쪽 노드를 참조

오픈 주소법(Open addressing)

• 오픈 주소법은 충돌이 발생했을때 재해시(Rehashing)을 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(Closed hashing)이라고도 한다.
• 오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형탐사법(Linear Probiny)이라고 한다.