순차 검색(Sequential Serach)
순차적으로 비교하면서 검색하는 알고리즘으로 선형 검색 방법입니다.
구현은 쉽지만 성능이 나쁩니다.
O(N)
이진 검색(Binary Search)
제어 검색 방법으로 정렬 상태에서만 검색할 수 있습니다.
키와 가운데 요소와 비교하여 키가 크면 뒤쪽 배열에서 재귀적으로, 작으면 앞쪽 배열에서 재귀적으로 검색합니다.
탐색 속도가 좋습니다.
O(logN)
해시(Hash) 알고리즘
해시 테이블(Hash Table)에 해시 함수(Hash Function)을 이용하여 자료를 저장하거나 검색하는 자료구조 및 알고리즘
해시 함수에 의해 자료를 저장할 위치나 저정한 위치를 계산하는 것을 해싱(Hashing)이라 부른다.
해싱(Hashing)은 해시 함수에 위해 결정한 위치에 직접 접근(Direct Access Method)이 가능합니다.
검색 속도가 가장 빠릅니다.
키를 해시 함수에 의해 보관할 혹은 보관한 주소로 변환하는 방식입니다.
해쉬 테이블의 구성
슬롯(Slot): 하나의 레코드를 저장할 수 있는 공간
버켓(Bucket): 해시 함수에 의해 결정한 하나의 주소를 갖는 구역
버켓 크기: 하나의 주소를 갖는 구역의 크기
충돌(Collision): 서로 다른 레코드의 키를 해싱에 의해 나온 주소가 같을 때, 이러한 키의 집합을 동의어(Synonym)이라 부름
오버플로우(Overflow): 충돌이 발생하였고 버켓이 꽉 차 저장할 기억 공간이 없을 때
해시 함수의 종류
제산법: H(key) = Key % Prime No, 키를 소수(Prime Number)로 나눈 값으로 주소 결정
제곱법: (Key^2)한 값의 중간 부분으로 주소 결정
폴딩법: 키 값을 여러 부분으로 분류하여 분류한 부분을 더하거나 XOR하여 주소를 계산
기수 변환법: 특정 진법으로 표현한 레코드 키 값을 다른 진법으로 간주하고 키 값을 변환하여 홈 주소를 취함
계수 분석법: 주어진 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수를 택함