CH 05. 해시 테이블
- 해시 함수 : 문자열을 받아 숫자(인덱스)를 반환하는 함수 = 문자열에 숫자를 할당
- 해시 테이블 (=딕셔너리=연관배열) : 해시 함수 + 배열, 키와 값으로 구성
최악의 경우 O(n)
최선의 경우 O(1)
book = dict()
book["apple"] = 0.67
book["milk"] = 1.49
book["avocado"] = 1.49
print(book)
print(book["avocado"])
- 해시 테이블 사용 예
1. 조회 시 (전화번호부, DNS 확인 작업)
phone_book = {} ## dict()
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print(phone_book["jenny"])
2. 중복 방지 시
voted = {}
value = voted.get("tom")
def check_voter(name):
if voted.get(name):
print("돌려 보내세요")
else:
voted[name] = True
print("투표하게 하세요")
check_voter("tom")
check_voter("mike")
check_voter("mike") ## 두번째 호출 시에는 중복된 값으로 판단
3. 캐싱
def get_page(url):
if cache.get(url):
return cache[url]
else:
data = get_data_from_server(url)
cache[url] = data
return data
* 충돌 : 두 개의 키가 같은 공간에 할당되는 경우
* 해결 방법 : 같은 공간에 여러 개의 키를 연결 리스트로 생성하여 넣기 … 해시 테이블 느려질 수 있음
- 사용률 = 해시 테이블에 존재하는 항목 수 / 해시 테이블에 존재하는 공간 수
> 사용률이 커지면 공간 추가 필요 … 리사이징
참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
