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

97

3

장

해싱

➊

k

로 만들어진 해시 코드에 대한 배열 인덱스 위치인

hc

를 계산한다.

➋

연결 리스트 내 첫 번째 노드에서 시작한다.

➌

k

와 일치하는

key

를 가지는 엔트리를 찾을 때까지

next

참조를 순회한다.

➍

k

와 연관된 값을 덮어쓴다.

➎

table[hc]

에

(k, v)

에 대한 새로운 노드를 추가하고 카운터

N

을 증가시킨다.

get

()

과

put

()

함수는 구조가 거의 동일하게, 함수 내에서 연결 리스트의 각

LinkedEntry

노드를 방문하는

while

루프가 있다.

table

[

hc

]

의 첫

LinkedEntry

에서 시작해

while

루프

는

entry

가

None

일 때까지 (모든 노드를 방문했다는 의미 ) 각 노드를 정확히 한 번씩 방문한

다.

entry

가

None

이 아닌 한

entry

.

key

속성을 조사해

k

매개변수와 정확히 일치하는 것이

있는지 확인한다.

get

()

에서 연관된

entry

.

value

가 반환되는 반면에

put

()

에서는 해당 값

을

v

로 덮어쓴다. 두 경우 최악의 상황에는

while

루프가 연결 리스트 내 엔트리를 모두 방문

하면 종료된다.

get

()

에서 연결 리스트를 모두 확인하고 찾은 엔트리가 없을 때

None

을 반환

한다.

put

()

은 이전에 존재하는 것이 없으므로 새로운 엔트리를 연결 리스트 맨 앞에 추가한다.

TIP

put

(