22

해시테이블 해시함수

호너의 법칙(Horner's method)

다항식(polynominal)을 효율적으로 계산할 수 있는 단항식으로 바꾸는 방법.

예를들어 $5x^4 + 2x^3 – 3x^2 + x – 7$ 가 있고 $x = 3$이라고 하면 아래처럼 계산되고 결과 값은 428이 된다.

곱셈 10(n*(n+1)/2)번에 덧셈 5(n)번이 필요함. 이것을 일반화했을 때 n차 다항식에서 필요한 덧셈과 곱셈의 횟수는 아래와 같다.

우리는 이를 코드로 구현해야하는데, 리소스 낭비를 줄이기 위해서 호너의 법칙을 이용하면 곱셈을 덜 할 수 있게 된다

$p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_nx^n$ $= a_0 + x(a_1 + x(a_2 + x(a_3 + ... +x(a_{n-1} + xa_n)...)))$ 실제 예시에 적용시켜보면

곱셈 4(=n)번 덧셈 4(=n)번으로 훨씬 줄어든 것을 확인할 수 있다.

호너의 법칙 알아서 뭐함?

문자열 속에서 특정 부분문자열을 찾고자할 때 해시된 값으로 비교할 때 쓰임

std::string 문자열 = "THISISATESTTEXT"std::string 찾고싶은문자열 = "TEST"

해싱을 모르면 찾고싶은문자열 의 글자 하나하나를 떼다가 문자열에 존재하는지 비교하고, 연속하고 있는지 여부까지 판별해야할 것이다

하지만 해싱 값으로 비교한다면 더 간단하게 찾아낼 수 있음. 찾고싶은문자열을 해시함수에 넣어 H찾고싶은문자열을 구하고 문자열을 0번째 인덱스부터 찾고싶은문자열의 길이만큼 증가하며 순회해 포함여부를 알아낸다.

예를들어 H찾고싶은문자열이 80이고 문자열을 찾고싶은문자열의 길이만큼 해싱한 테이블이 있다면 다음과 같이 찾아낼 수 있다.

이런 알고리듬을 '라빈 카프 문자열 매칭 알고리듬(Rabin-Karp String Matching Algorithm)'이라고 하는데, 이 알고리듬에서 해시 함수는 rolling hash 기법을 사용한다고 한다. $H[i] = S[i]*2^{m-1} + S[i + 1]*2^{m-2} + ... + S[i+M-2]*2^1 + S[i+M-1]*2^0$ 이를 우리의 예시 TEST로 적용시키면 아래와 같다. $H[0] = T(=84)*2^3 + E(=69)*2^2 + S(=83)*2^1 + T(=84)*2^0$ T, E, S, T의 아스키 코드 변환 값을 넣어주고, 2에 해당하는 숫자는 문자 코드의 크기(아스키 코드 = 256개)를 넣어주면 된다고 한다.

문제는 이 때에도 해시 충돌 현상은 피할 수 없으며 때문에 찾고싶은 문자열의 해시 값과 부분문자열의 해시 값이 같을 때 진짜 같은 문자열인지 검증하는 단계가 필요하고, 이를 위해 $2^{M-1}$ 과 같은 곱연산이 추가되었다고 이해하면 되겠다.

Q1. 문자열이 길어지면 해시 함수 연산량 감당 어케함?

A. 여기에 호너의 법칙이 사용된다.

Q2. 문자열이 길어지면 해시값 오버플로우 발생할 수 있지 않음?

A. 그래서 모듈러(%) 연산을 사용해 줄여준다. 이 때 큰 소수(big prime number)를 사용하는 것이 효과적이라 알려져있다

Q3. 근데 이것도 일일이 비교하는거랑 다를게 뭐임?

A. 그래서 해시 계산 최적화 유도식이 나왔다. $H[i+1] = 2*(H[i]-C[i]*2^{m-1})+C[i+m+1]*2^0$ 다음 해시는 이전 해시에서 맨처음 문자 계산 값을 빼고 마지막 문자 계산값을 더해주면 된다.

따라서 문자의 길이와 상관없이 최초로 구한 해시값만 있으면 항상 2개의 문자에만 접근하면 다음 해시값을 쉽게 구할 수 있게 된다.

라빈카프 알고리즘의 평균(average) 및 최고(best) 시간복잡도는 $O(n + m)$이지만 최악(worst)의 경우는 $O (nm)$이다.

최악의 경우 = P[] = "AAA", S[] = "AAAAAAA"

호너의 법칙 적용한 해시함수

static int GenerateHash(const std::string& keyString){	// "ABCD" [A,B,C,D] = [65,66,67,68]    // "ABCD" == "DCBA"	int hash = 0;		const int length = static_cast<int>(keyString.length());	for (int ix = 0; ix < length; ++ix)	{		hash = hash * 31 + keyString[ix];	}}

String 객체 해시 함수에서 31을 사용하는 이유는, 31이 소수이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다. 31N=32N-N인데, 32는 25이니 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은, (N << 5) – N과 같다. 31을 곱하는 연산은 이렇게 최적화된 머신 코드로 생성할 수 있기 때문에, String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.