[자료구조] 해싱 VS 이중해싱

해싱(Hashing)과 이중 해싱(Double Hashing) 기술을 사용하여 데이터를 삽입하는 방법에 대해 설명하겠습니다. 해싱과 이중 해싱의 기본 원리와 함께, 실제로 어떤 결과가 나올 수 있는지 살펴보겠습니다.

해싱(Hashing)

해싱은 키를 고정된 크기의 해시 값으로 변환하여 데이터를 저장하는 방법입니다. 해시 함수는 키를 해시 테이블의 인덱스 값으로 변환합니다.

기본 해싱 과정

1. 해시 함수 선택: h(k)를 해시 함수라고 하고, 입력 키 k를 해시 테이블의 인덱스 i로 변환합니다.
2. 충돌 해결: 두 개 이상의 키가 동일한 해시 값을 가질 때, 충돌이 발생합니다. 충돌을 해결하기 위해 여러 방법을 사용할 수 있습니다(예: 개방 주소법, 체이닝 등).

이중 해싱(Double Hashing)

이중 해싱은 개방 주소법의 일종으로, 첫 번째 해시 함수에서 충돌이 발생하면 두 번째 해시 함수를 사용하여 새로운 위치를 찾는 방법입니다.

이중 해싱 과정

1. 해시 함수:
   • 첫 번째 해시 함수: h1(k) = (k % m) - 주 해시 함수로 테이블의 인덱스를 결정합니다.
   • 두 번째 해시 함수: h2(k) = 1 + (k % (m - 1)) - 충돌 해결을 위한 추가 해시 함수입니다.
2. 위치 계산: 키 k를 삽입할 위치를 찾기 위해, 두 해시 함수를 사용하여 위치를 계산합니다.
   • 초기 인덱스: i0 = h1(k)
   • 충돌이 발생한 경우, i = (i0 + j * h2(k)) % m - 여기서 j는 재해시 시도 횟수입니다.

예제

가정:

• 해시 테이블의 크기(m)는 10입니다.
• 두 개의 해시 함수는 다음과 같습니다:
  • 첫 번째 해시 함수: h1(k) = k % 10
  • 두 번째 해시 함수: h2(k) = 1 + (k % 9)

예제 데이터 삽입

• 삽입할 데이터 키: 15, 25, 35

1. 데이터 15 삽입:

• h1(15) = 15 % 10 = 5
• h2(15) = 1 + (15 % 9) = 1 + 6 = 7
• 테이블의 5번 인덱스에 15 삽입.

2. 데이터 25 삽입:

• h1(25) = 25 % 10 = 5
• h2(25) = 1 + (25 % 9) = 1 + 7 = 8
• 5번 인덱스에 충돌 발생.
• 새로운 위치 계산: i = (5 + 1 * 8) % 10 = 13 % 10 = 3
• 테이블의 3번 인덱스에 25 삽입.

3. 데이터 35 삽입:

• h1(35) = 35 % 10 = 5
• h2(35) = 1 + (35 % 9) = 1 + 8 = 9
• 5번 인덱스에 충돌 발생.
• 새로운 위치 계산: i = (5 + 1 * 9) % 10 = 14 % 10 = 4
• 테이블의 4번 인덱스에 35 삽입.

결과

테이블에 데이터가 삽입된 결과는 다음과 같습니다:

인덱스데이터

0
1
2
3	25
4	35
5	15
6
7
8
9

요약

• 해싱은 데이터 삽입을 위해 주어진 키를 해시 함수로 변환하여 인덱스를 결정합니다.
• 이중 해싱은 충돌 시 두 번째 해시 함수를 사용하여 새로운 인덱스를 계산하고 충돌을 해결합니다.

실제 해시 함수와 충돌 해결 방식은 다양한 방법이 있으며, 구체적인 해시 함수의 설계와 충돌 처리 방법에 따라 결과가 달라질 수 있습니다.