11장. 해시테이블

해시 테이블 또는 해시 맵 = 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료구조다.

• 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.

• 데이터의 양에 관계없이 빠른 성능을 기대할 수 있는 장점이 있다.

해시 = 해시함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.

• 해시 테이블의 핵심은 해시 함수다. 여기서 입력값은 ABC, 1324BC, AF32B로 각각 3글자, 6글자, 5글자이지만, 화살표로 표시한 특정 함수를 통과하면 2바이트의 고정 크기 값으로 매핑된다.
• ABC → A1
• 1324BC → CB
• AF32B
 

해싱 = 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것

• 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나다.

• 해싱은 최적의 검색이 필요한 분야에 사용, 심볼테이블 등의 자료구조를 구현하기에도 적합하다.

• 해시 함수 값의 충돌 최소화

• 쉽고 빠른 연산

• 해시 테이블 전체에 해시 값이 균일하게 분포

• 사용할 키의 모든 정보를 이용하여 해싱

• 해시 테이블 사용 효율이 높을 것

충돌 = 해싱 결과 값이 같은 상황

• 개별 체이닝
• 연결리스트로 연결하는 방식
• 해시 테이블의 기본 방식, 무한정 저장 가능
• 대부분의 탐색은 O(1), 최악의 경우 O(n)

• 오픈 어드레싱
• 충돌 발생시 탐사를 통해 빈 공간을 찾아 나서는 방식
• 전체 슬롯 개수 이상 저장 불가
• 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장 X
• 의외로 전체적인 성능이 좋으나, 데이터들이 고르게 분포되지 않고 뭉치는 클러스터링 발생 가능
• 탐사 시간이 길어지고 해싱 효율이 떨어진다.
• 로드팩터(m/k, 적재율) 0.8부터 급격하게 효율이 떨어진다.
• 선형 탐사 방식은 0.8 이전까지 체이닝 보다 조회당 평균 캐시 실패가 낮다.
• 파이썬의 로드팩터는 0.66이다.

• 해시 테이블로 구현된 파이썬의 자료형은 딕셔너리
• 개별 체이닝이 메모리 할당하는 오버 헤드가 높아 오픈 어드레싱 사용

문제 리스트