Algorithm. 문자열 - 해싱

자주 수행되는 작업들

• 디렉토리 경로 따라가기
• 디렉토리 내에 존재하는 파일들 나열하기
• 특정 파일의 존재 유무 판별하기

해당 작업들은 시스템의 성능 저하의 원인이 된다. 이 작업들은 검색에 기반해서 수행되는 작업들이므로 어떻게 해결해야할까.

 

1. 해싱

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

• O(1) 시간 복잡도

1. 직접 번지 테이블

직접 번지 테이블(배열)에 저장하는 경우

• 전체 키(key)들의 집합(U)이 작은 경우에 효율적이다.
• 키 k가 테이블(T)에서 위치 k에 저장
• 테이블(배열)의 크기 = 집합 U의 크기

그러나 전체 키 값들의 집합 U가 클 때, 현실적인 컴퓨터 메모리 공간에서 테이블 T를 생성하는 것은 불가능하다. 또한 실제 저장되는 키들의 집합 k가 집합 U에 비해 상대적으로 작아서 T의 많은 메모리 공간이 낭비된다.

 

2. 해시 테이블

• 모든 가능한 키들의 집합 U에 비해 실제 사용되는 키들의 집합 k가 작은 경우
  • 해시 테이블 메모리 공간 < 직접 번지 테이블 메모리 공간
• 저장 공간을 Θ(|K|)로 줄인다.
• 키 값 k의 자료를 저장할 위치를 계산하는 해시함수 h를 사용한다.
• 키 값이 k인 자료를 h(k)의 위치에 저장한다.

2. 해시 함수

• 모든 키들의 집합 U = {0, 1, 2, ... ,N}를 해시 테이블 T[0, .. , m-1]의 위치에 대응시킨다.
• 테이블의 인덱스 범위를 줄여준다.
• h(k)는 키 k의 해시 값(주소)이다.
• 키 두개가 동일한 위치가 되는 상황을 충돌이라한다.

3. 충돌

• 서로 다른 키 값을 해시 함수에 적용했는데, 반환된 해시 주소가 동일한 경우이다.
• 해시 테이블에 저장되는 키에 해당하는 자료의 수가 증가하면 충돌이 불가피하다.
• 충돌 해결법
  1. 체이닝(chaining)
  2. 개방 주소법(open addressing)

 

4. 체이닝

• 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 가지는 자료가 저장될 수 있도록 하는 방법
• 하나의 버킷에 여러 개의 키값을 저장하도록 하기 위해 연결 리스트를 활용한다.

 

5. 개방 주소법

• 해시 함수로 구한 주소에 빈 공간이 없어 충돌이 발생하면, 그 다음 공간에 빈공간 여부를 조사
• 빈 공간이 있으면, 탐색키에 대한 항목 저장
• 빈 공간이 없으면, 공간이 나올 때까지 탐색 반복