n개의 엔트리가 있는 사전이 BST로 표현될 때 Get, Insert, Delete는 O(n) 시간이 걸린다.
이 연산들은 균형 BST를 이용하면 O(log n) 시간 내에 수행된다.
여기서는 Get, Insert, Delete를 O(1) 기대 시간에 수행할 수 있는 기법인 해싱에 대해 살펴본다.
1. 정적해싱
1.1해시 테이블
정적 해싱에서는 키와 값의 쌍이 해시 테이블에 저장된다.
해시 테이블은 ht[0], ..., ht[b-1]과 같이 b개의 버킷으로 분할된다.
각 버킷에 s개의 키 와 값의 쌍이 포함된다.
한 버킷에는 s개의 슬롯으로 구성되며 한 슬롯에는 하나의 사전 쌍을 저장할 수 있다.
보통 s=1이기에 각 버킷은 정확히 하나의 키와 값을 포함한다.
키와 값의 위치는 해시함수에 의해서 결정된다.
이 해시함수는 키값과 버킷을 매핑한다. 즉, 어떤 키값 k를 해시함수에 넣으면 0과 b-1사이의 정수가 된다.
즉, 키 값을 해시함수에 넣었을 때 나온 값을 해시라고 한다.
키 값은 다른데 해시함수에 넣어서 나온 값이 같은 경우 충돌이 일어났다고 한다.
만약 해시값이 같아 같은 버킷에 값이 들어가는데 버킷이 꽉찬경우 오버플로가 발생했다고 한다.
요약하자면, 해싱 기법은 해시함수를 사용하여 키를 해시 테이블의 버킷과 매핑하는 것.
해시함수는 연산이 적으면서 충돌이 최소화 되도록 해야한다.
1.2 해시함수
해시함수는 키를 해시테이블 내의 버킷에 매핑한다.
임의의 키 k를 해시함수에 넣었을 때 나오는 값의 확률이 균일한 것이 좋다. 즉 각 버킷에 배정될 확률이 균일.
이런 특성을 만족하는 해시 함수를 균일 해시함수라고 한다.
다양한 종류의 해시함수가 사용되는데 그 중 일부는 산술 연산을 통해서 계산한다.
많은 응용에서는 키의 데이터타입이 스트링과 같아서 산술 연산을 할 수 없는 경우도 있다. 이럴 땐 키를 정수와 같이 산술 연산이 가능한 데이터 타입으로 변환한 뒤 연산을 수행한다.
다음은 많이 사용되는 해시함수에 대해 소개한다.
1.2.1 division 함수
division함수는 실제로 가장 많이 씅이는 해시함수로 키 값이 음이 아닌 정수라고 가정한다.
해시 값은 mod(%)연산자에 의해 결정된다.
즉, 키를 어떤 정해진 수로 나눈 나머지 값을 해시값으로 사용하는 것이다.
h(key) = key % D;
이 때 버킷의 범위는 0~D-1이고 테이블에는 D개의 버킷이 있어야한다.
D의 선택이 오버플로 발생에 큰 영향을 미친다. 만약 D가 짝수라면 홀수 값을 가진 키들은 모두 나머지가 홀수이므로 홀수 버킷에 사상될 것이고 짝수 값을 가진 키들은 짝수 버킷에 매핑될 것이다.
최상의 성능을 내기 위해서는 소수인 D를 선택해야한다.
1.2.5 스트링 키를 정수로 변환하기
위의 해시함수를 쓰려면 키를 먼저 0 또는 자연수로 변환해야한다.
스트링을 16비트 정수로 매핑하는 방법
unsigned int StringToInt(string s)
{
int length = (int)s.length();//스트링의 문자 수
unsigned int answer = 0;
if(length % 2 == 1)
{
answer = s.at(length-1);
length--;
}
for(int i = 0; i<length;i+=2)
{
answer += s.at(i);
answer += ((int)s.at(i+1))<<8;
}
return answer;
}
위 함수에서는 문자의 쌍을 유일한 정수로 변환한 뒤 이 유일한 정수들을 모두 더한다.
모든 문자들을 8비트씩 이동시키지 않고 더하면 8비트 이하의 정수가 생성되기 때문에 쉬프트하여 더한다.
C++ STL은 T타입의 개체를 음이아닌 정수 size_t로 변환시키는 hash<T>라는 STL템플릿 클래스를 제공한다.
이러한 템플릿 클래스를 사용하여 스트링 값을 음이아닌 정수로 변환하면 된다.
1.3 안전 해시 함수
해시함수는 컴퓨터 보안 분야에서도 사용된다.
메시지 인증이 그런 응용 중 하나이다.
메시지 M이 보안없는 채널을 통해 A에서 B로 전송된다고 할 때.
메시지와 H(msg)값을 함께 보내고 B는 받은 메시지를 해시함수에 넣어서 받은 해시값과 일치하는지 확인하여 원본임을 인증할 수 있다.
하지만 해시 충돌이 일어나지 않도록 해야한다.
이런 특성을 약한 충돌 저항이라고 한다.
해시값을 보고 해시함수에 넣은 값을 알아내기 힘든 특성을
단방향 특성이라고 한다.
h(x)=h(y)인 x, y쌍을 계산을 통해 찾기 힘들게 하는 특성을
강한 충돌 저항이라고 한다.
1.4 오버플로우 처리
오버 플로우를 처리하는 방법에는 open addressing과 chaining이 있다.