1. 해싱

해싱이란?

임의의 길이를 가진 키(key)에 산술 연산을 적용해(해시함수)
고정된 길이의 주소(인덱스)를 알아내고
해당 주소로 해시 테이블에서 데이터를 조회하거나 저장하는 기법이다.

2. 충돌

해싱에서 충돌이란?

대체로 해시 테이블의 버킷 수는 모든 키의 경우의 수보다 작다.
따라서 여러 개의 서로 다른 키가 해시 함수에 의해 같은 해시 주소로 사상될 수 있다.
이 경우를 충돌이라고 한다.

3. 오버플로우

해싱에서 오버플로우란?

충돌이 버킷에 할당된 슬롯 수보다 많으면, 버킷에 더이상 저장할 수 없게 된다.
이것이 오버플로우다.

4. 해시테이블 크기

해시 테이블 크기가 소수이어야 하는 이유는?

해시 테이블의 크기가 소수이면 해시 함수의 결과가 고르게 분포되므로 충돌의 가능성을 줄일 수 있다.

5. 클러스터링

클러스터링이란?

해싱에서 클러스터링이란 충돌로 인해 해시 테이블의 연속된 슬롯이 채워지는 현상을 말한다.

클러스터링은 왜 문제가 될까?

새로운 키가 들어올 때 구간의 앞부분부터 순차적으로 빈 슬롯이 있는지 조사해야 한다.
즉 연속한 슬롯을 탐색하기 위해 접속 횟수가 증가한다.
탐색/삭제/삽입 속도가 느려진다.

6. 해시함시

해시함수란?

키값을 입력으로 받고 산술연산을 적용해 고정된 길이의 주소를 리턴하는 함수이다.
해시 함수가 잘 설계되어 있어야 탐색의 효율이 높아진다.

7. 해시 함수 종류

1. 제산 함수

• 가장 간단한 해시 함수
• 나머지 연산을 사용하여 키를 해시 테이블의 크기로 아눈 나머지를 해시 주소로 사용하는 연산
• key mod (해시 테이블 크기)

2. 폴딩 함수

• 키를 몇개의 부분으로 나누고 이를 더해서 비트별로 XOR같은 부울 연산을 하여 계산하는 함수
• 사용되는 경우: 키가 해시테이블의 크기보다 더 큰 정수일 경우
• 종류
  • 이동 폴딩: 키를 여러 부분으로 나눈 값을 더해서 해시 주소로 사용
  • 경계 폴딩: 키를 여러 부분으로 나누고 키의 이웃한 부분을 거꾸로 더해서 해시 주소로 사용
• 키를 해시 테이블의 크기만큼 부분으로 나누고 분할된 부분을 합해서 해시 주소를 만듦
  • 예시:
    탐색키: 12320324111220
    이동 폴딩: 123 | 203 | 241 | 112 | 20 = 699
    경계 폴딩: 123 | 302 | 241 | 211 | 20 = 897

3. 중간 제곱 함수

• 키를 제곱한 다음 중간의 몇 비트를 사용해 해시 주소를 생성함

4. 비트 추출 방법

• 해시 테이블의 크기기를 2^k라고 할 때,임의의 위치의 k개 비트를 사용해 해시 주소로 사용함
• 키의 일부분만 사용하므로 연산의 결과가 고르게 분포되지 않을 수 있음

5. 숫자 분석 방법

• 숫자로 구성된 키에서 특정 위치에 있는 수의 특징을 미리 알고 있을 때 유용
• 각각 위치에 있는 숫자 중 편중되지 않는 수를 해시 테이블 크기에 적합하게 조합하여 해시 주소로 사용
• 예시: 20250814 -> 2025년 연도이므로 중복되는 값. 0814만 가지고 해시 주소로 사용

8. 해시 충돌 해결법

1. 체이닝 방법

• 해시 테이블 구조를 변경하여 각 버킷이 하나 이상의 값을 저장할 수 있도록 함
• 체이닝 방법에서는 연결 리스트를 사용해서 버킷에 여러 값을 저장할 수 있게 함
  • 각 버킷에 고정된 슬롯을 할당하지 않고, 버킷에 삽입과 삭제가 용이한 연결 리스트 할당
• 순서
  • 키가 버킷으로 들어오면
  • 동적 메모리 할당으로 새로운 노드를 생성
  • 이 노드에 키를 복사함
  • 버킷에 연결되어 있는 기존의 연결 리스트에 해당 키가 있는지 검사
  • 이미 있으면 -> pass
  • 없으면 -> 마지막 노드에 새로운 노드 연결
• 장점
  • 필요한 만큼만 노드를 만드므로 메모리 사용 효율이 높음
  • 오버플로우가 발생해도 해당 버킷에 할당된 연결 리스트만 처리하면 되어 처리 시간 효율 높음

2. 개방주소법

1. 선형 조사법

• hash_table[k]에서 충돌이 발생하면, hash_table[k+1]이 비어있는지 확인
• 비어있다면 hash_table[k+1]에 값을 할당
• 장점: 간단
• 단점: 클러스터링이 발생함.

2. 이차 조사법

• 선형 조사법과 유사하지만 충돌 발생 후 다음으로 조사할 위치를 계산하는 방법이 다름
  • 선형 조사법: k -> k+1 -> k+2 -> k+3...
  • 이차 조사법: k -> k+1 -> k+4 -> k+9...
• 장점: 클러스터링 완화
  • 충돌이 발생해도 비연속적인 슬롯이 비어있는지 검사하므로
• 한계: 2차 클러스터링 여전히 발생 가능
  • 동일한 위치로 사상되는 여러 키는 동일한 순서대로 빈 슬롯을 조사할 것이므로

3. 이중 해싱법

• 재해싱 방법으로도 불림
• 충돌이 발생하면 새로운 해시함수를 사용해 주소를 계산함
• 키를 참조해 더하는 값을 다르게 함 -> 키가 다르면 서로 다른 조사 순서를 가짐
• h(k) -> h(k) + step -> h(k) + 2 step -> h(k) + 3step ...
• 예시
  • 8, 1, 9, 6, 13
  • 해시 테이블 크기: 7
  • 1차 해시 함수: k mod 7, 2차 해시 함수: 5 - (k mod 5)
    8 % 7 = 1 -> 저장
    1 % 7 = 1 -> 충돌 => (1 + (5 - (1 mod 5))) mod 7 = 5 mod 7 = 5 -> 저장
    9 % 7 = 2 -> 저장
    6 % 7 = 6 -> 저장
    13 % 7 = 6 -> 충돌 => (6 + (5 - (13 mod 5)) mod 7 = 1 -> 충돌 => (6 + 2 *(5 - (13 mod 5)) mod 7 = 10 mod 7 = 3 -> 저장