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

93

3

장

해싱

값 제거하기

연결 리스트에서 노드를 찾고 그에 따라

next

참조를 조정해 값을 제거할 수 있다. 이 값이 리스

트 내 첫 번째 노드라면 특별히 주의를 기울여야 한다.

최악의 경우에 대한 시나리오에서 어떤 일이 발생하는지 생각해보자. 비어 있는

Hashtable

에

엔트리를 추가하고

table

[

0

]

에 넣었다고 가정하자. 다음

N

-

1

개의 항목 추가 요청이

table

저장 공간 내 기존 키와 충돌하면 어떻게 될까? 탐색해야 하는 버킷은 총 몇 개일까? 첫 번째

요청에서 그 수는

1

이다. 두 번째 요청에서는

2

이고 세 번째에서는

3

이다. 보다시피,

k

번째 요

청에 대해

k

개의 버킷을 조사해야 한다. 총 개수는

1

+

2

+…+ (

N

-

1

)의 합이며 해당 식은

N

×

(

N

-

1

)/

2

와 같다. 평균 계산은 이를

N

으로 나눈 값으로 (

N

-

1

)/

2

만 남게 된다.

NOTE

_

2

장에서 설명한 내용을 기반으로 (

N

-

1

)/

2

를

O

(

N

)으로 분류할 수 있다. 먼저, 해당 공식은

N

/

2

-

1

/

2

로 쓸 수 있다. 문제 인스턴스 크기가 커짐에 따라 지배적인 항은

N

/

2

가 된다. 최악의 경우 탐색할 평균

버킷 개수는

N

에 정비례하게 된다(이 경우에는

N

의 절반).

최악의 경우 탐색할 평균 버킷 개수가

O

(

N

)임을 증명했다.

get

()

과

put

()

에 대한 런타임 성

능은 탐색할 버킷 개수와 ...