고성능 파이썬(2판)

120

고성능 파이썬(2판)

4.1.2

삭제

해시 테이블에서 값을 삭제할 때 단순히 해당 메모리 블록을

NULL

로 만드는 방법은 사용할 수

없다.

NULL

을 프로빙 시 해시 충돌을 위한 감싯값

sentinel

value

으로 사용하기 때문이다. 따라서

해당 블록이 비었음을 나타내는 특수한 값을 기록해두고 나중에 해시 충돌을 해결하는 과정에

서 이 값을 활용해야 한다. 예를 들어

Rome

이 삭제된 다음에

Barcelona

를 검색하면 처음에는

Rome

이 들어있던 블록이 비었음을 나타내는 값이 있는 배열 항목을 먼저 만난다. 값을 찾지 못

했다고 멈추는 대신,

index

_

sequence

함수가 반환하는 다음 색인을 검사해야 한다. 해시 테이

블의 빈 슬롯은 새로운 값이 쓰이거나 해시 테이블의 크기가 변경될 때 삭제된다.

4.1.3

크기 변경

해시 테이블에 항목이 추가되면 해시 테이블의 크기도 그에 맞춰 변경되어야 한다. 해시 테이

블의

2

/

3

이하만 채워진다면 충돌 횟수와 공간 활용 측면 모두 적절하다고 볼 수 있다. 따라서

해시 테이블이 임계 크기에 다다를 때까지 계속 사용하면 된다. 크기를 변경할 때는 충분히 큰

해시 테이블을 할당하고 (더 많은 메모리를 할당하고 ) 그 크기에 맞게 마스크값을 조정한다.

그리고 모든 항목을 새로운 해시 테이블로 옮긴다. 이 과정에서 ...