Hash Table
키와 값의 쌍으로 이뤄진 데이터를 저장하는 자료구조
키는 일반적으로 문자열이나 정수형으로 지정
해쉬 함수를 통해 키와 값을 연결한다.
해쉬 함수
임의의 크기를 가진 키 값을 입력을 받아서
고정된 크기의 값으로 변환하는 함수이다.
이 변경된 값은 해쉬 테이블의 배열 인덱스 값으로 활용된다.
해쉬 함수의 특징
- 일관성
동일한 입력값은 동일한 데이터를 출력한다.
- 고르게 분포된 해쉬값
다른 입력값이 같은 결과 값으로 나오지 않게 고르게 분포시켜야한다.
- 해쉬 충돌 최소화
다른 입력값으로 같은 값으로 나오면 충돌이 발생한다.
이러한 경우 데이터 손실이 일어날 수 있다.
따라서 최대한 해쉬 충돌을 최소화해야한다.
충돌 대비책
Open Address 방식
다른 해시값을 가진 빈 버킷을 찾아 데이터를 저장하는 방법
Linear Probing
순차적으로 비어있는 버킷을 찾을 때까지 계속 진행하는 방식
만약 빈 버킷이 없다면 해쉬 테이블을 확장한다.
일반적으로 기존 테이블 크기에서 2배정도 확장한다.확장 후 기존 테이블을 다시 해싱하여 확장된 테이블에 저장하고
저장하려면 값을 저장한다.확장은 추가적인 비용을 발생시키므로 기존에 크기 설계를 잘해야한다.
Quadractic Probing
2차 함수를 사용해 탐색할 위치를 찾는다.
충돌이 발생한 버킷의 인덱스를 i라고 하면 다음과 같은 공식을 사용한다.
next = (i + c1 * k + c2 * k^2) % table_size이때 c1 c2 는 정해진 상수이다.
Linear Probing에 비해 일정한 간격으로 다음 버킷을 찾기 때문에
클러스터링 문제를 완화시킬 수 있다.
클러스터링이란 동일한 해쉬 값을 나타내는 것들이
인접한 곳에 몰리는 현상을 말한다.클러스터링이 발생하면 성능저하가 발생한다.
충돌이 발생한 버킷에서 데이터를 찾기 위해서
해당 버킷 이후의 버킷도 검색해야한다.
따라서 데이터를 찾는데 평균시간이 증가하고
최악의 경우 선형 탐사와 유사한 시간이 걸린다.또한 공간을 비효율적으로 사용될 수도있다.
일부 버킷에만 데이터가 몰리고 다른 버킷은 비어 있게될 수도 있다.
Double Hashing
해쉬 충돌이 발생했을 때 다른 해쉬 함수를 이용하여 빈 버킷을 사용하는 방법
Separate Chaining 방식
동일한 해시 값을 갖는 원소들을 연결리스트 또는 Red Black Tree에 추가
연결리스트의 길이가 길어질 경우 검색 속도가 느리다.
따라서 이와 같은 경우 Red Black Tree를 사용한다.Red Black Tree는 Binary Search Tree 기반의 자료구조로
검색/삽입/삭제 시간이 O(logn) 으로 빠르다.
하지만 노드가 가지고 있는 데이터의 종류가 연결리스트 보다 많기 때문에
공간 복잡도 측면에서는 비교적 좋지 않다.
