[기본 시리즈] 해시 테이블과 해시 충돌 그리고 JAVA의 HashMap

해싱의 기본 해시 함수

해시 함수는 입력한 Key를 해시 테이블에 적절한 index로 Mapping 해주는 함수를 말합니다. 해시 함수를 어떻게 구현하느냐에 따라서 해싱 성능이 좌지우지 될 수 있습니다.

Java11 HashMap 클래스의 hash function

 굉장히 방대한 데이터를 저장해야 하고 충돌에 민감한 HashMap을 구현해야 한다면 당연히 해시 함수 최적화에 노력을 기울여야겠죠. 하지만 아무리 노력해도 해시 함수는 Pigeonhole principle에 의해서 해시 충돌이 발생할 수 밖에 없습니다.

해시 충돌 (Collision)

해시 충돌은 해시 값의 충돌을 의미합니다. 해시 함수를 통해서 Key 값을 해시 테이블에 맵핑하는데 만약에 해싱 결과가 똑같다면 어떻게 처리해야 할까요?

Seperate Chaining

Seperate Chaining은 Closed Addressing 방법이라고도 하며 Hash Collision을 해결하기 위하여 해시 테이블에 추가적인 메모리를 사용하는 방식입니다. 대표적인 예시로 연결 리스트를 이용하곤 합니다. 연결 리스트를 활용할 경우 충돌이 발생한 Key 값들은 연결 리스트에 차례대로 저장합니다. 쉽고 직관적인 방법이죠.

그런데 HashMap은 O(1)의 탐색 시간 복잡도를 지원하기 위하여 고려된 자료 구조입니다. 만약 연결 리스트를 활용하여 Collision을 해결하려고 한다면 최악의 경우 연결 리스트에 최대 N개의 Key가 맵핑 될 수 있으며 시간 복잡도는 당연히 증가하게 됩니다.

 

그래서 최신 Java의 HashMap은 LinkedList가 아닌 Self balancing BST를 이용하여 최악의 경우에도 O(logN)의 탐색 시간 복잡도를 보장하도록 되어있습니다.

Seperate Chaining
장점	구현이 간단하다
	해시 테이블이 가득찰 일이 없다
	해시 함수와 부하 계수에 덜 민감하다
	키 삽입과 삭제의 빈도를 정확히 알 수 없는 경우에 주로 사용한다
단점	연결 리스트의 경우 캐싱 성능이 좋지 않다. (추가적인 탐색이 필요하기 때문이다) (인덱싱이 가능한 동적 Array를 사용하면 캐싱 성능을 올릴 수 있다)
	해시 테이블의 공간이 낭비된다
	체인이 길어지면 탐색 시간 복잡도가 증가한다
	추가적인 메모리가 필요하다

Open Addressing 

Open Addressing 방법은 충돌이 발생한 해시 값이 아닌 다른 곳에 Key를 맵핑하는 방법입니다. 세 가지 방식이 있습니다. 

- 1. Linear Probing

선형 탐색은 충돌이 발생한 해시에서 순차적으로 충돌이 발생하지 않는 해시를 찾는 방식입니다. 예를 들어 해시 값 1에서 충돌이 발생했다면 해시 값 2를 확인하고 충돌이 발생하지 않는다면 Key를 맵핑합니다. 단점은 새로운 해시 값을 찾는 시간이 충돌이 발생할수록 증가한다는 것과 클러스터링(군집화) 문제가 있습니다.

If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S 
..................................................
..................................................

- 2. Quadratic Probing

선형 탐색과 다르게 보통 제곱 값을 더하는 형태로 해시 값을 증가시키며 탐색합니다. (물론 범위 안에서 탐색이 가능하도록 모듈러 연산이 포함됩니다) 이 방식은 선형 탐색의 클러스터링 문제를 해결할 수 있습니다.

let hash(x) be the slot index computed using hash function.  
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S
..................................................
..................................................

- 3. Double Hashing

이중 탐색은 두 개의 해시 함수를 사용하여 클러스터링을 최소화하는 방식입니다. 

let hash(x) be the slot index computed using hash function.  
If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S
..................................................
..................................................

	Linear Probing	Quadratic Probing	Double Hashing
장점	캐시 성능이 뛰어나다	Linear 방식에 비해서 클러스터링 회피에 이점이 있다	클러스터링 문제가 거의 없다
단점	클러스터링 문제가 있다	Linear 방식에 비해서 캐시 성능이 떨어진다	캐시 성능이 떨어진다. 해싱에 더 많은 시간이 걸린다

비둘기 집의 한계

비둘기 집이 언젠가는 가득찰 수 밖에 없습니다. 이를 피하려면 적절한 시점에 비둘기 집을 늘리는 방법 밖에 없습니다.

복잡성

HashMap은 상수 시간 복잡도 안에 저장, 삭제, 탐색을 지원하는 것을 목표로하는 자료구조입니다. 그런데 데이터의 수가 증가하고 HashMap의 크기가 고정되면 자연스럽게 Collision이 발생하고 시간 복잡도가 증가할 것입니다. 따라서 낮은 복잡성을 유지하기 위한 유일한 해결책은 HashMap의 크기를 확장시키는 것이며 HashMap의 확장 시점을 결정하는 요소로는 HashMap의 현재 용량, 부하 계수, 임계 값이 있습니다.

용량 설정과 부하 계수 설정

HashMap을 사용한다고 가정하고 초기 용량을 16, 부하 계수를 0.75로 설정하겠습니다. 부하 계수는 무엇이냐면 HashMap의 용량을 늘릴 시점을 결정하는데 도움을 주는 장치입니다. 부하 계수를 설정하면 HashMap의 용량으로부터 임계값을 계산할 수 있습니다. 임계 값은 비둘기가 얼마나 들어왔을 때 비둘기 집을 늘리기 시작할 것이냐에 대한 기준이라고 볼 수 있습니다. 현재 용량과 부하 계수를 곱하면 임계값을 얻을 수 있고, 현재 임계값은 16 * 0.75 = 12 이므로 데이터가 12개 들어왔을 때 HashMap의 용량을 늘리면 됩니다.

확장과 재해싱

Java HashMap을 예로 들자면 임계 값을 초과했을 경우 맵의 크기가 두 배가 됩니다. 그런데 용량이 증가하면 기존의 데이터를 재해싱하여 새로운 공간에 균등하게 배포해야 합니다. 이를 재해싱이라고 하며 가장 큰 비용이 발생하는 작업입니다. 그렇기 때문에 큰 용량의 데이터가 들어올 것으로 예상된다면 처음부터 큰 HashMap을 생성하는 것이 차라리 효율적입니다.