Page 452 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

이렇게 재해시를 하면 (18 + 1) % 13의 결과값(6)을 얻을 수 있습니다. 그런데 b 처럼 인덱스

가 6인 버킷도 데이터가 채워져 있으므로 재해시합니다. 그러면 (19 + 1) % 13의 결과값(7)
을 얻을 수 있습니다. 따라서 c 처럼 인덱스가 7인 버킷에 새로운 데이터(18)를 삽입합니다.
이렇게 오픈 주소법은 빈 버킷을 만날 때까지 재해시(rehashing)를 여러 번 반복하므로 연결
탐사법(linear probing)이라고도 합니다.

요소 삭제
이제 c 에서 인덱스가 5인 값을 삭제하는 과정을 살펴보겠습니다. 인덱스가 5인 버킷의 데

이터를 비우면 될 것 같지만 실제로는 그렇지 않습니다. 왜냐하면 같은 해시 값을 갖는 18을
검색할 때 ‘해시 값이 5인 데이터는 존재하지 않는다’라고 생각하여 검색에 실패하기 때문입
니다.

그래서 각 버킷에 대해 아래의 속성을 부여합니다.

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

다음 그림에서는 버킷이 비어 있는 상태를 ‘-’로, 삭제를 마친 상태를 ‘★’로 나타냅니다. 5를
삭제할 때 그림 11-10처럼 그 위치의 버킷에 삭제를 마쳤음을 나타내는 속성값으로 ‘★’을
저장합니다.

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２
－ 14 － 29 － ★ 6 18 34 － 75 37 51

삭제 마침 : 같은 해시 값의 데이터가 다른 버킷에 저장되어 있습니다.
비어 있음 : 같은 해시 값의 데이터가 존재하지 않습니다.
[그림 11-10] 오픈 주소법의 삭제 마침 속성값과 비어 있음 속성값 사용

요소 검색
이어서 값 17을 검색해 보겠습니다. 해시 값이 4인 버킷을 보면 속성값이 ‘비어 있음(-)’이므

로 검색 실패입니다. 그러면 18을 검색하는 경우를 생각해 보겠습니다. 해시 값이 5인 버킷을
보면 그 속성은 ‘삭제 마침(★)’입니다. 그래서 그림 11-11처럼 재해시를 수행하여 6인 버킷
을 다시 검색합니다. 여기에는 값 6이 저장되어 있으므로 다시 재해시를 수행하여 7인 버킷을

검색합니다. 검색하는 값 18이 저장되어 있으므로 검색 성공입니다.

452 C 알고리즘