정적인 해싱

정적인 해싱(Static Hashing)은 해시 테이블을 사용하여 데이터를 저장하고 검색하는 방법 중 하나로, 해시 함수와 고정된 해시 테이블 크기를 사용하는 기법입니다. 정적인 해싱은 데이터를 특정 위치에 매핑하여 빠르게 검색할 수 있도록 해주지만, 데이터의 양이 변할 때 유연성의 제한이 있을 수 있습니다.

1. 정적인 해싱의 기본 개념

정적인 해싱은 데이터가 해시 함수에 의해 특정 버킷(혹은 슬롯)에 매핑되는 방식입니다. 해시 함수는 입력 값을 해시 값으로 변환하여 데이터의 저장 위치를 결정합니다. 이 저장 위치는 고정된 크기의 해시 테이블에서 설정됩니다.

2. 정적인 해싱의 구조

• 해시 함수: 데이터를 해시 테이블의 인덱스 위치로 변환하는 함수입니다. 예를 들어, 키 kkk를 해시 테이블의 크기 MMM으로 나눈 나머지를 계산하여 인덱스를 얻습니다:해시 인덱스=해시 함수(k)=kmod  M\text{해시 인덱스} = \text{해시 함수}(k) = k \mod M해시 인덱스=해시 함수(k)=kmodM
• 해시 테이블: 고정된 크기의 배열로, 각 인덱스는 데이터 항목이 저장될 수 있는 버킷입니다. 데이터는 해시 함수에 의해 계산된 인덱스에 위치하게 됩니다.
• 버킷: 해시 테이블의 각 인덱스 위치를 나타내며, 하나 이상의 데이터를 저장할 수 있는 공간입니다. 충돌 해결 방법을 통해 같은 인덱스에 여러 데이터를 저장할 수 있습니다.

3. 해싱 충돌 해결

정적인 해싱에서는 충돌(두 개 이상의 데이터가 같은 해시 인덱스를 가지는 경우)을 해결하기 위해 여러 방법을 사용합니다:

• 체이닝(Chaining): 각 버킷이 연결 리스트를 포함하도록 하여, 충돌이 발생할 경우 리스트에 추가로 데이터를 저장합니다.
  • 데이터 23과 43이 모두 해시 함수에 의해 인덱스 3으로 매핑되면, 인덱스 3의 버킷에 연결 리스트가 형성되어 23과 43이 순서대로 저장됩니다.
• 예제:
• 오픈 어드레싱(Open Addressing): 충돌이 발생할 경우, 다른 버킷을 찾아서 데이터를 저장합니다. 이 방법에는 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 포함됩니다.
  • 데이터 23이 해시 인덱스 3으로 매핑되고, 인덱스 3이 이미 사용 중일 경우, 선형 탐사 방법으로 인덱스 4, 5, ... 를 차례로 검사하여 빈 버킷을 찾습니다.
• 예제:

4. 정적인 해싱의 장점과 단점

4.1 장점

• 단순성: 구현이 간단하고 이해하기 쉬워서 기본적인 해시 테이블의 구조를 쉽게 구축할 수 있습니다.
• 빠른 검색: 해시 함수에 의해 직접 접근이 가능하므로 평균적인 검색 시간 복잡도가 O(1)입니다.

4.2 단점

• 제한된 크기: 해시 테이블의 크기가 고정되어 있기 때문에, 데이터 양의 변화에 유연하지 못합니다. 데이터가 많아지면 충돌이 증가하고, 테이블이 포화 상태에 가까워지면 성능이 저하될 수 있습니다.
• 스페이스 낭비: 고정된 크기의 해시 테이블에 비해 데이터가 적을 경우 메모리의 일부가 낭비될 수 있습니다.
• 충돌 문제: 데이터가 많아지면 충돌이 증가하여, 충돌 해결 방법에 따라 성능이 저하될 수 있습니다.

5. 정적인 해싱의 예제

예제: 학생 ID를 해시 키로 사용하는 학생 데이터베이스

• 데이터: 학생 ID, 이름
• 해시 함수: 학생 ID mod\text{mod}mod 해시 테이블 크기 (예: 100)
• 해시 테이블: 크기가 10인 해시 테이블을 사용한다고 가정합니다.
  • 학생 ID 103이 해시 함수에 의해 인덱스 3으로 매핑되면, 인덱스 3에 학생 정보를 저장합니다.
  • 학생 ID 113이 인덱스 3으로 매핑되면, 체이닝을 통해 인덱스 3의 연결 리스트에 추가됩니다.

요약

정적인 해싱은 고정된 크기의 해시 테이블과 해시 함수를 사용하여 데이터를 효율적으로 저장하고 검색하는 방법입니다. 해시 함수는 데이터를 특정 인덱스로 매핑하고, 충돌 발생 시 체이닝이나 오픈 어드레싱 등의 방법으로 해결합니다. 정적인 해싱은 구현이 간단하고 검색 속도가 빠르지만, 데이터 양에 대한 유연성이 부족하고 충돌 문제가 발생할 수 있습니다.

 

 

4o mini