오픈 주소법

지난 글 : [알고리즘/Do it 알고리즘] - 체인법

 

오픈 주소법

어제 배운 체인법과는 다른 해시법인 오픈 주소법(open addressing)은 충돌이 발생했을 때 재해시(rehashing)를 수행해 비어 있는 버킷을 찾아내는 방법으로, 닫힌 해시법(closed hashing)이라고도 한다. 요소의 검색, 삽입, 삭제 과정을 알아보자.

 

요소 삽입

새로운 값(18)을 삽입하고자 할 때 충돌이 발생한 경우(해시값 5에 5가 들어있는 경우) 사용하는 방법이 재해시다. 재해시할 때 해시 메서드는 자유롭게 결정할 수 있다. 예로 키값에 1을 더한 값을 요솟수로 나눈 나머지가 있다. 하지만 재해시를 한 번 수행했는데도 또 다시 충돌이 발생한다면 한 번 더 재해시를 할 수 있다. 이렇게 오픈 주소법은 빈 버킷을 만날 때까지 재해시를 여러 번 반복하므로 선형탐사법(linear probing)이라고도 한다.

 

요소 삭제

인덱스가5인 값(5)을 삭제하는 경우다. 인덱스가 5인 버킷의 데이터를 그냥 비우면 되는 것이 아니다. 인덱스가 5인 버킷을 그냥 비워 두면 해시값이 같은 값을 검색할 때 '해시값이 5인 데이터는 존재하지 않는다'라고 생각해 검색에 실패하기 때문이다. 그래서 각 버킷에 아래 속성 중 하나를 부여한다.

1. 데이터 저장
2. 비어 있음 속성값(-)
3. 삭제 마침 속성값(★)

table에서 버킷이 비어 있는 상태를 '-'로, 삭제를 마친 상태를 '★'로 나타낸다.

 

요소 검색

버킷 수가 13개인 table에서 값 17을 검색하는데, 해시값이 4인 버킷이 비어 있는 경우(table에 17이 없는 경우) 검색 실패다. 이제 18을 검색하는 경우다. 해시값이 5인 버킷은 위에서 삭제를 진행 했기에 속성은 '삭제 마침(★)'이다. 그래서 요소 삽입 때처럼 재해시를 수행해 버킷을 다시 검색한다. 이때, 해시값이 6인 버킷에도 값이 저장돼 있다면 다시 재해시를 수행해 해시값이 7인 버킷을 검색한다. 검색하는 값이 저장되어 있다면 검색 성공이다.

 

아래는 오픈 주소법으로 구현한 클래스 OpenHash<K, V>다.

 

아래는 오픈 주소법을 사용하는 프로그램이다. 해시에 저장하는 데이터의 클래스인 Data 자료형은 어제 배운 체인법과 같다.

참고 서적 :