오늘은 해시 테이블과 함수를 잘 선택하여 오버플로우가 발생하지 않도록 하는 방법을 알아보고자 합니다.

개요

최선으로 오버플로우가 발생하지 않고, 발생한다면 효율적으로 처리하는 방식을 채택해야 합니다.

해결하는 방식에는 충돌이 일어나 키값을 다른 빈 버킷을 찾아 저장하는 선형 개방 주소법과 여러개의 항목을 저장할 수 있도록 해시 테이블 구조를 변경하는 체이닝 방식이 있습니다.

• 선형 개방 주소법

선형 개방 주소법은 해시 함수로 구한 버킷에 빈 슬롯이 없어 오버플로우가 발생하면 그 다음 인덱스에 빈 슬롯이 있는지 조사하여, 빈 슬롯이 있다면 저장하고 없으면 또 다음 인덱스에 비어있는지 조사합니다.

이를 반복하며 해시 테이블의 비어있는 슬롯을 순차적으로 찾아서 사용하게 됩니다.

이 방식은 배열에서 구현가능 합니다.

• 체이닝

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

버킷에 슬롯을 동적으로 삽입하며 삭제하기 위해서는 링크드 리스트를 사용합니다.

각각의 버킷에 대한 헤드 노드는 배열로 만들고, 버킷의 슬롯은 링크드 리스트로 만듭니다.

충돌이 발생하면 해당 버킷의 다음 링크드 리스트를 만들어 저장하면 됩니다.

버킷안에서 원하는 슬롯을 검색하기 위해서는 링크드 리스트를 선형 탐색해야 합니다.