똑똑한 코드 작성을 위한 실전 알고리즘

116

똑똑한 코드 작성을 위한 실전 알고리즘

●

연결 리스트 자료구조는 동적 삽입과 제거를 허용해 작은 컬렉션을 효율적으로 저장할 수 있다.

●

심볼 테이블은 엔트리를 저장하는 데 버킷이

M

개인 저장 배열을 사용한다. 이때, 같은 버킷으로 할당되

는 키 해시가 두 개 이상일 때 충돌을 해결할 전략이 있어야 한다.

●

개방 주소법은 충돌 횟수를 줄이기 위해 배열 내 항목을 분산하는 데 의존하지만, 이는 저장 배열 크기

M

이 저장된 엔트리 개수

N

보다

2

배 이상 클 때만 효율적으로 동작한다. 키 제거를 지원하는 두 가지 접

근에 대한 연습 문제를 확인하자.

●

분리 연쇄법은 해시 코드가 동일한 키를 가지는 엔트리를 저장하는 데 연결 리스트를 사용한다. 해당 접

근은 키에 대한 제거 연산을 더 쉽게 지원할 수 있다.

●

해시 함수를 설계하기는 어렵다. 그러니 파이썬 설계자가 고안한 미리 정의된 것을 사용하자.

●

기하학적 크기 재조정은 미래에 발생할 크기 조정의 빈도를 감소해 심볼 테이블이 효율적인 상태로 유

지되도록 한다.

●

완벽한 해싱은 개수가 고정된 키에 대해 고유한 인덱스 위치를 계산해 충돌을 회피하는 해시 함수를 구

성하기 위해 사용한다. 해당 해시 함수는 기본으로 제공되는

hash()

함수보다 더 많이 계산해야 하는 경

우가 종종 있다.

3.13

연습 문제

1.

충돌을 해결하기 위해 다른 전략을 사용하면 개방 주소법의 성능이 향상될까? 바로 다음

인덱스를 선택하는 선형 조사를 사용하는 대신에 크기가

2

의 거듭제곱인 해시 테이블을 생

성하고, ...