알고리즘 문제 풀이에 쓰이는 자료구조의 활용
알고리즘 문제를 풀다보면 데이터를 저장할 일이 정말 많은데, 보통 배열을 사용하게 된다면 데이터를 조회할 때 O(n)만큼의 시간이 소요되어 데이터가 많아진다면 시간 초과가 발생하곤 합니다.
이를 개선할 수 있는 방법으로는 트리가 있는데, 트리는 원소 하나를 저장하거나 검색하는데 O(log n) 의 시간이 소요됩니다. 특히나 자가 균형 이진 탐색 트리 중 하나인 레드 블랙 트리의 경우 최악의 경우에도 O(log n)을 보장합니다.
이러한 방식으로도 많이 개선되기는 하지만, 그래도 데이터의 크기가 커질 수록 데이터를 삽입하고 조회하는 성능에 영향을 받게 됩니다.
위 문제에서 벗어나 저장된 자료의 양에 상관없이 데이터 하나를 저장하고 검색하는 것을 상수 시간에 가능하게 도와주는 자료구조가 해시 테이블 입니다.
해시 테이블(Hash Table)
해시 테이블(HashTable) 또는 해시맵(Hash Map)은 키를 값에 매핑할 수 있는 자료구조로 해시 테이블의 가장 큰 특징은 연산의 대부분이 시간복잡도 O(1)을 가진다는 점입니다. 이러한 특징으로 데이터 양에 관계없이 빠른 성능을 기대할 수 있다는 장점이 있습니다.
해시
해시 테이블의 핵심은 해시 함수 입니다. 입력값이 Hello World 여도 특정 함수를 통과하면 d2a84f4b8b650937ec8f73cd8a804a26 ... 와 같은 값으로 매핑되고 이를 가능하게 해주는 것이 해시 함수 입니다.
이렇게 해시 테이블을 인덱싱 하기 위해 해시 함수를 사용하는 것을 해싱(Hashing) 이라고 합니다.
생일 문제 (Birthday Problem)
일년이 365일로 생일의 가짓수가 365개이므로 사람들이 많더라도 비둘기 집 원리에 따라 366명은 되어야 일어나는 일 처럼 느껴지지만, 실제로는 위 그래프와 같이 23명만 모여도 생일이 중복될 확률이 50% 가 되고 57명을 넘어가면 그떄부턴 99% 확률로 생일이 같은 사람이 존재한다고 합니다.
비둘기집 원리
비둘기집 원리는 1834년 독일의 수학자 페터 디리클레(Peter Dirichlet)가 만든 것으로 n개의 아이템을 m 개의 컨테이너에 넣었을 때 n>m 이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어있다는 원리를 말합니다.
생일 문제 소스 코드
public static void main(String[] args) {
int sameBirthdays = 0;
for (int i = 0; i < 100000; i++) {
int[] birthdays = new int[23];
// 23명이 모이는 경우
for (int j = 0; j < 23; j++) {
//365일 중 랜덤하게 지정
int birthday = ThreadLocalRandom.current().nextInt(1, 365 + 1);
// 만약 같은 날이 존재한다면 일치 여부 +1 이후 다음 실험 진행
if (IntStream.of(birthdays).anyMatch(x -> x == birthday)) {
sameBirthdays++;
break;
}
// 일치하지 않는 경우 저장하고 다음 사람으로
birthdays[j] = birthday;
}
}
System.out.print("10만 번 실험 중 생일이 같은 실험의 확률: ");
System.out.print((double) sameBirthdays / 100000 * 100);
System.out.println("%");
}
로드 팩터
충돌이 발생할 때, 또는 충돌이 발생하기 전 최적화를 하려면 일정 비율에 따라 함수를 재작성 할지, 또는 해시 테이블의 크기를 조정할지를 결정하는데 이를 로드 팩터라고 합니다.
로드팩터
해시테이블에 저장된 개수 n 을 버킷의 개수 k로 나눈 것 로드팩터 - n/k
자바는 8버전에 이르러 해시맵을 대폭 개선했고, 기본 로드팩터를 0.75로 정했다고 합니다.
일반적으로 로드팩터가 증가할 수록 해시 테이블의 성능은 점점 감소하며 (데이터가 많이 저장될수록 빈 공간은 적어지고 그만큼 충돌이 많이 일어나기 때문 이라고 예상) 자바는 0.75를 넘어설 경우 ArrayList의 더블링처럼 해시 테이블의 공간을 재할당 하는데 이것을 리해싱 이라고 합니다.
해시함수
해시함수란 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수 입니다.
성능 좋은 해시 함수의 특징
해시 함숫값 충돌의 최소화
쉽고 빠른 연산
해시 테이블 전체에 해시값이 균일하게 분포
사용할 키의 모든 정보를 이용하여 해싱
해시 테이블 사용 효율이 높을 것
원소가 해시 테이블 전체에 고루 저장되어야 함
그림처럼 해시 테이블을 인덱싱 하기 위해 해시 함수를 사용하는 것을 해싱(Hashing) 이라고 합니다.
해시 함수 중 가장 단순하면서 널리 쓰이는 정수형 해싱 기법인 모듈로 연산을 이용한 나눗셈 방식은 다음과 같습니다.
h(x) = x mod m
입력값 x를 해시테이블의 크기인 m 으로 나누는 방식이고, m의 값은 2의 멱수(거듭제곱으로 된 수)에 가깝지 않은 소수를 선택하는 것이 좋다!
충돌 해결
아무리 좋은 함수라고 해도 충돌은 발생하는데, 이러한 충돌을 해결하는 방법도 여러가지가 존재합니다.
1️⃣ 체이닝(Chaining)
먼저 위의 표와 같이 해싱 결과가 충돌 한다고 가정할 때 개별 체이닝(separate Chaining) 방식으로 구현하면 다음과 같습니다
해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생시 연결 리스트로 연결하는 방식입니다. 가장 전통적인 방식으로 흔히 해시 테이블이라고 하면 이 방식을 말하고, 자바의 해시 테이블 구현체인 HashMap도 연결 체이닝 방식으로 구현되어 있습니다.
개별 체이닝의 절차는 다음과 같습니다
1. 키의 해시값을 계산
2. 해시값을 이용해 배열의 인덱스를 구함
3. 같은 인덱스가 있으면 연결 리스트로 연결
잘 구현 할 경우 대부분 탐색은 O(1)이지만, 최악의 경우 즉, 모든 해시 충돌이 발생할 경우 O(n)이 됩니다. 자바8의 해시테이블 구현체인 HashMap은 연결리스트 구조를 좀 더 최적화해서, 데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태를 병행하기도 합니다.
2️⃣ 오픈 어드레싱(Open Addressing)
개방 주소법 이라고도 하는 오픈 어드레싱(Open Addressing) 방식은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식입니다.
연결리스트로 연결해 나가기 때문에 사실상 무한히 저장할 수 있는 체이닝 방식과 다르게 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없습니다.
충돌이 일어나면 테이블 공간 내에서 탐사를 통해 빈 공간을 찾아 해결하기 때문에 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 되지는 않습니다.
위 그림은 다양한 오픈 어드레싱 방식 중 가장 간단한 선형 탐사 방식의 예시인데(i는 1로 충돌이 일어나면 i칸 다음을 순차적으로 조사), 충돌이 발생할 경우 해당 위치부터 순차적으로 탐색을 진행하고, 비어있는 공간에 데이터를 삽입하게 됩니다.
2에서 충돌되어 토리가 3 에 저장되고, 데이가 3에서 토리와 또 충돌해 4에 저장되게 됩니다.
클러스터링
선형탐사의 문제점으로는 순차적으로 탐색하다보니 특정 구간에만 데이터가 뭉쳐 그룹이 형성되는 현상이 발생하는데 이러한 현상을 클러스터링이라고 합니다. 클러스터링 현상은 탐사 시간이 오래걸리게 하고, 전체적으로 해싱 효율을 떨어뜨리는 원인이 됩니다.
선형 탐사 이외에도 i라는 일차원 값을 사용하는 것이 아닌 이차함수로 보폭을 넓혀가면서 탐사하는 이차원 탐사와, 두개의 함수를 사용하는 더블 해싱 등 다양한 방법이 존재합니다.
오픈 어드레싱 방식의 리해싱
오픈 어드레싱 방식은 버킷 크기(전체 슬롯의 개수) 보다 큰 경우에는 삽입이 불가능 하기에 기준이되는 로드 팩터 비율을 넘게되면, 그로스팩터(Growth Factor)의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 새롭게 복사하는 리해싱(Rehashing) 작업이 일어납니다.
자바의 ArrayList의 Growth Factor가 1.5 인 것처럼, HashMap의 그로스 팩터는 2 입니다. 이는 해시맵에 저장되는 데이터가 로드팩터(0.75)를 넘어서면 2배 더 큰 메모리 영역을 새롭게 할당한다는 의미입니다. 따라서 해시맵은 75% 이상 차면 2배 더 큰 메모리 영역을 할당합니다.
간단 요약 정리
HashMap
- 로드팩터 0.75
- 그로스팩터 2
- 기본 사이즈 16ArrayList
- 로드팩터 1
- 그로스 팩터 1.5
- 기본 사이즈 10
언어별 해시 테이블 구현방식
해시 테이블의 구현 방식이 크게 체이닝 방식, 오픈 어드레스 방식이 있다는 것은 알겠는데
그렇다면 자바의 해시 테이블 구현체는 둘중 무엇일까?
자바에서는 HashMap이 자바의 해시 테이블 구현채고,이전에 설명했던 것처럼 HashMap은 연결 체이닝 방식으로 구현되어 있습니다.연결리스트 구조를 최적화해서, 데이터의 개수가 많아지면, 레드 블랙 트리에 저장하는 형태를 병행하기도 합니다.
❗️반면에 스크립트 언어의 경우(파이썬, 루비) 오픈 어드레싱으로 구현하는 경우가 많습니다.
로드팩터 크기에 따른 알고리즘 성능 비교
위 그래프와 같이 보통은 오픈 어드레스 방식이 체이닝 방식보다 성능이 좋지만, 80% 이상 차게되면 급격하게 성능이 저하되는 것을 확인할 수 있습니다. 따라서 파이썬, 루비 같은 스크립트 언어들은 오픈 어드레스 방식으로 성능을 높이는 대신, 파이썬의 경우 로드팩터를 0.66, 루비의 경우 0.5로 로드팩터를 작게 잡아 성능 저하 문제를 해결합니다.
로드팩터가 작을수록 좋은가?
ArrayList에서도 데이터 삽입시 성능에 가장 영향을 미치는 것이 더블링이었는데, 로드팩터가 너무 작아진다면 HashMap의 리해싱이 그만큼 자주일어나고 성능 저하로 이어질 것이라는 것을 예측할 수 있다. 자바의 0.75는 많은 연구 끝에 정해진 숫자가 아닐까 생각한다.
