[해시 테이블] 해시 함수

이번 포스팅에서는 해시 함수에 대해서 조금 더 알아보고 해시 함수를 구현할 수 있는 가장 간단한 방법들에 대해서 살펴보겠습니다.

101호: 최지웅
204호: 강영훈
302호: 성태호
711호: 김현승
942호: 손동욱

먼저 주어진 key를 원하는 범위의 자연수로 바꿔서 리턴해주는 것 말고 다른 해시 함수의 조건들을 볼게요.

 

한 해시 테이블의 해시 함수는 결정론적이어야 된다.

• 똑같은 key를 넣었을 때는 항상 똑같은 결과가 나와야 한다는 건데요. 942를 해시 함수에 넣을 때 어쩔 때는 5이 나오고 어쩔 때는 10이 나오고 이러면 안 된다는 거죠. 942를 넣으면 항상 똑같은 결과가 나와야 됩니다.

결과 해시값이 치우치지 않고 고르게 나온다.

• 그러니까 해시 함수에 101, 204, 302, 711, 942나 아무 숫자를 넣었을 때 항상 40만 나오면 안 된다는 거죠. 원하는 범위가 0 부터 100까지의 자연수면, 이 사이에 아무 두 숫자가 나올 확률이 최대한 비슷해야 됩니다..

빨리 계산할 수 있어야 된다.

• 해시 테이블은 모든 연산을 할 때마다 해시 함수를 써야 되는데요. 해시 함수가 비효율적이면 해시 테이블도 비효율적일 수밖에 없겠죠?

이 조건들이 조금 어렵게 느껴질 수도 있는데요. 사실 해시 함수를 만드는 건 생각보다 어렵지 않습니다. 이번 포스팅에서는 가장 간단한 두 가지만 알아보겠습니다.

 

나누기 방법

 

가장 직관적이면서 쉬운 방법은 나누기 방식인데요. 자연수 key를 해시 테이블의 크기로 나눈 나머지를 리턴하는 함수입니다. 그러니까 저장해야 되는 키가 40, 120, 788, 2307이고 배열의 크기가 200이라고 할게요. 그럼 그냥 key를 200으로 나누어서 남는 나머지를 리턴한다는 거죠. 40을 넣으면 40, 120은 120, 788 은 188, 2307은 107가 리턴됩니다.

 

나누기 방법을 코드로 나타내면 이렇게 됩니다.

def hash_function_remainder(key, array_size):
    """해시 테이블의 key를 나누기 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
    return key % array_size


print(hash_function_remainder(40, 200))
print(hash_function_remainder(120, 200))
print(hash_function_remainder(788, 200))
print(hash_function_remainder(2307, 200))

40
120
188
107

어떤 키가 들어와도 0 ~ 원하는 정수 범위의 자연수로 바꿔줍니다.

 

곱셈 방법

 

다음으로 볼 방법은 곱셈 방법입니다. 곱셈 방법은 나누기 방법보다는 조금 까다로운데요.

 

이해를 돕기 위해 예시로 key가 200이고 사용하려는 배열 크기가 30이라고 하겠습니다.

1. 먼저 0<a<1 인 아무 값 a를 정합니다. 일단 임의로 0.6666로 정할게요
2. 그다음에 이 a에 key를 곱합니다. 그러니까 0.666에 200을 곱하면 133.32이 되는데 이때 정수 부분은 버리고 소수 부분만 남깁니다. 0.32가 남습니다.
3. 마지막으로 남은 소수 부분에 배열의 크기를 곱해줍니다. 0.32 * 30 하면 9.6이 되죠. 이번엔 소수점 부분을 버리고 9만 남깁니다.

단계가 조금 많아서 헷갈릴 수도 있는데요. 왜 이 방법이 원하는 범위의 자연수를 리턴하는지 생각해볼까요? a와 key를 곱한 값의 정수 부분을 버리면 그 결과 값은 0.xxxx 이런 식으로 0과 1 사이의 소수가 나올 수밖에 없겠죠? 0과 1 사이의 소수에 테이블의 크기를 곱해버리면, 다시 0과 테이블 크기 사이의 수가 나오죠. 그러니까 0.0001에 테이블 크기 30을 곱하면 0.003이 나오고 0.9999에 테이블 크기 30을 곱하면 29.997이 나오는데요. 항상 0보다 크거나 같고 테이블 크기인 30보다는 작은 숫자가 나옵니다. 그리고 여기서 소수점 뒷자리를 버리니까 원하는 범위의 자연수를 구할 수 있습니다.

 

곱셈 방법도 코드로 작성해 볼까요?

def hash_function_multiplication(key, array_size, a):
    """해시 테이블의 key를 곱셈 방법으로 0 ~ array_size - 1 범위의 자연수로 바꿔주는 함수"""
    temp = a * key # a와 key를 곱한다
    temp = temp - int(temp) # a와 key를 곱한 값의 소숫점 오른쪽 부분만 저장한다
    
    return int(array_size * temp) # temp와 배열 크기를 곱한 수의 자연수 부분만 리턴한다
        

print(hash_function_multiplication(40, 200, 0.61426212))
print(hash_function_multiplication(120, 200, 0.61426212))
print(hash_function_multiplication(788, 200, 0.61426212))
print(hash_function_multiplication(2307, 200, 0.61426212))

114
142
7
20

 

정리

 

나누기 방법과 곱셈 방법은 해시 함수로 사용할 수 있는 가장 간단한 두 예시였는데요. 사실 key를 받아서 원하는 범위의 자연수를 리턴하면서:

1. 결정론적이어야 된다.
2. 원하는 범위의 자연수 하나하나가 리턴될 확률이 최대한 비슷해야 된다.
3. 빨리 계산을 할 수 있어야 된다.

이 세 조건을 만족하는 아무 함수나 만들면 해시 함수로 이용할 수 있습니다.

 

출처 코드잇