Hash 함수 및 충돌 처리

해시 구조는 데이터 값(키)이 들어오면, "해시 함수"를 통해 변환된 값을 기반으로 버킷에 넣어주는 구조를 가진다.

이때, 해시 함수가 변환한 값이 최대한 중복되지 않도록 (해시 충돌이 적게 발생하도록) 하는 것이 중요하다.

1. 해시 함수

공식 : h(x) = x mod k

가장 기본적인 해시 함수로 나눗셈법을 이용한 함수가 있다.
"키"를 소수로 나눈 나머지를 활용하는 방식이다.
이때, 소수를 사용하는 이유는 충돌을 줄일 수 있기 때문이다.
- 예시) x = 3, 6, 9, 12, 15, 18, ... (3의 배수)
- 15라는 수로 나눈 경우
  - 3 ~ 15 까지의 수는 각각 3, 6, 9, 12, 0 에 해당하는 버킷에 들어가게 된다.
  - 그러나, 이후의 값(18 ~)에 있어서 3, 6, 9, 12, 0 이 반복되어서 나오기 때문에
  - 충돌이 많이 발생하게 된다.
- 7이라는 소수로 나눈 경우
  - 3 ~ 21 까지 중복되는 값이 없으므로
  - 소수를 사용하지 않은 경우보다 충돌이 적게 발생한다.
이유를 생각해보면
- N의 약수 중 하나를 M이라고 할 때
- 임의의 수 K에 대해 M*K = N이 되는 수가 존재한다. (위 예시에서 N=15, M=3, K=5)
- 그 결과 K주기마다 같은 값이 반복된다.
- 그러므로 K 값이 소수라면 1과 K만이 존재하기 때문에, 충돌을 줄일 수 있다 (K=17이면 주기가 17이 될 것이다)
결론
- 위에서 언급한 대로 K라는 소수를 이용한 나눗셈법을 이용하면,
- 해시 테이블의 크기는 0 ~ K-1 (최대 버킷 인덱스 = K-1) 이 될 것이다.
- K가 큰 소수라면 더욱 많은 데이터를 저장할 수는 있지만, 큰 소수를 구하는 일이 어렵다는 것이 나눗셈법의 단점이다.

공식 : h(x) = (((x*A) mod 1) * m)

m : 최대 버킷의 개수 / A : 황금비 (1.6180339887...)

동작 방식
- 키에 황금비를 곱하고
- 소수 부분만 취하기
- 이후 소수 부분만 남은 값에 m을 곱해서
- 정수부분만 취하여 버킷에 넣기 (최대 버킷 인덱스 : m - 1)

앞에 사용한 방식들은 키값이 숫자일 때 사용한 방식이고, 해당 방식은 키의 자료형이 문자열일 때 사용하는 방식이다.

공식 : hash(s) = (s[0] + s[1]*p + s[2]*p^2 + ... + s[n-1]*p^(n-1)) mod m

위 공식은 polynomial rolling method 이다.
- p는 31을 사용한다. 31은 홀수이면서 메르센 소수이기 때문
- 메르센 소수는 해시 충돌을 줄여주는 수
동작 방식 ("apple" 문자열)
- 알파벳을 a ~ z 까지 1 ~ 26 로 매치표에 등록
- "a" 는 매치표에서 1에 해당
  - s[0] * p^0 = 1 * 1 = 1
- "p"는 매치표에서 16에 해당
  - s[1] * p^1 = 16 * 31 = 496
- 이렇게 모든 문자열을 지나 값들을 더한 결과는 4,990,970 이고 이 수를 m으로 나눠서 저장하기
이 방식의 단점은 문자열의 크기에 비해 해시 함수를 통과한 결과가 너무 크다는 점이다.
이 방식은 모듈러 연산을 통해 개선할 수 있다.

개선된 문자열 해시 함수

여기서 사용하는 테크닉은 모듈러 연산을 통해 오버플로를 방지하는 방식이다.
예를 들어,
- (a + b) % c = (a % c + b % c) % c
- 위 식을 보면, 두 식의 결과는 같지만 오른쪽 방식이 중간 연산에 있어서 오버플로를 방지해 준다.
수정된 해시 함수

hash(s) = (s[0]%m + s[1]*p%m + s[2]*p^2%m + ... + s[n-1]*(p^(n-1))%m) % m

서로 다른 키가 해시 함수를 거쳐 같은 값이 나왔다면, 충돌 처리를 해주어야 한다.

충돌이 발생한 경우, 링크드 리스트를 통해 같은 해시값을 가지는 데이터를 뒤에 이어서 저장하는 방식이다.

충돌한 값이 생기면, 빈 버킷을 찾아서 충돌한 값을 넣어주는 방식

해시 테이블을 최대한 활용한다는 이점이 있다.

2 - 2 - 1. 선형 탐사 방식

해시 값이 충돌한 경우 일정한 간격(대체로 1)으로 이동하면서 빈 버킷을 찾는 방식
h(k,i) = (h(k) + i) mod m
- h(k) : 해시 함수 결과값
- i : 일정한 간격 (대체로 1)
- m : 최대 버킷의 크기 (모듈러 연산을 통해 최대 크기 벗어나는 것 방지)

2 - 2 - 2. 이중 해싱 방식