[Advanced] 8. 문자열 탐색 - 이론편

해싱

특정 항목 검색 시, 탐색 키에 대한 산술적 연산으로 키가 있는 위치를 계산하여 바로 찾아가는 방법

• O(1) 시간에 자료에 접근

 

직접 번지 테이블

모든 가능한 키들의 집합 U, 실제 사용되는 키들의 집합 k가 있고 자료가 담긴 테이블 T가 있음
T(k)를 통해 자료를 검색할 수 있음

해시테이블

모든 가능한 키들의 집합 U에 비해 실제 사용되는 키들의 집합 k가 작을 경우 메모리가 낭비됨
→ 실제 사용되는 집합 k의 사이즈로 줄임

키 값 k의 자료를 저장할 위치를 계산하는 해시 함수(h)를 사용하여 자료를 h(k)에 저장

 

해시 함수

모든 키들의 집합 U={0,1,2,...N}를 해시 테이블 T[0 .. m-1]의 위치에 대응시킴

테이블의 인덱스 범위를 줄여줌

h(k)는 키 k의 해시 값(주소)이라 함

키 두 개가 동일한 위치가 되는 상황을 충돌이라 함

• 서로 다른 키 값을 해시 함수에 적용했는데, 반환된 해시 주소가 동일한 경우
• 해시 함수가 아무리 해시 주소를 공평하게 분배해도 해시 테이블에 저장되는 키에 해당하는 자료의 수가 증가하면 충돌남
• 해결법 - 체이닝(Chaining), 개방주소법(Open addressing)

 

체이닝(Chaining)

해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 가지는 자료가 저장될 수 있도록 하는 방법

하나의 버킷에 여러 개의 키 값을 저장하도록 연결 리스트 활용

 

개방주소법(Open addressing)

해시 함수로 구한 주소에 빈 공간이 없어 충돌이 발생하면, 그 다음 공간에 빈 공간 여부를 조사

• 빈 공간이 있으면, 거기에 저장
• 빈 공간이 없으면, 나올때까지 반복