해시 테이블
- Key-Value로 데이터를 저장하는 자료구조 중 하나로, 해싱을 통해 정보를 빠르게 저장하고 검색할 수 있다.
- 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다.
- 먼저 각각의 키에 해시 함수를 적용해 해시 코드를 계산하고, 계산한 해시 코드를 이용해 배열의 고유한 인덱스를 계산한다.
- 계산한 인덱스를 통해 값을 저장하거나 검색하며, 실제 값이 저장되는 장소를 버킷이라고 한다.
해시 함수
- 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수로, 충돌이 발생할 확률을 최대한 줄이는 것이 중요하다.
- 충돌은 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 것을 말하며, 충돌이 자주 발생하면 최악의 경우 탐색에 걸리는 수행 시간은 O(N)이다.
- 좋은 해시 함수들의 특징은 아래와 같다.
- 해시 함수값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
비둘기집 원리
- 비둘기집 원리란 n개 아이템을 m개 컨테이너에 넣을 때, n > m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 말한다.
- 비둘기집 원리에 따라 9개의 공간이 있는 곳에 10개의 아이템이 들어온다면 반드시 1번 이상은 충돌이 발생하게 된다.
- 좋은 해시 함수라면 충돌을 최소화하여 단 1번의 충돌만 일어나지만, 좋지 않은 해시 함수의 경우 심하면 9번을 충돌해서 10개의 공간 중 1개밖에 사용하지 못할 수도 있다.
로드 팩터
- 로드 팩터란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것으로, 로드 팩터 비율에 따라서 해시 함수를 재작성할지 또는 해시 테이블의 크기를 조정할지를 결정한다.
- 또한 이 값은 해시 함수가 키들을 잘 분산해 주는지에 대한 효율성 측정에도 사용된다.
- 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소하게 되며, 자바 10의 경우 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당 한다.
해싱 알고리즘
알고리즘 | 설명 |
Division Method | 나눗셈을 이용하는 방법으로, 입력값을 해시 테이블의 크기로 나누어 계산한다. 해시 테이블의 크기는 일반적으로 2의 제곱수와 먼 소수로 정하는 것이 좋다. |
Digit Folding | 각 키의 문자열을 아스키 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법 |
Multiplication Method | 숫자로 된 키 값, 0과 1 사이의 실수, 2의 제곱수를 사용하여 계산하는 방법 |
Universal Hashing | 다수의 해시 함수를 만들어 집합에 넣어두고, 무작위로 해시 함수를 선택해 해시 값을 만드는 방법 |
충돌 완화
개방 주소법 (Open Addressing)
- 오픈 어드레싱 방식은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식으로, 충돌이 일어나면 테이블 공간 내에서 탐사(Probing)를 통해 빈 공간을 찾아 해결한다.
- 오픈 어드레싱 방식은 연속된 공간에 데이터를 저장하기 때문에 개별 체이닝에 비해 캐시 효율이 높으므로, 데이터의 개수가 충분히 적다면 오픈 어드레싱 방식의 성능이 더 좋다.
탐사 방식 | 설명 |
Linear Probing | 충돌이 발생했을 때 비어있는 인덱스를 찾을 때까지 다음 인덱스로 이동하는 방법으로, 충돌 횟수가 작을 때 아주 빠르고 공간 절약적이다. 하지만 해시 테이블 여기저기에 연속된 데이터 그룹이 생기는 클러스터링 현상이 발생해 탐색과 삭제가 오래 걸리고, 전체적으로 해싱 효율이 떨어지게 된다. |
Quadratic Probing | 탐색 거리를 1, 4, 9, ... 처럼 제곱수로 증가시키는 방법으로, 선형 탐사에 비해 더 폭넓게 탐사할 수 있다. 하지만 여전히 클러스터링 문제는 발생한다. |
Double Hashing Probing | 클러스터링 문제를 해결하기 위해 도입된 방법으로, 처음 해시 함수는 해시 값을 찾기 위해 사용하고 두 번째 해시 함수는 충돌이 발생했을 때 탐사폭을 계산하기 위해 사용한다. |
- 오픈 어드레싱 방식은 해시 테이블에 담을 수 있는 전체 데이터가 배열의 크기에 제한되므로, 기준이 되는 로드 팩터 비율을 넘어서게 되면 그로스 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 새롭게 복사하는 리해싱 작업이 일어난다.
개별 체이닝 (Separate Chaining)
- 개별 체이닝은 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정하고, 버킷을 아래와 같은 자료구조로 구성해 충돌이 발생할 경우 해당 버킷의 자료구조에 추가한다.
- 연결리스트: 충돌되는 횟수가 작을 경우 사용하며, 데이터가 이상하거나 해시 함수 성능이 나쁠 때 최악의 경우 탐색에 O(N) 시간이 걸린다.
- 이진 탐색 트리: 탐색에 O(logN) 시간이 걸리지만 데이터가 극단적으로 균일하게 분포할 때만 사용한다.
- 레드-블랙 트리: 자바 8에서는 연결리스트 구조를 좀 더 최적화해서 데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 한다.
- 해시 테이블 구조의 원형이 되는 가장 전통적인 방식으로, 흔히 해시 테이블이라고 하면 개별 체이닝 방식을 이야기 한다.
- 또한 개별 체이닝 방식은 해시 테이블의 확장을 보다 늦출 수 있다는 장점이 있다.
'Python > Algorithm' 카테고리의 다른 글
트리의 종류와 트리 순회 (0) | 2022.02.26 |
---|---|
최단 경로 알고리즘 (0) | 2022.02.25 |
그래프와 그래프 탐색 (0) | 2022.02.25 |
스택과 큐 (0) | 2022.02.23 |
배열과 연결리스트 (0) | 2022.02.22 |