#6-4 The Art of Computer Programming - 정렬과 검색

이번 절은 그 이름도 유명한 '해싱'이다.

사실 해싱이라는 용어는 정말 자주 듣는 것 중에 하나인데

그냥 특정 문자열을 겹치지 않는 다른 형태의 문자, 숫자, 특수문자의 조합 열로 바꿔주는 걸로만 알고 있다.

 

지금까지는 주어진 인수 K를 테이블의 키들과 비교하거나 인수의 숫자들로 분기 공정을 결정하는 방법을 사용했다.

K에 대한 어떤 산술 계산을 수행해서 그러한 모든 탐색 작업을 피하는 기법에 대해 소개한다.

 

바로, 테이블 안의 K 및 관련 자료의 위치를 함숫값으로 하는 적절한 함수 f(K)를 이용하는 것이다.

그러나 f(K)가 중복 값을 내지 않는 게 상당히 중요하다. (충돌 방지)

 

Hash: 무언가를 잘게 썰거나 뒤범벅으로 만든다는 의미.

해싱의 핵심 : 키의 어떤 측면들을 뒤섞어서 얻은 부분적 정보를 검색의 기초로 사용.

 

해시 함수 : 해시 함수 h가 최대 M개의 서로 다른 값들을 받으며 그 값들이 모든 키 K에 대해

0 <= h(K) < M를 만족해야 한다.

실제 응용에서는 파일의 키들이 훨씬 더 중복된다.

충돌 횟수를 줄이기 위해 파일을 거의 동일한 키들의 덩어리들로 분산시키는 해시 함수를 찾아야 한다.

 

좋은 해시 함수의 요구 조건

1. 계산이 아주 빨라야 한다.

2. 충돌을 최소화해야 한다.

 

해싱의 특징

1. 해시 테이블에서 검색이 실패할 경우 우리가 알게 되는 것은 원하는 키가 표에 존재하지 않는다는 것뿐임. 비교에 근거한 검색 방법들은 더 많은 점보를 제공.

 

2. 해시 테이블을 위한 저장소 할당이 다소 까다로운 경우가 있음. 해시 테이블로 사용할 메모리 영역을 따로 마련해야 하는데 공간을 얼마나 잡아야 할지 명확치 않을 수 있음.

 

3. 해싱 방법들을 사용할 때 확률 이론에 크게 의존할 수밖에 없음. 최악의 경우에는 성능이 매우 나빠짐. 따라서 사람의 목숨이 달려있는 항공관제 시스템 등에는 해시 테이블의 적용이 부적합함. 차라리 특정한 상계를 보장하는 균형 트리 알고리즘이 훨씬 안전함.