(데이터베이스) 해시 테이블(Hash Table)의 오버플로우 처리기법

해싱 테이블의 오버플로우 처리기법

개방주소법

• 해시 충돌(collision)이 일어나면 다른 버켓에 데이터를 삽입 하는 방식
• 대표적으로 선형 탐색(Linear Probing), 제곱 탐색(Quadratic Probing), 이중 해시(Double Hashing)이 있음

• 선형 탐색 : 해시 충돌 시 다음 버켓, 혹은 몇 개를 건너 뛰어 데이터를 삽입
• 제곱 탐색 : 해시 충돌 시 제곱 만큼 건너 뛴 버켓에 데이터를 삽입 (1, 4, 9, 16 ...)
• 이중 해시 : 해시 충돌 시 다른 해시 함수를 한 번 더 적용한 결과를 이용

폐쇄 주소법

• 충돌이 일어난 레코드들을 별도의 오버플로우 영역에 저장하고 chain(pointer)으로 홈 버킷에 연결하는 방법
• 해시 테이블 내의 빈자리에 보관하는 direct chaining, 해시 테이블과는 별도의 기억공간에 보관하는 indiret chaining이 있음

재해싱

• 해시 충돌 시 새로운 해싱 함수로 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