비선형 데이터구조, 해시(Hash) #2 해시함수에서 문자열

이전글

https://yonghwankim-dev.tistory.com/171

비선형 데이터구조, 해시(Hash) #1 해시소개

 

개요

이전글에서는 해시 함수에 문자열을 넣으면 필요없는 문자열을 제거한 후 숫자 부분만 추출하고 재가공하여 인덱스를 계산하였습니다. 이번글에서는 key가 문자열일때 해시함수값을 계산하는 방법에 대해서 소개하겠습니다.

 

1. 해시 함수에서 문자열

예를 들어 다음과 같은 코드가 있습니다.

String s = "my name is Rob";
char c = s.charAt(6);
System.out.println(c);

위와 같은 코드를 실행할 때 결과는 아래와 같습니다.

m

s.charAt(6) 메서드 호출로 문자열의 6번째(공백포함) 문자인 m을 문자 변수 c에 저장하고 출력한 것입니다. 이번에는 아래와 같은 코드가 있습니다.

String s = "my name is Rob";
int i = s.charAt(6);
System.out.println(i);

정수형 변수 i에 문자 'm'을 넣고 출력할 때 결과는 아래와 같습니다.

109

이유는 아스키 코드값으로 소문자 'm'은 109에 해당되고 정수형 변수에 저장될때 변환된 것이기 때문입니다.

 

위의 예제와 같이 문자를 숫자로 변경할 수 있다면 해시 함수에 문자열이 들어오더라도 숫자로 변경하여 해시함수 값을 계산할 수 있습니다. 해시 함수의 수식내용은 각각의 문자에 따른 아스키 코드 값을 더하여 합계를 내는 것이 해시 함수 값입니다.

 

예를 들어 "this"라고 하는 문자열을 해시 함수에 넣을때 해시함수 값은 다음과 같이 계산됩니다.

t h i s
=> 116 + 104 + 105 + 115 = 440

하지만 위의 해시함수 수식은 문제가 있습니다. 문제점은 각 문자의 위치를 변경하여도 같은 값이 발생합니다.

h i t s
=> 104 + 105 + 116 + 115 = 440

"this" 문자열과 "hits" 문자열을 해시함수에 넣을때 해시 함수 값은 동일합니다. 이는 해시 충돌이 발생한 것입니다.

위 문제점을 개선하기 위해서는 어떤 상수 g를 문자의 위치 만큼 제곱한 뒤에 그 수를 곱하면 문제가 해결됩니다.

t		h		i		s
116		104		105		115
*		*		*		*
g^0		g^1		g^2		g^3

116*g^0 + 104*g^1 + 105*g^2 + 115*g^3

문자열을 해시로 나타내는 함수는 다음과 같습니다.

public static int hashCode(String s) {
		int g=31;
		int hash=0;
		// 문자열을 숫자로 나타내기
		// 상수 g를 문자의 위치만큼 제곱한 뒤 곱합니다.
		for (int i=0; i<s.length(); i++)
			hash = (int) (Math.pow(g, i) * s.charAt(i));
		return hash;
}

System.out.println(hashCode("this"));	// Expected Output : 3425965

 

References

[부스트코스] 자바로 구현하고 배우는 자료구조