[코테] 해시

해시

해시 함수

해시함수는 특정한 Key를 입력받으면 적절한 해시값(Index)을 반환하는 함수이다. 해시 함수를 이용하면 인덱스에 키 정보를 저장할 수 있다. 키를 입력받으면 해시 함수를 적용하여 인덱스를 바로 구하고 인덱스로 접근하면 O(1) 시간에 값을 얻을 수 있다.

해시함수는 KEY의 개수가 n개 라면 해시값은 0 ~ n-1 사이 값을 내야한다. 이때 KEY값에 따라 동일한 해시값이 나올 수 도있는데 이것을 해시충돌이라고 한다. 이러한 해시충돌이 적을수록 좋은 해시함수라고 할 수 있다.

해시 함수 - 나눗셈 법

h(x) = x mod k (x는 키, k는 소수)

k로 나눈 나머지는 무조건 0 ~ k - 1이기 때문에 해시 함수라고 할 수 있다. (k가 클수록 충돌이 적음)

해시 함수 - 곱셈 법

h(x) = (((x*A) mod 1) * m) (x는 키, A는 황금 비, m은 최대 버킷의 갯수

x * A를 정수 부분과 소수 부분으로 나누면 소수 부분의 범위는 [0,1)이다. 여기에 m을 곱하게 되면 [0, m) 범위의 해시 값을 얻을 수 있다.

해시 충돌

서로 다른 키에 대한 해시 값이 같을 경우 충돌이 발생했다고 한다. 이러한 해시 충돌을 처리하기 위해 체이닝, 개방 주소법, 등을 쓸 수 있다.

해시 충돌 - 체이닝

충돌 발생 시 버킷에 링크드리스트로 데이터를 연결한다. 최악의 경우 특정 테이블에 모든 해시값이 몰린다면 탐색에 O(n)의 시간이 걸린다.

해시 충돌 - 개방 주소법

충돌 발생 시 다른 빈 버킷을 찾아서 충돌값을 삽입한다. 개방 주소법을 사용하면 메모리를 아낄 수 있다. 이를 확장하여 두 개의 해시 함수를 사용하는 이중 해싱을 사용할 수 있다. 이중 해싱은 첫 번째 해시 함수에서 충돌이 발생하면 두 번째 해시 함수를 적용하여 새로운 버킷을 찾는 것이다.

해시를 사용해야 하는 문제

• 키-값 쌍으로 연관된 데이터가 존재하고 해당 값에 대한 접근이 빈번한 경우 (사전)
• 중복되지 않는 키를 사용하는 경우 (학번, 주소)

해시를 사용하지 말아야 하는 경우

• 특정 키에 여러 가지 값을 매칭해야 하는 경우