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

115

3

장

해싱

표

3-6

해시 테이블 반복자가 반환한 단어의 순서

개방 주소법 분리 연쇄법 완벽한 해싱

a sweet a

by any any

any a as

name would by

other smell name

would other other

smell as rose

as name smell

sweet by sweet

rose rose would

개방 주소법과 분리 연쇄법의 해시 테이블에 대해 반환된 단어는 무작위 순서로 나타난다. 물

론 이는 키가 해싱되는 방식에 전적으로 기반하므로 무작위는 아니다. 직접 예제 코드를 실행

해보면 개방 주소법과 분리 연쇄법에 대한 순서는 아마 [표

3

-

6

]과 다를 것이다 (파이썬

3

에서

문자열에 대한

hash

()

코드 값은 예측이 불가능하기 때문).

perfect

-

hash

라이브러리의 좋은 기능 하나는

perfect

_

hash

(

key

)

로 계산된 인덱스 위치

는 완벽한 해싱으로 코드를 생성할 때 사용된 단어의 순서를 기반으로 한다는 것이다. 단순히

이미 정렬된 문자열 리스트를 사용하면 엔트리는 정렬된 순서대로 저장되고 반복자는 같은 순

서로 (키, 값 ) 쌍을 제공할 것이다.

8

장에서는 파이썬

dict

타입을 더 상세히 다룬다. 이 장에서 했던 것처럼 처음부터 심볼 테이

블을 구현하지 말고 항상

dict

를 사용해야 한다.

dict

는 내장 타입이며 ...