해시 자료구조와, 해시 충돌 그리고 Java의 HashMap 동작 방법

목차

1. 해시란?
2. 해시함수란?
3. 해시 충돌 완화 방법
4. Java에서 HashMap 동작 방법

 

 

해시(Hash)란?

해시(Hash) 구조란, key-value쌍으로 이루어진 데이터 구조로써, 해시 구조에서는 key를 이용하여 value를 빠르게 찾을 수 있다는 장점이 있습니다.

파이썬의 Dicitionary, 루비의 Hash, Java의 HashMap, C++의 unordered_map이 해시 테이블의 대표적인 예입니다.

 

 

해시 함수(Hash Function)이란?

해시 함수란, 임의 길이의 입력 값을 고정 길이의 암호화된 출력으로 변환해주는 함수입니다. key를 해시 함수에 넣어서 나오는 결과가 hash이며, 결국 해시 함수란 key를 hash로 만들어내는 함수입니다.

해시 함수는 다음과 같은 크게 세 가지의 특징을 가지고 있습니다.

1. 어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.
2. 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.(눈사태 효과)
3. 출력된 결괏값을 통해 입력값을 유추할 수 없다.

각각의 특징을 하나씩 살펴보겠습니다.

먼저 첫 번째, '어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.'라는 특징은 입력값이 짧든 길든 항상 동일한 길이의 해시값으로 출력된다는 의미입니다. 해시는 크게 MD 알고리즘 혹은 SHA 알고리즘이 있는데, 간단하게 SHA 알고리즘을 통해 첫 번째 특징을 확인해 보겠습니다.

