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

87

3

장

해싱

3.3

(키, 값) 쌍에 대한 해시 테이블 구조

다음

Entry

구조제는 (키, 값 ) 쌍을 저장한다.

class Entry:

def __init__(self, k, v):

self.key = k

self.value = v

[코드

3

-

3

]은

Entry

객체를

M

개까지 저장 가능한

table

배열을 구성하는

HashTable

클래스

를 정의한다. 배열에서 이런

M

개의 인덱스 위치 각각을

버킷

bucket

이라 부른다. 첫 시도에서 버

킷은 비어 있거나 단일

Entry

객체를 포함할 수 있다.

코드

3-3

비효율적인 해시 테이블 구현

class Hashtable:

def __init__(self, M=10):

self.table = [None] * M

➊

self.M = M

def get(self, k):

➋

hc = hash(k) % self.M

return self.table[hc].value if self.table[hc] else None

def put(self, k, v):

➌

hc = hash(k) % self.M

entry = self.table[hc]

if entry:

if entry.key == k:

entry.value = v

else:

➍

raise RuntimeError('Key Collision: {} and {}'.format(k, ...