[비선형] Hash Table

❒ Description

---

비선형 자료 구조 중 하나인 Hash Table의 특징, 충돌 로드 팩터 등등 해시 테이블에 대해서 자세히 알아보자.

 

 

❒ 해시, 해시 함수 그리고 해시 테이블

---

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

가장 큰 특징은 대부분의 연산이 시간 복잡도 O(1)이라는 점이다.

 

해시는 어떤 길이의 임의 데이터를 고정 길이의 데이터로 매핑하는 것을 말한다.

해시 함수는 임의의 크기의 입력 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 

해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 하며, 

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

 

해시 함수의 특징은 입력되는 데이터가 뭐든 출력되는 해시값의 길이가 고정되어 있다는 것이다. 

하지만 해시 함수는 서로 다른 입력 2개에 같은 해시값을 생성할 가능성도 조금 있다. 이것을 해시 충돌이라고 한다.  

 

해시 테이블의 크기를 소수로 정하는 이유

 

 

 

❒ 해시 충돌과 그 해결책

---

위에서 언급했듯 해시 충돌은 서로 다른 2개의 입력에 같은 해시값을 반환하는 것을 말한다. 

그렇다면 충돌을 어떻게 해결할 수 있을까?

 

1. 개별 체이닝

해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 연결 리스트로 연결하는 방식이다.

잘 구현한 경우 대부분의 탐색은 O(1)이지만, 모든 해시 충돌이 발생했다고 가정할 경우 O(n)이 된다.

자바에서는 해당 방식을 채택하여 사용중이다. 

 

---

2. 오픈 어드레싱 (개방 주소법)

오픈 어드레싱 방식은 충돌 시 탐사(Probing)를 통해 빈 공간을 찾아나서는 방식이다.

 

선형 탐사는 오픈 어드레싱 방식 중 가장 간단한 방식으로, 특정 위치가 선점되어 있으면 바로 그 다음

위치를 확인한다. 선형 탐사의 한 가지 문제점은 데이터가 고르게 분포되지 않고 뭉쳐지는 클러스터링이다.

이 현상은 탐사 시간이 오래 걸리게 하며, 전체적으로 해싱 효율을 떨어뜨리는 원인이 된다.

 

오픈 어드레싱은 버킷 크기보다 큰 경우에는 삽입할 수 없다. 로드 팩터 비율을 넘어서면

그로스 펙터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는

Rehashing 작업이 일어난다. HashMap의 그로스 펙터는 2이며 로드 펙터는 0.75다.

 

파이썬에서는 해당 방식을 채택하여 사용중이다.