Hashing.md

Hashing(해싱)

작성자

해싱?

• 해시테이블(HashTable) : 키 값의 연산에 의해 직접 접근이 가능한 구조
• 해싱(Hashing) : 해시테이블을 이용한 탐색
• 사전과 같은 자료 구조를 구현할 때에 최상의 선택
• 이론상 O(1)의 시간 안에 탐색을 끝마칠 수 있다.

해시 함수

• 키 값을 해시 테이블의 주소로 변환하는 함수

좋은 해시 함수의 조건

1. 충돌이 적어야 한다.
2. 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
3. 계산이 빨라야 한다.

해시 함수의 종류

1. 제산 함수

   • 나머지 연산자를 사용하여 탐색 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법
   • h(x) = x mod M

2. 폴딩 함수

   • 탐색 키를 여러 부분으로 나누어 모두 더한 값을 해시 주소로 사용하는 방법
   • 이동 폴딩과 경계 폴딩이 대표적인 방법이다.

3. 중간 제곱 함수

   • 탐색 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성하여 사용하는 방법
   • 서로 다른 탐색 키는 몇 개의 문자가 같을지라도 서로 다른 해싱 주소를 갖게 된다.

4. 비트 추출 방법

   • 해시 테이블의 크기가 M=2^k일 때 탐색 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 방법

5. 숫자 분석 방법

   • 숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용한 방법
   • 키의 각각의 위치에 있는 숫자 중에서 편중되지 않은 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법

해시함수의 충돌과 해결책

충돌

• 서로 다른 탐색 키를 갖는 항목들이 같은 해시 주소를 가지는 현상
• 충돌이 발생하면 해시 테이블에 항목을 저장하는 것이 불가능해진다.

해결책

1. 선형 조사법

   • 충돌이 일어난 바로 뒤를 보는 방법이다.
   • i번째 해시 함수는 h(x)로 부터 i만큼 떨어진 자리가 된다.
   • h(k), h(k)+1, h(k)+2 ... 순으로 조사하게 된다.

2. 이차 조사법

   • 선형 조사법과 유사하지만 다음 조사할 위치를 이차 함수에 의하여 결정하는 방법이다.
   • h(k), h(k)+1, h(k)+4, h(k)+9 ... 순으로 조사하게 된다.

3. 이중 해싱법

   • 다음 조사할 위치를 현재 해시함수가 아닌 다른 별개의 해시함수를 이용하는 방법이다.
   • 두개의 해시 함수를 h(x)= x mod m, m보다 작은 소수 m'에 대해 f(x)= 1+(x mod m')으로 잡아서 사용한다.

4. 체이닝

   • 충돌 문제를 연결 리스트로 해결하는 방법이다.
   • 각 버켓에 삽입과 삭제가 용이한 연결 리스트를 할당한다.
   • 효율성을 위해서 연결리스트 맨 앞에 삽입을 한다. 맨뒤에 넣으면 삽입때마다 맨 뒤로 이동해야 하기 때문이다.
   • 탐색과 삭제 같은 경우는 연결리스트 방식과 동일하게 진행된다.

기타

• C++ STL중 unordered_map이 해시 테이블로 구현되어있다.
• SHA(Secure Hash Algorithm) : 1993년부터 미국 NSA가 제작하고 미국 국립표준기술연구소(NIST)에서 표준으로 제작한 해시 암호 알고리즘
• 라빈 카프 알고리즘이 해싱에 기반하고 있다.

참조

• C언어로 쉽게 풀어쓴 자료구조 개정판. 천인국, 공용해 공저