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

85

3

장

해싱

>

0

일 때마다 주어진 문자열

s

가 유효한 달의 이름인지 확인하고 싶을 수 있는데, 그것은 옳지

않다. 예를 들어, 문자열

'

abbreviated

'

를 계산하면

'

March

'

와 같은 인덱스 위치로 계산되

어

'

abbreviated

'

가 유효한 달이라고 잘못 알려줄 수 있다. 이는 나쁜 기능이다. 지금부터 해

당 이슈를 해결하는 방법을 알아보자.

3.2

해시 함수와 해시 코드

base26

()

은 임의 크기의 키를

32

비트나

64

비트 정수와 같은 크기가 고정된 해시 코드 값과

매핑하는

해시 함수

hash

function

의 예다.

32

비트 정수는 –

2

,

147

,

483

,

648

과

2

,

147

,

483

,

647

사

이의 값이고

64

비트 정수는 –

9

,

223

,

372

,

036

,

854

,

775

,

808

과

9

,

223

,

372

,

036

,

854

,

775

,

807

사이의 값이다. 보다시피 해시 코드는 음수일 수 있다.

수학자들은 수십 년간 해싱을 연구하며 구조적 데이터를 고정 길이의 정수로 변환하는 계산

을 개발했으며 프로그래머들은 이를 활용할 수 있다. 대부분의 프로그래밍 언어가 임의 데이

터에 대한 해시 코드를 계산하는 내장 지원을 가지기 때문이다. 파이썬은 불변의 객체에 대한

hash

()

메서드와 같은 것을 제공한다.

NOTE

_ 해시 함수에 필요한 단 한 가지 속성은 서로 같은 두 객체는 반드시 ...