Hash Table
해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조로, 연관 배열 추상 자료형(ADT)를 구현한 자료구조다.
특징
대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)
해시 함수
해시 함수란 임의의 크기 데이터를 고정 크기 값으로 매핑하는데 활용되는 함수를 말한다.
"abcedewf", "nbkflnb", "weirupweouf" 등등 여러 입력값들이 있다고 했을 때 이 각각의 값들이 해시함수를 통과하면 길이가 2인 문자열로 바꾸는 함수가 해시함수의 예시이다.
abcedewf -> Hash() -> AL
nbkflnb -> Hash() -> 9P
weirupweouf -> Hash() -> B7
이렇게 해시 함수를 통해 입력값을 특정 값으로 바꾸는 작업을 해싱이라하고 해싱은 여러 분야에서 쓰이는 작업이다. 최적 검색에도 사용되며, 심볼 테이블 등의 자료구조를 구현하는데도 해싱이 쓰인다. 또한 체크섬, 손실 압축, 무작위화 함수, 암호 등과도 연관이 깊다.
성능이 좋은 해시함수는 아래와 같은 특징을 가진다.
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
충돌
충돌은 다른 입력 값이 해시함수를 통과했는데 같은 결과가 나온 경우를 말한다.
위 예시에서
abcedewf -> Hash() -> AL
nbkflnb -> Hash() -> AL
인 경우가 충돌이 발생한 것이다.
해시 테이블은 이러한 충돌을 해결할 방법으로 개별 체이닝을 제시하고 있다.
개별 체이닝
개별 체이닝은 충돌 발생시 연결 리스트로 연결하는 방식이다. 가장 전통적인 방식이며 해시 테이블이라 하면 대개 이 방식을 일컫는다.
AL abcdewf -> nbkflnb
원리는
- 키 해시 값 계산한다.
- 해시 값을 이용해 배열 인덱스를 구한다.
- 같은 인덱스가 있으면 연결 리스트로 연결한다.
이 경우 대부분 탐색이 O(1)이지만 최악의 경우(계속 해시 충돌이 발생해 모두 같은 인덱스에 연결된 경우)O(n)이다.
