AVL 트리의 성능에 만족하지 못할 수도 있다. 그리고 이러한 상황에서 도입을 검토할 수 있는 자료구조가 바로 ‘테이블’이다.
테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보이니, 테이블의 탐색성능을 표현하는데 있어서 ‘단번에’라는 표현을 써도 괜찮지 않겠는가
표에 저장된 데이터의 형태가 다음과 같을 때에만 테이블로 구분 짓는다.
“저장되는 데이터는 키와 값이 하나의 쌍을 이룬다.”
테이블에는 키와 관련해서 다음의 조건이 존재한다.
“키가 존재하지 않는 값은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다.”
테이블은 사전(dictionary) 혹은 맵(map) 이라 불리기도 한다.
typedef struct _empInfo
{
int empNum;
int age;
} EmpInfo;
키를 결정하였다면, 이를 기반으로 데이터를 단번에 찾을 수 있어야 한다.
“직원 고유번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않다.”
“직원 고유번호의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.”
이 두 가지 문제를 동시에 해결해주는 것이 마로 ‘해쉬 함수’이다.
중요한 점만 적도록 하겠다.
해쉬함수가 똑같은 값을 반환하는 충돌 (collision) 을 해결해야 한다. (혹은 충돌 최소화)
“좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다.”
좋은 해쉬 함수의 디자인 방법은 키의 특성에 따라 달라진다. 때문에 해쉬 함수의 디자인에 있어서 절대적인 방법은 존재하지 않는다. 다만 위의 조언, 키 전체를 참조하는 방법과 관련하여 다양한 방법이 소개되고 있는데, 그중 하나는 다음과 같다.
“여뎗 자리의 수로 이뤄진 키에서 다양한 해쉬 값 생성에 도움을 주는 네자리의 수를 뽑아서 해쉬 값을 생성한다.”
키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 지극히 상식적인 방법이다. 그리고 이와 유사한 방법으로 ‘비트 추출 방법이 라는 것이 있다. 이는 탐색 키의 비트 열에서 일부를 추출 및 조합하는 방법이다.
이어서 소개할 방법은 ‘자릿수 폴딩’이다. 폴딩은 ‘접는다’는 뜻이 있다. 그럼 다음 그림에서 보이듯이 숫자를 종이에 쓴 다음에 이를 삼등분 하여 접어보자.