HashMap는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Searching 하는데 데이터 고유의 인덱스로 접근하게 되므로 Time Complexity가 O(1)이 되는 것이다. 그리고 데이터의 삽입과 삭제 시 기존 데이터를 밀어내거나 다시 채우는 작업이 필요없도록 '특별한 알고리즘'을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없으므로 추가적인 데이터의 이동이 없다.
`특별한 알고리즘`이란 것을 통해 고유한 인덱스 값을 설정하는 것이 중요해보인다.
위에서 언급한 특별한 알고리즘을 해시 메소드(Hash Method) 또는 해시 함수(Hash Function)라고 하고 이 메소드에 의해 반환된 데이터의 고유의 숫자 값을 hashcode라고 한다. Java에서는 Object 클래스의 hashCode()라는 메소드를 이용하여 모든 객체의 hashcode 값을 쉽게 구할 수 있다.
hash 메소드를 구현하는 가장 간단한 방법은 나머지 연산자를 이용하는 것이다. 저장할 데이터의 값을 저장할 hash table의 크기로 나누고 나머지 연산 결과를 해당 데이터의 인덱스로 사용하는 것이다. 하지만 이렇게 하면 문제점이 발생한다. 다음 상황을 보자.
만약 3의 배수로 이루어진 데이터 9개를 저장한다고 가정해보자.
저장하려는 데이터 : 3, 6, 9, 12, 15, 18, 21, 24, 27
hashcode 값 계산 :
3 % 9 == 3
6 % 9 == 6
9 % 9 == 0
12 % 9 == 3
15 % 9 == 6
18 % 9 == 0
21 % 9 == 3
24 % 9 == 6
27 % 9 == 0
계산 결과 hashcode 값이 0,3,6 으로 집중되고 있다. 이렇게 되면 같은 index 로 접근하게 되는 value가 많아져 데이터를 저장할 수 없게 되는 충돌현상이 발생한다. 이를 Collision 이라고 한다.
이런 충돌을 최소화 하기 위한 가장 간단한 방법은 나머지 연산의 값이 중복되지 않도록 테이블의 크기를 소수(prime number)로 만드는 것이다. 위와 동일한 경우, 저장하려는 데이터의 크기가 9이므로 9보다 큰 소수인 11로 나머지 연산을 해보자.
hashcode 값 계산 :
3 % 11 == 3
6 % 11 == 6
9 % 11 == 9
12 % 11 == 1
15 % 11 == 4
18 % 11 == 7
21 % 11 == 10
24 % 11 == 2
27 % 11 == 5
중복이 깨끗이 사라진 것을 확인할 수 있다. 하지만 이걸로 모든 것이 해결된 것일까? 위의 과정에서 데이터의 성질이 달라져 다른 값이 들어올 수 있게 된 경우는 어떨까. 예를 들면 26이라는 데이터를 추가적으로 저장해야 한다면? 데이터의 크기는 10이 되므로 10보다 큰 소수 11로 나머지 연산자를 수행해준다.
26 % 11 == 4
다시 중복이 발생하였다. 바로 Collision이 발생한 것이다. Hash Table의 크기를 소수로 만드는 것은 충돌을 줄일 수는 있겠지만 원천적으로 해결해주지는 못한다.
충돌이 많아질 수록 Searching에 필요한 Time Complexity가 O(1)에서 O(n)에 가까워진다. 어설픈 해쉬 함수는 해시를 해시 답게 사용하지 못하도록 한다. 좋은 해쉬 함수를 선택하는 것은 해쉬 테이블의 성능 향상에 필수적인 것이다.
두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미)되면 같은 곳에 저장할 수 없게 된다.(Collision) 따라서 해싱(hashing)된 인덱스에 이미 다른 값이 들어 있다면 데이터를 저장할 다른 위치를 찾은 뒤에야 저장할 수 있는 것이다. 따라서 충돌 해결은 필수이며 그 방법들에 대해 알아보자.
기본적인 두 가지 방법부터 알아보자. 해시 충돌을 해결하기 위한 다양한 자료가 있지만, 다음 두 가지 방법을 응용한 방법들이기 때문이다.
1. Open Address 방식 (개방주소법)
해시 충돌이 발생하면, 즉 삽입하려는 해시 버킷이 이미 사용 중인 경우, '다른' 해시 버킷에 해당 자료를 삽입하는 방식이다. (버킷(bucket)이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.) 다른? 이런 애매모호한 표현은 개발자에게 어울리지 않는다. 다른 해시 버킷이란 어떤 해시 버킷을 말하는 것인가
공개 주소 방식이라고도 불리는 이 알고리즘은 Collision이 발생하면 데이터를 저장할 장소, 즉 다른 해시 버킷을 찾아 헤맨다. 이 과정에서도 여러 방법들이 존재하는데, 다음 세 가지에 대해 간단히 알아보고 넘어가자.
1) Linear Probing
순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다. Worst Case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.
2) Quadratic probing
2차 함수를 이용해 탐색할 위치를 찾는다.
3) Double hashing probing
하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구한다.
2. Seperate Chaining 방식 (분리 연결법)
참고로 Java 7에서는 Separate Chaining 방식을 사용하여 HashMap을 구현하고 있다.
Why?HashMap의 특징상 remove( )메소드가 빈번하게 일어날 수 있는데, 데이터를 삭제할 때 Open Address 방식은 처리가 효율적이기 어렵다. 또한 저장된 Key-Value 쌍의 개수가 일정 개수 이상 많아지만, 보통 Seperate Chaining 방식에 비해 Open Address 방식이 느리다.
연결 리스트를 사용하는 방식(Linked List)
각각의 버킷들을 연결리스트(Linked List)로 만들어 Collision이 발생하면 해당 버킷의 list에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다.
한 가지 또다른 장점은 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다는 것이다.
일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case or Worst Case에 가까워 지는 것을 줄일 수 있다. 보조 해시 함수에 대해서는 다음 글을 확인하면 좋겠다. >> 보조 해시 함수 >>
Tree를 사용하는 방식(Red-Black Tree)
기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 트리는 기본적으로 메모리 사용량이 많고 데이터 개수가 적을 때 Worst Case를 살펴보면 트리와 연결 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 연결 리스트를 사용한다.
데이터가 적다는 것은 얼마나 적다는 것을 의미하는가?
앞에서 말했듯이 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다. 이 키-값 쌍의 개수가 6개, 8개를 기준으로 결정한다.(응?) 기준이 두 개 인것이 이상하게 느껴질 수 있다. 7은 어디로 갔는가?
결론부터 말하자면 연결 리스트의 기준과 트리의 기준을 6과 8로 잡은 것은 변경하는데 소요되는 비용을 줄이기 위함이다.
한 가지 상황을 가정해보자.
해시버킷에 6개의 key-value 쌍이 들어있었다. 그리고 하나의 값이 추가되었다. 만약 기준이 6과 7이라면 자료구조를 연결 리스트에서 트리로 변경해야 한다. 그러다 바로 하나의 값이 삭제된다면 다시 트리에서 연결 리스트로 자료구조를 변경해야 한다.
각각 자료구조로 넘어가는 기준이 1이라면 Switching 비용이 너무 많이 필요하게 되는 것이다. 그래서 2라는 여유를 남겨두고 기준을 잡아준 것이다. 따라서 데이터의 개수가 6개에서 7개로 증가했을 때는 연결 리스트의 자료구조를 취하고 있을 것이고 8개에서 7개로 감소했을 때는 트리의 자료구조를 취하고 있을 것이다. 참고로 Java 8을 구현하는데 사용하는 트리는 Red-Black Tree이다. RBT를 사용하는 이유는 RBT에 대한 포스팅을 참고하면 되겠다. >> Red-Black Tree에 대해서 >>
해시 버킷 동적 확장(Resize)
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다. 그래서 HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
또 애매모호한 '일정 개수 이상'이라는 표현이 등장했다. 해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor로 HashMap의 생성자에서 지정할 수도 있다.
Reference>>
end
'Dev.Basic > 자료구조&알고리즘' 카테고리의 다른 글
| [DataStructure] Graph라는 자료구조에 대해서 (0) | 2016.12.20 |
|---|---|
| Sorting Algorithm을 비판적으로 바라보자. (0) | 2016.12.10 |
| [Sorting] 5. Non-Comparison Sorting - Counting Sort, Radix Sort (0) | 2016.11.21 |
| [Sorting] 4. Heap, Heapify, Heap Sort (0) | 2016.11.20 |
| [Sorting] 3. Quick Sort (0) | 2016.11.19 |
