비선형 데이터구조, 해시(Hash) #3 해시 크기 최적화 및 양수로 전환

이전글

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

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

 

개요

이전글에서는 해시 함수에 문자열을 넣어 문자열에 따른 해시함수 값을 계산하는 해시함수를 구현하였습니다. 그런데 해시 함수에 키를 넣어 해시함수값을 구하여도 동일한 해시함수 값이 나올 수 있습니다. 따라서 이번글에서는 해시 충돌을 방지하기 위해서 해시 크기를 최적화하는 방법에 대해서 알아봅니다.

 

1. 해시 크기 최적화

해시 함수에 객체를 넣었을때 해시 함수 값은 정수가 나옵니다. 하지만 오직 양수만 나오는 것이 아닌 음수도 나올 수 있습니다. 음수를 양수로 변환하여도 양수 값이 너무 높아서 배열의 범위를 벗어날 수 있습니다. 또는 동일한 해시 함수 값이 나와서 해시 충돌(collision)이 발생할 수 있습니다. 따라서 정수를 배열에 사용하기 위해서는 최적화 작업이 필요합니다. 

 

해시의 충돌을 예방하기 위해서는 테이블의 크기를 최적화합니다.

• 예시1 : 테이블의 크기를 홀수로 설정하여 % 연산자를 사용했을 때 다양한 결과가 나오게 합니다.
• 예시2 : 테이블의 크기를 소수로 설정하여 나머지가 다양한 숫자가 나오게 합니다.

 

2. 양수로 전환

예를 들어 다음과 같이 음수가 해시 값이 될 수 있습니다.

-10 % 3 = -1
10 % 3 = 1

위와 같이 -1이 해시 값이 되는 경우 양수로 전환하는 것이 좋습니다. 이유는 테이블의 값(value)에 접근하기 위해서는 양수여야 합니다.

 

위와 같이 해시 함수 값이 음수이거나 배열의 범위를 초과하는 해시함수 값이 나오는 문제점을 해결하기 위해서 다음과 같은 단계를 수행합니다.

• 객체를 해시함수에 넣어 정수 값을 반환받음
• 음수일수도 있는 정수값을 양수로 전환
• 배열(테이블)의 범위를 벗어날 수도 있기 때문에 테이블 크기에 최적화 수행

위 단계를 코드로 구현하면 아래와 같습니다. (Java에서는 음수를 표현하기 위해 2의 보수를 활용합니다. 첫 숫자가 0이면 양수고, 1이면 음수입니다.)

// data의 index 결정
int hashval = data.hashCode(s);	// 정수 반환
hashval = hashval & 0x7FFFFFFF;	// 양수로 전환
hashval = hashval % tableSize;	// 테이블 크기에 맞게 최적화

hashval 정수값에 &0x7FFFFFFF을 and 연산하면 음수가 양수로 전환됩니다.

 

정리하면 해시 함수 값은 음수가 나올 수 있고 양수로 나왔다 하더라도 테이블의 범위를 벗어나는 양수가 나올 수 있습니다. 이 문제를 해결하기 위해서 "0x7FFFFFFF"를 and연산하면 양수로 전환이 가능하고 테이블 사이즈로 나머지 연산을 하면 테이블 사이즈 범위에 맞는 해시 함수 값(인덱스)을 얻을 수 있습니다.

 

References

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