자료 구조 - 해싱 (오버 플로우 처리 방법)

1. 오버 플로우 처리 방법

1) 오버 플로우 처리

• 해시 테이블과 해싱 함수를 잘 선택하여 오버플로우가 발생하지 않도록 함

(1) 오버플로우 발생시 처리 방법

(1-1) 선형 개방 주소법

• 충돌이 일어난 킷값을 다른 비어잇는 버킷을 찾아 저장

(1-2) 체이닝

• 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경하는 방법

2) 선형 개방 주소법 (선형 조사법)

(1) 해싱 함수로 구한 버킷에 빈 슬롯이 없어 오버플로우가 발생하면

• 그 다음 버킷에 빈 슬롯이 있는지 조사함
• 빈 슬롯이 있으면 - 키 값을 저장
• 빈 슬로이 없으면 - 다시 그 다음 버킷을 조사
• 이런 과정을 되풀이 하면서 해시 테이블 내에 비어있는 슬롯을 순차적으로 찾아서 사용하여 오버 플로우 문제를 처리

(2) 오버플로우 처리 예제

• 해시 테이블의 크기 : 5
• 해시 함수 : 제산함수 사용, 해시 함수 h(k) = k mod 5

  저장할 키 값 : {45, 9, 10, 96, 25}

• 키 값 45 저장 : h(45) = 45 mod 5 = 0 => 해시 테이블 0번에 45 저장
• 키 값 9 저장 : h(9) = 9 mod 5 = 4 => 해시 테이블 4번에 9 저장
• 키 값 10 저장 : h(10) = 10 mod 5 = 0 => 충돌 발생
  • 다음 버킷중에서 비어있는 버킷 1에 10 저장

• 키 값 96 저장 : h(96) = 96 mod 5 = 1 => 충돌 발생
  • 다음 버킷 중에서 비어있는 버킷 2에 96저장
• 키 값 25 저장 : h(25) = 25 mod 5 = 0 => 충돌 발생
  • 다음 버킷중에서 비어있는 버킷 3에 25 저장

3) 체이닝

• 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키 값을 저장할 수 있도록 하는 방법

(1) 버킷에 슬롯을 동적 삽입하고 삭제하기 위해서 연결 리스트 사용

• 각 버킷에 대한 헤드노드를 1차원 배열로 만들고
• 각 버킷에 대한 헤드노드는 슬롯들을 연결 리스트로 가지고 있어서 슬롯의 삽입이나 삭제 연산을 쉽게 수행 할 수가 있음
• 버킷 내에서 원하는 슬롯을 검색하기 위해서는 버킷의 연결 리스트를 선형 검색함

(2) 예제

• 해시 테이블의 크기 : 5
• 해시 함수 : 제산 함수 사용, 해시 함수 h(k) = k mod 5

  저장할 키 값 : {45, 9, 10, 96, 25}

• 키 값 45 저장 : h(45) = 45 mod 5 = 0 => 해시 테이블 0번에 45 저장
• 키 값 9 저장 : h(9) = 9 mod 5 = 4 => 해시 테이블 4번에 9 저장

• 키 값 10 저장 : h(10) = 10 mod 5 = 0 => 해시 테이블 0번에 10 저장
• 키 값 96 저장 : h(96) = 96 mod 5 = 1 => 해시 테이블 1번에 96 저장

• 키 값 25 저장 : h(25) = 25 mod 5 = 0 => 해시 테이블 0번에 25 저장