[4주차]8장 해시

해시는 해시 함수를 통해 변환한 값을 인덱스처럼 사용하고, 키와 값을 저장하여 데이터 탐색을 빠르게 할 수 있다. 

해시는 키를 사용해서 데이터 탐색을 빠르게 한다. 

 

값을 검색하기 위해서 활용하는 것은 키고, 키를 통해 해시값이나 인덱스로 변환할 때는 해시 함수를 통한다. 이때, 해시 함수는 키를 일정한 해시 값으로 변환 시킨다. 

 

해시의 특징

1. 해시는 키를 통해 값을 찾을 수 있지만, 값을 통해 키를 찾을 수는 없다. 

2. 키 자체가 해시함수를 통해 값이 포함된 인덱스이므로 값을 찾기 위한 과정이 필요 없다. 따라서 탐색은 O(1)의 시간복잡도가 걸린다. 

3. 값을 인덱스로 활용하기 위해서는 적절한 변환 과정을 거쳐야 한다. 

 

해시 테이블은 키와 대응한 값이 저장되어 있는 공간이고, 해시 테이블의 각 데이터를 버킷이라고 한다. 

 

해시 함수

해시 함수 구현시 고려 사항

1. 해시 함수를 통한 결과는 해시 테이블의 크기인 0~(N-1) 사이의 값을 내야한다. 

2. 해시 함수가 변환한 값의 충돌(중복 발생)은 최대한 작은 확률로 일어나게끔 해야한다.  (충돌 발생은 불가피함)

 

자주 사용하는 해시 함수

나눗셈법

나눗셈법에 소수가 아닌 수를 사용하면 충돌이 많이 발생한다. 

따라서 나눗셈법의 해시 테이블의 크기는 소수를 사용해야한다. 

이렇게 하면, 나눗셈법의 해시 테이블 크기는 K가 된다.

왜냐하면 K에 대해 나머지 연산(모듈러 연산)을 했을 때, 나올 수 있는 값은 0 ~ (K - 1)이기 때문이다. 

그러나, 매우 큰 소수를 구하는 방법 중 효율적인 방법은 없다는 점이 단점이다. 

 

곱셈법

곱셈법도 나눗셈법 처럼 모듈러 연산을 활용하지만 소수는 사용하지 않는다. 

 

곱셈법의 공식 

 

 h(x) = ((( x * A ) mod 1 ) * m)

 

 

m은 최대 버킷의 개수, A는 황금비이고 무한소수이지만, 소수부의 일부인 0.6183만 이용한다. 

 

1. 키에 황금비를 곱한다. 

2. 1번 결과에 모듈러 1을 취한 후, 소수 부분만 취한다. 

3. 2번 결과 값에 테이블 크기 m을 곱한다. 

 

3번 결과를 통해 테이블의 인덱스인 0 ~ (m - 1)에 매치할 수 있다. 

 

곱셈법은 소수가 필요없고, 테이블의 크기가 커져도 추가 작업이 필요없다. 

 

문자열 해싱

키의 자료형이 문자열일 때, 문자열을 해싱하는 방법은 다음과 같다. 

문자열의 문자를 숫자로 변환해준 후, 테이블의 인덱스에 매칭될만한 값으로 숫자를 다듬어주면 된다. 

 

문자열을 해싱하기 위해 사용하는 다항식 rolling method이다. 

 

 

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

 

문자열의 문자를 숫자로 변환해준 후, 테이블의 인덱스에 매칭될 만한 값으로 숫자를 다듬어 줄 때, 

중간 중간에 모듈러 연산을 한 후 더한값에 대해 모듈러 연산을 하게되면 오버플로우를 최대한 방지할 수 있다. 

 

*** 일반적인 수식에도 모듈러 연산이 있는 문제중에서 큰 수를 다루는 문제는 오버플로우를 어떻게 처리하는지 확인하는 함정이 있으니, 유의해야한다. 

 

충돌 처리

해시 테이블은 충돌 발생이 불가피 하므로, 반드시 충돌 처리를 해줘야한다. 

 

체이닝

충돌 처리는 체이닝으로 처리할 수 있다. 

체이닝은 해싱한 값중 중복값이 나올 경우, 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결하는 방법이

다.

 

그러나 이 방법에는 두가지 단점이 존재한다. 

 

1. 충돌이 많아질 경우, 링크드리스트의 길이가 길어지고 사용하지 않은 해시 테이블의 공간은 덜사용하게 되므로 공간 활용성이 떨어진다. 

2. 충돌이 많아질 경우, 링크드리스트의 한계로 인해 검색 성능이 떨어진다. 

왜냐하면, 링크드리스트로 검색할때 맨 처음부터 검색하기 때문이다. 

최악의 경우, O(N)의 시간복잡도가 발생할 수 있다. 

 

 

개방 주소법

이를 개방 주소법으로 개선할 수 있다. 
개방 주소법은 체이닝과 달리, 빈 버킷을 찾아서 충돌값을 삽입한다. 

이 방법은 체이닝보다 메모리를 더 효율적으로 사용하는 방법이다. 

 

개방 주소법 중 하나로 선형 탐사 방식이 있다. 

이 방식은 충돌발생 시 다른 빈 버킷을 찾을 때 까지 일정한 간격으로 이동한다. 

 

h(k, i) = (h(k) + i) mod m

 

*보통 간격은 1로 한다

 

단, 이 방법에도 단점이 있다. 

충돌 발생 시 한 칸씩 이동하며 해시 테이블의 빈 곳을 찾아서 값을 넣을 경우, 해시 충돌이 발생한 값끼리 모이는 영역이 발생한다. 이를 클러스터를 형성한다고 한다. 이런 영역이 발생하면 해시값이 충돌할 확률이 더 높아진다. 

 

 

이를 개선하기 위해 이중 해시 방식이 있다. 

이 방식은 해시 함수를 2개 사용하는 방식이다.  N개로도 늘려서 사용할 수 있다. 

첫번째 해시 함수는 기존 해시 함수의 역할을 수행하고, 두번째 해시 함수의 역할은 첫 번째 해시 함수의 결과로 충돌이 발생하면, 해당 위치를 기준으로 위치를 어디로 정할지 새로 결정하는 역할을 한다. 

 

*h1은 1차 해시함수, h2는 2차 해시함수이다. 

 

h(k,i) = (h1(k) + i * h2(k)) mod m

 

수식을 보면 선형 탐사 방식과 비슷하지만 클러스터를 줄이기 위해, m을 제곱수나 소수로 한다. 

 

 

 

---

 

실제 코테 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정이다. 

특정 값이나 정보를 기준으로 자주 검색하거나 특정 값과 매핑 값의 관계를 확인해야 하는 작업이 문제에 포함되면 해시를 고려해봐야 한다.