아래는 입력값을 SHA256 알고리즘을 적용하여 해쉬값을 손쉽게 출력시켜 주는 사이트입니다.(https://www.convertstring.com/ko/Hash/SHA256)

고정된 길이의 해쉬값 출력

위 결과를 잘 보면 입력값의 길이에 상관없이 무조건 고정된 길이의 해시값을 출력하는 것을 확인할 수 있습니다. 해시 함수는 어떤 길이의 입력값이 들어오더라도 256비트의 고정된 결괏값을 출력합니다.

두 번째, '입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.(눈사태 효과)'라는 특징은 입력값이 한 글자만 바뀌어도 이전과 전혀 다른 결괏값을 출력한다는 것을 의미합니다.

전혀 다른 결과 값 출력

자세히 보면 마침표 하나만 제거했을 뿐인데 처음의 출력값과 완전히 다른 결괏값을 출력하는 것을 확인할 수 있습니다. 추가적으로 해시함수는 입력값일 동일할 경우에는 항상 같은 결괏값을 출력합니다.

세 번째, '출력된 결괏값을 통해 입력값을 유추할 수 없다'라는 특징은 말 그대로 출력값을 통해 입력값을 알아낼 수 없다는 말을 의미합니다. 위 이미지들을 살펴보았을 때 출력값을 통해 전혀 입력값을 유추할 수 없었습니다.

 

 

해시 충돌(Hash Collision)이란?

위에서 살펴본 함수에도 단점이 존재하는데, 해시 함수는 입력 값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결괏값이 나오는 경우가 있습니다. 이것을 해시 충돌(Hash Collision)이라고 표현하며, 해시 충돌이 적은 함수가 좋은 해시함수라고 불립니다.

해시 충돌 예시

위 이미지를 보면 "ARGOS"와 "MINIBEEF"라는 key값이 해시 함수를 거쳤는데 둘 다 15라는 동일한 값을 출력했습니다. 이를 해시 충돌이라고 하는데 좀 더 상세하게 알아보기 위해서 먼저 적재율(load factor)의 개념을 알아야 합니다.

적재율(load factor)이란 해시 테이의 크기에 대한 키의 개수의 비율을 뜻합니다. 즉 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이 됩니다.

해시 충돌이 발생하지 않을 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행되지만, 충돌이 발생하는 경우에는 탐색과 삭제 연산이 키의 개수인 O(K)만큼이 걸리게 됩니다.

위와 같이 HashMap은 키 집합인 정의역과, 값 집합인 공역의 대응에 해시 함수를 이용하기에 해시 충돌이 하나도 일어나지 않는 해시 함수를 만드는 것은 비둘기집 원리에 의해 불가능합니다. 따라서 해시 충돌에 대해 안전하다는 해시 함수는 '충돌이 거의 일어나지 않는다'라는 의미를 뜻합니다.

결론적으로 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우에는 비둘기집 원리에 의해 해시 충돌은 항상 존재하며, 해시 테이블의 충돌을 해결하기 위해서는 해시 충돌을 완화하는 방향으로 문제를 해결해야 합니다.

 

 

해시 충돌 완화 방법

해시 충돌을 완화하는 방법에는 크게 Open Addressing과 Separating Chaining 방법이 있습니다.

• 개방 주소법(open addressing): 해시 테이블 크기는 고정하면서 저장할 위치를 찾는다.
• 분리 연결법 (separate chaining): 해시 테이블의 크기를 유연하게 만든다.

각각의 방법에 대해 한번 알아보겠습니다.

1. 개방 주소법(open-address)

open addressing은 한 버킷 당 들어갈 수 있는 엔트리는 하나이지만 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법입니다. 즉, open addressing의 주요 목적은 저장할 엔트리를 위한 다음의 slot을 찾는 것인데 예시로 다음과 같습니다.

그림을 살펴보면, John Smith와 Sandara Dee 152번으로 동일한 값이 나옵니다. 해시 충돌이 일어난 경우인데, Sandara Dee는 152번에 덮어 씌워지지 않고, 다음 빈 버킷인 153번에 들어간 것을 확인할 수 있습니다. 다음 key인 Ted Baker는 153이라는 값이 나왔지만 이미 Sandra Dee가 저장되어 있기에 충돌이 발생해서 다음 빈 버킷인 154번에 저장되었습니다.

예시는 무조건 한 칸씩 찾는 방법을 예로 들었지만 비어있는 칸을 찾아가기 위해서 아래와 같은 다양한 방법들이 존재합니다.

• Linear probing(선형 탐사법)
• Quadratic probing(제곱 탐사법)
• Dobule hashing(이중 해싱)

Linear Probing(선형 탐사법)

말 그대로 가장 간단하게 선형으로 순차적 검색을 하는 방법입니다. 해시 함수로 나온 해시 값(index)에 이미 다른 값이 저장되어 있다면, 해당 해시값에서 고정된 폭만큼 옮겨 다음 빈칸을 찾아가는 방법입니다.

위 이미지를 보면 52라는 값을 해싱하여 해시값 2에 접근했지만 이미 존재하여 충돌이 났음을 알 수 있습니다. 따라서 임의의 고정된 크기인 한 칸씩 옮겨서 빈칸을 찾아가며 최종적으로 6에 저장되는 것을 확인할 수 있습니다.

이 경우에는 간단하지만 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화(primary clustering) 문제가 발생할 수 있습니다. 위 이미지만 해도 2~6까지 데이터가 모여있는 것을 확인할 수 있는데, 모든 키가 2라는 값으로 해시값이 나올 경우 군집화 된 값들을 순차적으로 방문할 텐데 해시 성능이 크게 저하될 수 있습니다.

따라서 Linear Probing(선형 탐사법)은 해시 충돌이 해시 값 전체에 균등하게 발생할 때 유용한 방법입니다.

Quadratic probing(제곱 탐사법)

제곱 탐사법은 위의 선형 탐사법과 동일한데, 탐사 폭이 고정된 값이 아니라 제곱으로 늘어나는 점에 있어 차이가 있습니다. 즉, 빈 버킷의 slot을 찾기 위해 고정된 값이 아닌 2^1, 2^2, 2^3.... 의 방식으로 이동해서 빈칸을 찾습니다.

제곱 탐사법을 이용한 경우 데이터의 밀집도가 선형 탐사법보다 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 가능성이 적습니다. 하지만 선형 탐사법보다는 캐시의 성능이 떨어져서 속도의 문제가 발생합니다. 이는 배열의 크기가 커지게 되면서 L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문입니다.

Dobule hashing(이중 해싱)

이중해싱법 또는 재해싱은 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법입니다. 이 방법은 항목들을 이전 방법들보다 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적인 방법이라 할 수 있습니다.

하나는 처음의 key를 저장할 index를 찾기 위한 것이고, 나머지 하나는 충돌 발생 시 저장할 index를 찾기 위한 것이며, 충돌 발생 시 저장할 index를 찾기 위한 해시 함수는 첫 번째 해시 함수와 달라야 합니다.

Dobule hashing(이중 해싱)

이중 해싱법은 충돌의 발생 가능성은 가장 적으나, 캐시의 성능은 Linear Probing, Quadratic Probing과 비교했을 때 가장 좋지 않으며, 추가적인 해시 연산이 들어가기에 가장 많은 연산량을 요구한다는 단점이 있습니다.

개방 주소법(open-address) 정리

탐사 방식에 따라 open-addressing 해시의 성능이 달라지지만, 가장 치명적인 영향을 미치는 요소는 바로 해쉬 테이블의 적재율인 load factor(전체 슬롯에서 사용 중인 슬롯 비율)입니다. Load Factor가 100%로 증가할수록 데이터를 찾거나 삽입하기 위해 필요한 탐사 횟수는 비약적으로 증가합니다. 일단 테이블이 꽉 차게 되면 probing이 실패하여 끝나버리기도 하는데, 아래 표는 Load Factor에 따른 평균 성공 탐색수와 실패수를 보여줍니다.(http://egloos.zum.com/sweeper/v/925740)

open - addressing 성능 정리

위 표를 잘 보면 아무리 좋은 해시 함수를 쓰더라도 일반적으로 Load Factor는 80% 이내까지만 좋은 성능을 보여주는 것을 알 수 있습니다. 특히 Linear probing 방식이 Load Factor가 높을수록 가장 급격하게 성능 저하가 발생하는 것을 확인할 수 있습니다.

따라서 Load Factor가 임계점을 넘어 큰 경우의 성능은 double hashing > quadratic > linear의 순서로 나타낼 수 있습니다.

 

2. 분리 연결법 (separate chaining)

분리 연결법은 개방 주소법(open-addressing)과는 달리 한 버킷(슬롯) 당 들어갈 수 있는 엔트리의 수에 제한을 두지 않습니다. 이때 버킷에는 링크드 리스트(linked list)나 트리(tree)를 사용합니다.(조금 뒤에 상세하게 설명하겠지만 자바에서는 둘 다 사용합니다.)

분리 연결법 (separate chaining)

위 이미지를 잘 보면 동일한 값들은 리스트로 연결되어 저장이 되는 것을 확인할 수 있습니다. 따라서 해시 충돌이 일어나더라도 리스트로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있습니다. 하지만 open addressing 방법과 비교했을 때 추가적인 메모리 공간이 필요하며, 테이블의 적재율(Load Factor)에 따라 선형적으로 성능이 저하됩니다.

따라서 적재율이 작을 경우 즉, 데이터가 적은 경우에는 open addressing 방식이 평균적으로 더 빠릅니다.

위의 2가지 방법 이외에도 해시 테이블의 적재율이 높아진 경우에는 크기가 더 큰 새로운 테이블을 만들어서 기존 데이터를 옮겨서 사용하는 방법이 있습니다. 또한 분리 연결법을 사용했을 경우엔 재해싱을 통해서 너무 길어진 리스트의 길이를 나누어서 다시 저장할 수도 있습니다.

 

언어별 해시 충돌 완화 방법

언어	방식
C++	개별 체이닝
Java	개별 체이닝
Go	개별 체이닝
Ruby	오픈 어드레싱
Python	오픈 어드레싱

 

Java에서 HashMap 동작 방법

여기서부터는 네이버 d2의 문서를 보고 간단하게 정리한 내용입니다. 자세히 보고 싶은 해당 링크를 통해 확인해주시면 감사하겠습니다.

먼저 자바에는 HashMap과 HashTable이 존재합니다. 둘 다 Java에서 제공하는 API로써 둘 다 Map 인터페이스를 구현하고 있기 때문에 제공하는 기능은 같습니다. 하지만 HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있습니다. 또한 HashTable은 성능의 개선이 더 이상 일어나지 않지만, HashMap은 지속적으로 개선이 되고 있습니다.

Java HashMap에서 사용하는 방식은 Separate Channing입니다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 매우 빈번하게 호출될 수 있기 때문입니다. 또한 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리기 때문입니다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문입니다.(적재율)

반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 '조정'할 수 있다면 Worst Case에 가까운 일이 발생하는 것을 줄일 수 있습니다.

 

Java 7과 Java 8의 HashMap에서의 Separate Chaining

Java 2부터 Java 7까지의 HashMap에서 Separate Chaining 구현 코드는 조금씩 다르지만, 구현 알고리즘 자체는 같았습니다. 하지만 Java 8부터 변경되었는데 이전까지는 Separate Chaining에서 링크드 리스트를 고정적으로 사용했지만 Java 8 이후부터는 데이터의 개수가 많아지면 트리를 사용하도록 변경되었습니다.

링크드 리스트를 사용했을 때는 조회에 대한 시간복잡도가 O(N/M)을 보여줬지만 트리를 사용하게 되면 O(log N/M)의 복잡도를 가지게 됩니다. 따라서 데이터의 개수가 일정 이상일 때에는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점을 가지게 됩니다. 물론 고정적으로 트리를 사용하게끔 구현되어 있는 것은 아닙니다. 링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수입니다.

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

위 코드를 보면 알 수 있듯이, Java 8 HashMap에서는 상수 형태로 기준을 정하고 있습니다. 즉 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경합니다.

만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경하는데, 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문입니다. 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문입니다. 이때 사용하는 트리는 Red-Black Tree입니다.

따라서 Java HashMap에서는 해시 충돌을 방지하기 위하여 Separate Chaining과 보조 해시 함수를 사용하며, Java 8에서는 Separate Chaining에서 링크드 리스트 대신 트리를 사용하기도 한다는 것으로 정리할 수 있겠습니다.

 

 

참고

1. https://steemit.com/kr/@yahweh87/2
2. https://ai-rtistic.com/2022/01/29/data-structure-hash/
3. http://egloos.zum.com/sweeper/v/925740
4. https://d2.naver.com/helloworld/831311