[Algorithm] 해시 테이블(Hash Table) 해시함수(Hash Function)에서 문자열 키(key)값을 정수로 바꾸기
해시 테이블에서 문자열을 받았을 때 해싱하는 방법을 알아보자
환경 및 선수조건
- C++
- Hash의 개념
- Hash Table의 개념
String을 Key값으로 받았을 때
- 1번의 방식은 단순하나 중복이 될 가능성이 크며 2~3번의 방식이 분포를 더 크게 만들 수 있다.
- 만약 연산중에 혹은 결과 값이 해시 테이블의 크기보다 크다면 해시 테이블의 크기만큼 나누어서 나머지의 값을 취하면 된다.
1. 문자열에 있는 문자들을 모두 더하기
- 문자열에 있는 문자들을 다 더해서 계산하는 방식
- 단, 아래와 같은 경우에는 “abc”, “acb” 그리고 “cba”의 결과가 모두 같다는 단점이 있다. 즉
hashCode("abc")==hashCode("acb")==hashCode("cba")
int hashCode(String s){
int r = 0;
for(int i = 0; i < s.length(); i++){
r += s[i];
}
return r;
}
2. 다항식을 이용해서 구하기
h(s) = xk-1 × ak-1 + xk-2 × ak-2 + ... + x0 × a0와 같은 다항식을 바탕으로 만드는 방식- 특정한 값
a(일반적으로 소수가 좋다고 한다.)를 곱하고 문자열에 있는 문자를 더하면서 완성해가는 방식
int hashCode(String s){
int i;
int r = 0;
// Special Prime Number
int a = 33;
for(i = 0; i < s.length(); i++){
r += r*a + s[i];
}
return r;
}
3. 시프트(Shift) 연산자를 이용해서 구하기
- 위에 2번에 있는 다항식의 방법과 똑같은데 시프트(Shift)연산을 이용해서 값을 곱하는 방식
int hashCode(String s){
int i;
int r = 0;
for(i = 0; i < s.length(); i++){
r += (r<<4) + s[i];
}
return r;
}