[강의노트] 해시 테이블 - 2

해시 테이블 - 2

https://man-25-1.tistory.com/177

[강의노트] 해시 테이블 - 1

위의 게시글에 이어지는 내용입니다.

 

개방주소법에서의 갱신

이전글에서 개방주소법 알고리즘의 삭제는 조금 복잡한걸 언급했었다 한번 알아보자.

 비활성화 전략이라는 개념이 나오는데 이것은 이전에 설명한 삭제에서 생기는 오류를 방지하기 위한 전략이다.

 

findElement메소드를 보면 탐색과정에서 empty 상태를 탐색의 끝으로 보고 비어있는 셀을 만나면 탐색을 실패한것으로 간주한다. 따라서 삭제를 단순하게 항목을 empty 상태로 만드는 것은 치명적인 오류를 발생시킬 것이다. 그래서 항목이 삭제되었을때 empty가 아닌 기존에 사용하던 공간이지만 현재 사용하지않는다는 의미의 inactive 를 사용하는 것이다.

 

따라서 방의 status는 3가지가 존재하게 된다. empty , active, inactive

 

이렇게 자료구조를 세팅해놓으면 findElement , insertItem, removeElement 메소드를 구현하기 수월해진다.

 

조금 살펴볼만한 삭제 메소드의 알고리즘을 살펴보면, 삭제하고자하는 항목을 만나면 empty 로 만드는 것이 아니라

inactive로 만든다. 이것이 가장 핵심 ! 

 

적재율

해시테이블의 적재율은  버켓이 차지하고 있는 크기 n 을 해시테이블 공간 M으로 나눈것 a = n/M

이때 a가 1이 넘어갈 수 있을까? 정답은 가능하다. 

분리연쇄법의 경우 각 항목에 연결리스트를 달아놓는데 만약 M= 10 이라도, 각 항목당 3개의 리스트가 존재한다면

30개의 항목이 버켓에 적재되어 있는 것이다. 따라서 a가 1이 넘을수도 있다.

 

그러나 개방주소법의 경우에는 외부 메모리를 추가로 사용하지않기때문에 항상 a<=1 이다.

여기서 말하는 기대실행시간의 O(a)는 좋은 해시함수가 주어졌을 때 적재율 a는 1보다 아래로 유지되기때문에

기대실행시간은 O(1) 에 가까운 시간을 말함.

 

재해싱

재해싱은 적재율을 유지하기 위한 작업.

적재율을 0.75 이하로 유지하기 위해서는 원소를 삽입할 때마다 이 한계를 넘기지않기위해 뭔가 추가적인 작업이 필요하다. 그것이 재해싱 작업

여기서 너무 많은 비활성 셀들로 포화되어 성능이 저하되었을때의 경우를 생각해보자.

 

300개의 셀 중에 180개가 비활성 셀이라 하자. 이 경우 탐색과정이 매우 비효율적으로 진행되기때문에

남아있는 120개의 셀들을 가지고 재해싱을 해서 새로 배치를 시켜주면 해시테이블을 효율적으로 사용가능하다

 

재해싱단계에서는 압축맵을 새 크기에 맞게 수정해야하는 것을 주의하자.

 

해싱의 성능

적재율은 해시테이블의 성능을 좌우한다 .