● 검색 (Search)
- 컴퓨터에 저장한 데이터 중에서 원하는 항목을 찾는 작업
● 선형 검색 (Linear Search)
- 선형으로 늘어선 데이터 집합(선형 구조)에서 맨 앞 부터 스캔하여 키값을 찾을 때까지 순서대로 검색하는 방식
- 데이터의 정렬 여부와 상관없이 동작한다.
- 데이터의 양이 많아지면 검색에 소요되는 시간이 비례하여 많아진다.
● 이진 검색 (Binary Search)
- 데이터의 가운데에 있는 항목을 키값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방식
- 검색 범위를 반으로 줄여 가면서 빠르게 검색한다.
- 정렬되어 있는 데이터를 검색할 때만 사용할 수 있다.
① 키값이 더 크면 오른쪽 부분을 검색한다.
② 키값이 더 작으면 왼쪽 부분을 검색한다.
● 해시법 (Hashing)
- 키값에 해시 함수를 적용하여 나온 결과를 해시 테이블의 버킷 주소로 사용하여 항목에 접근하는 방식
- 해시 함수(Hash Function) : 키값을 해시값으로 변환하는 연산
- 해시값(Hash Value) : 해시 테이블의 버킷 주소(해시 테이블의 인덱스)
- 해시 테이블(Hash Table) : 해시값을 테이블 내의 버킷 주소로 이용하여 키값을 저장한 테이블
- 버킷(Bucket) : 해시 테이블의 행 인덱스
- 슬롯(Slot) : 해시 테이블의 열 인덱스
● 해시 함수 (Hash Function)
○ 제산 함수 (Division Function)
- 나머지 연산자를 이용하여 버킷 주소를 계산하는 방법
- 버킷 주소 = 키값 mod 해시테이블의 크기
○ 중간 제곱 함수 (Mid-Square Function)
- 키값을 제곱한 후 결과 값의 중간 부분에 있는 적당한 비트를 선택하여 버킷 주소로 사용하는 방법
- 제곱 결과 값에서 주소로 사용하는 비트의 수는 해시 테이블의 버킷 개수에 따라 결정된다.
- 비트의 수가 \(n\)이라 하면 버킷 개수는 \(2^n\)으로 버킷 주소는 \(0\) ~ \(2^n\)\(-1\)이다.
○ 접지 함수 (Folding Function)
- 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 나누고, 나누어진 각 부분을 모두 더하거나 XOR 연산을 하여 버킷 주소로 이용하는 방법
- 해시 테이블 인덱스가 \(n\)자리이면 \(n\)비트로 나눈다.
- 이동 접지 함수(Shift Folding Function) : 마지막을 제외한 모든 부분을 이동시켜 최하위 비트가 마지막 부분의 자리와 일치하도록 우측 끝을 맞추어 더한 값을 버킷 주소로 사용하는 방법
- 경계 접지 함수(Boundary Folding Function) : 나누어진 각 부분의 경계선을 기준으로 접으서 역으로 정렬한 다음 같은 자리에 위치한 수를 더해서 나온 결과값을 버킷 주소로 사용하는 방법
● 해시 충돌 (Hash Collision)
- 서로 다른 키 값에 대해서 해시 함수에 의해 주어진 해시값(버킷 주소)이 같아서 버킷이 중복되는 현상을 말한다.
- 충돌이 발생하면 버킷의 비어있는 슬롯에 키 값을 저장한다.
- 동거자(Synonym) : 서로 다른 키 값을 가지지만 해시 함수에 의해 주어진 해시값이 같아서 같은 버킷에 저장된 키 값들
- 오버 플로우 : 버킷에 비어있는 슬롯이 없는 상태에서 충돌이 발생하여 해당 버킷에 키 값을 저장할 수 없는 상태다.
◎ 개방 주소법 (Open Addressing)
- 오버플로우가 발생하면 비어있는 다른 버킷을 탐색해서 키값을 저장하는 방법이다.
○ 선형 탐사법 (Linear Probing)
- 충돌 시, 다음 버킷에 빈 슬롯이 있는지 탐색한다.
- 빈 슬롯이 있으면 키 값을 저장하고 빈 슬롯이 없다면 다시 그 다음 버킷에 빈 슬롯이 있는지 탐색한다.
○ 제곱 탐사법 (Quadratic Probing)
- 충돌 시, 제곱만큼 건너뛰어서 버킷에 빈 슬롯이 있는지 탐색한다.
- 빈 슬롯이 있으면 키 값을 저장하고 빈 슬롯이 없다면 다시 그 다음 버킷에 빈 슬롯이 있는지 탐색한다.
○ 이중 해시법 (Double Hashing)
- \((h(k) + i * h'(k))\) \(mod\) \(TableSize\) #\(q\)와 \(TableSize\)는 서로소, \(q < TableSize\)
- 2개의 해시 함수를 준비한다.
- 하나는 최초의 버킷 주소를 얻을 때 사용한다. -> \(h(k) = \) \(k\) \(mod\) \(TableSize\)
- 또 다른 하나는 충돌 시에 사용한다. -> \(h'(k) =\) \(q - (k\) \(mod\) \(q)\)
◎ 체인법 (Chaining)
- 해시값이 같은 키들을 연결리스트를 이용해 각 버킷에 하나 이상의 키값을 저장할 수 있도록 하는 방법이다.
댓글