[선형 자료구조] 해시 테이블

참고자료

출처 : 파이썬 알고리즘 인터뷰 (279p~)

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

- 해시 테이블의 가장 큰 특징은 시간 복잡도가 O(1)이라는 점이다.

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

ABC → A1

1324BC → CB 

(여기서 화살표 역할을 하는 함수가 바로 해시 함수다)

 

- 해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱(Hashing)이라 하며,

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

 

- 해싱이 사용되는 분야 :

• 최적의 검색이 필요한 분야
• 심볼 테이블 등의 자료구조를 구현
• 체크섬(Checksum)
• 손실 압축
• 무작위화 함수(Ramdomization Function)
• 암호

- 성능 좋은 해시 함수들의 특징 :

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

<충돌>

아무리 좋은 해시 함수라도 충돌(collision)은 발생하게 된다. 충돌이 발생할 경우 어떤 식으로 처리하게 되는지 살펴보자.

• 개별 체이닝 (Separate Chaining)  :
  • 충돌 발생 시 연결 리스트로 연결 하는 방식
  • 흔히 해시 테이블이라고 하면 바로 이 방식을 말한다. 
  • 잘 구현한 경우 탐색은 O(1)이지만 최악의 경우, 즉 모든 해시 충돌이 발생했다고 가정할 경우에는 O(n)이 된다.
  • 원리
    1. 키의 해시 값을 계산한다.
    2. 해시 값을 이용해 배열의 인덱스를 구한다.
    3. 같은 인덱스가 있다면 연결 리스트로 연결한다.
• 오픈 어드레싱 (Open Addressing) :
  • 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식
  • 무한정 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯 개수 이상은 저장할 수 없다.
  • 따라서 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다. 
  • 선형 탐사(Linear Probing) : 오픈 어드레싱 방식 중에서 가장 간단함
    • 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다.
    • 특정 위치가 선점되어 있으면 바로 그다음 위치를 확인하는 식이다.
    • 이렇게 탐사를 진행하다가 비어있는 공간을 발견하면 삽입하게 된다. (가장 가까운 다음 빈 위치를 탐색해 새 키를 삽입)
    • 선형 탐사 방식은 구현 방법이 간단하면서도, 의외로 전체적인 성능이 좋은편이다.
    • 한 가지 문제점은 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향이 있다는 점이다. 이러한 현상을 클러스터링(Clustering)이라 하는데, 탐사 시간을 오래 걸리게 하며, 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다.

딕셔너리 자료형은 해시 테이블로 구현되어 있다. 

파이썬의 해시 테이블은 충돌 시 "오픈 어드레싱 방식"을 사용한다.