[파이썬 알고리즘 인터뷰] 해시 테이블

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

• 연관 배열?
  키(문자열 명칭) 하나에 값 하나가 연결되어있는 자료구조의 일종.
  즉, 이름을 갖는 인덱스로 인덱싱화된 배열.

특징

대부분 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이다.

• 분할 상환 분석?
  상황에 따라 성능이 크게 변동하는 연산이나 알고리즘의 최악의 경우에도 평균적인 성능을 유지 할 수 있는 분석 기법.

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

해시 테이블의 핵심은 해시 함수다.
아래의 예시를 보자

예시)
ABC -> A1
1234BC -> CB
AF323BSE -> 5D

예시를 보면 화살표를 통해 크기가 일정하게 나온 결과값으로 매핑 된 것을 볼 수 있고, 여기서 화살표가 해시 함수 역할을 한 것이다.

해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라고 한다.

성능 좋은 해시 함수들의 특징은 다음과 같다.

1. 해시 함수값 충돌의 최소화
2. 쉽고 빠른 연산
3. 해시 테이블 전체에 해시값이 균일하게 분포
4. 사용할 키의 모든 정보를 이용하여 해싱
5. 해시 테이블 사용 효율이 높을 것

• 비둘기 집 원리(= 서랍 원리)?
  n개의 아이템을 m개의 컨테이너에 넣을 때, n > m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리.

• 개별 체이닝?
  해시 값 충돌(중복) 발생 시 연결 리스트로 연결하는 방식

• 오픈 어드레싱?
  충돌 발생 시 탐사를 통해 빈 공간을 찾아내어 삽입.
  이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.