해시 테이블

해시 함수 

• 문자열을 받아서 숫자를 반환하는 함수
• 문자열에 대해 숫자를 할당(mapping) 한다

조건 1 일관성이 있어야한다. 예를 들어, "apple"을 넣었을 때 "4"를 반환한다면 "apple"을 넣을 때마다 반환되는 값은 항상 "4"이어야 함

=같은 이름에 대해서는 항상 같은 인덱스를 할당한다

조건 2 다른 단어가 들어가면 다른 숫자가 나와야 함. 예를들어 어떤 단어를 넣어도 "1"만 나온다면 좋은 해시 함수가 아님

=다른 문자열에 대해서는 다른 인덱스를 할당한다.

해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 한다.

해시 테이블

(=해시 맵 =맵 =딕셔너리 =연관 배열)

해시 테이블 = 해시 함수 + 배열 

book = dict()

book["apple"] = 0.6

book["milk"] = 2.45

book["avocado"] = 2.3

print book #{'avocado': 2.3, 'apple': 0.6, 'milk': 2.45}

print book["avocado"] #2.3

웹 주소에 대해 IP 주소를 할당하는 작업 (DNS resolution) => 해시 테이블은 이 기능을 제공하는 방법 중의 하나

중복 항목 방지하기

voted = {} #voted = dict() 과 같다

def check_voter(name):

if voted.get(name):

print "이미 투표를 완료한 사람입니다"

else:

voted[name] = True

print "투표하세요"

check_voter("lee") #투표하세요

check_voter("jang") #투표하세요

check_voter("lee") #이미 투표를 완료한 사람입니다

해시 테이블을 캐시로 사용하기

캐시란? 

• 서버가 홈페이지에 어떤 정보를 제공할지 고민할 필요 없이 홈페이지의 내용을 외워서 보여주는 것
• 캐싱은 작업 속도를 올리는 일반적인 방법이며, 자료는 해시 테이블에 저장됨

URL 호출 -> 해시 테이블에 있는지 확인 -> 예: 해시 테이블의 내용 전송

아니오: 서버 작업

cache={}

def get_page(url):

if cache.get(url):

return cache[url] #캐싱된 자료를 전송

else:

data = get_data_from_server(url)

cache[url] = data #캐시에 처음으로 자료를 저장

return data

해시 테이블의 장점

1. 어떤 것과 다른 것 사이의 관계를 모형화
2. 중복을 막을 수 있음
3. 서버에게 작업을 시키지 않고 자료를 캐싱할 수 있음

충돌

• 해시 함수는 서로 다른 키를 배열의 서로 다른 위치에 할당한다? ->사실 거의 불가능한 이야기

배열공간에, 알파벳 순서로 공간을 할당한다고 할 때

0번째에 apples

1번째에 bananas

avocados를 해시 테이블에 넣으려고 할 때 apples가 이미 공간을 차지하고 있다 => 덮어 씌워짐

=> 충돌(collision)

• 충돌을 해결하는 방법

-가장 간단한 방법: 같은 공간에 여러 개의 키를 연결 리스트로 만든다

0번째 공간 - > apples -> avocados

1번째 공간: bananas

단점1.  a로 시작하는 상품이 많아지면 a로 시작하는 상품을 찾을 때 속도가 느려짐

단점2.  2번째 공간부터는 비게 됨

-해시 함수는 중요하다. 이상적으로는 해시 함수는 키를 해시 테이블 전체에 고르게 할당해야 한다

-연결 리스트가 길어지면, 테이블의 속도도 느려진다. 좋은 해시 함수가 필요하다

성능

	해시테이블(평균)	해시테이블(최악)	배열	연결리스트
탐색	O(1)	O(n)	O(1)	O(n)
삽입	O(1)	O(n)	O(n)	O(1)
삭제	O(1)	O(n)	O(n)	O(1)

충돌을 피하기 위해서는?

1. 낮은 사용률
2. 좋은 해시 함수

• 사용률

해시 테이블에 있는 항목의 수 / 해시 테이블에 있는 공간의 수

[ ,"1", ,null, ]

사용률 2/5 = 0.4

사용률이 1보다 크다는 것은 배열에 공간의 수보다 항목의 수가 많다는 것

->resizing해야 함 

risizing은 평균적으로 O(1)의 시간이 걸린다.

좋은 해시 함수?

• 배열에 값을 고루 분포시키는 함수
• 나쁜 해시 함수는 값들이 뭉쳐져 있어 충돌이 자주 발생

정리

1 해시 테이블 = 해시 함수 + 배열

2 충돌을 줄이는 해시 함수가 필요함

3 해시 테이블은 빠른 탐색,삽입,삭제 속도를 가짐

4 해시 테이블은 어떤 항목과 다른 항목의 관계를 모형화하는 데 좋음

5 사용률이 0.7보다 커지면 해시 테이블을 리사이징 해야함

6 해시 테이블은 데이터를 캐싱하는 데도 사용됨

7 해시 테이블은 중복을 잡아내는 데에 뛰어남