자바의 Collection 인터페이스 중에서 대표적인 것이 Map 인터페이스입니다.
Map 인터페이스는 여러 구현 클래스를 갖는데, 대표적인 것이 HashMap 클래스와 HashTable 클래스입니다.
그리고 이 두 클래스를 이해하기 위해서는 우선 해시 자료구조에 대해 알아야 합니다.
1) 해시 자료구조란 무엇인가?
- 해시 자료구조의 구성 요소는 크게 해시 함수와 해시 테이블입니다.
해시 자료구조는 key, value 셋을 저장하는데,
key를 해시 함수로 계산해서 해시값을 만들어내고,
그 해시 값에 해당하는 해시 테이블의 위치에 value를 저장합니다.
- 해시 자료구조의 장점은 값의 저장이나 검색, 삭제를 이론상으로 시간 복잡도 O(1)에 할 수 있다는 점입니다.
다만, 실제로는 시간 복잡도가 O(1)이 아닌데, 이는 해시 충돌(hash collision)이 발생하기 때문입니다.
1-1) 해시 충돌(hash collision)이란 무엇인가?
- 해시 충돌이란 두 개의 다른 key 값이 동일한 해시 값을 갖게 되어,
해시 테이블의 동일한 위치를 지정하게 되는 것을 의미합니다.
이러한 경우 저장될 value를 식별하기 위해 추가적인 방식이 필요합니다.
그것은 대표적으로 Open Addressing과 Seperate Chaining이 있습니다.
1-2) Open Addressing이란?
- Open Addressing 이란 해시 충돌이 발생했을 때, '빈 주소'를 찾아나가는 방식입니다.
그리고 이 방식에는 대표적으로 2가지가 있는데, 바로 Linear Probing과 Quadratic Probing입니다.
Linear Probing은 해시 충돌이 발생하면 한 칸씩 이동하면서 빈 주소를 찾아나가는 방식이고,
Quadratic Probing은 해시 충돌이 발생하면 1^2, 2^2, ...과 같이 이동하면서 빈 주소를 찾아나가는 방식입니다.
1-3) Seperate Chaining이란?
- Seperate Chaining이란 독립적인 자료구조를 만들어서 해시 충돌을 해결하는 방식입니다.
자료구조는 대표적으로 LinkedList를 사용합니다.
Seperate Chaining은 해시 충돌이 발생하면, 해당 위치에 연결된 링크드 리스트에 value를 차례대로 저장합니다.
이와 같이 해시 충돌이 발생하면 Open Addressing이나 Seperate Chaining 방식 등을 통해 추가적인 탐색이 필요합니다. 이러한 추가적인 탐색 시간은 해시 자료구조의 성능을 떨어뜨리는 요인이 됩니다.
따라서 해시 자료구조를 이용할때는 '어떻게 해시 충돌과 그로 인한 추가적인 탐색 시간을 최소화할 것인가' 가 중요한 문제입니다.
2) HashMap 클래스와 HashTable 클래스
- Hash 자료구조에 대해서 알아봤으니, 다시 HashMap클래스와 HashTable 클래스로 돌아와봅니다.
HashTable 클래스는 JDK 1.0부터, HashMap 클래스는 자바 2부터 제공되었고, 둘 다 Map 인터페이스를 기반으로
하고 있기 때문에 제공하는 기능은 같습니다.
다만, 차이점은 HashTable 클래스는 기능에 변화가 없었던 반면, HashMap 클래스는 지속적으로 성능 개선이 일어났다는 점입니다.
- HashMap 클래스의 성능 그리고 성능 개선의 주요 포인트는 3가지 정도로 요약할 수 있습니다.
(1) HashMap 클래스는 해시 충돌 발생 시 Separate Chaining 방식을 사용
(2) HashMap 클래스는 Separate Chaining 방식 사용 시,
자바 7까지는 Linked List를 사용했으나, 자바 8부터는 Linked List와 Tree를 같이 사용
(3) HashMap 클래스는 해시 충돌을 줄이기 위해 보조 해시 함수를 사용
각각에 대해서 좀 더 자세히 알아 보겠습니다.
2-1) HashMap 클래스는 해시 충돌 발생 시 Separate Chaining 방식을 사용
- 해시 충돌을 해결하는데는 Open Addressing 방식과 Separate Chaining 방식이 있는데,
이 중에서 HashMap 클래스는 Seperate Chaining 방식을 사용합니다.
그 이유는 다음과 같습니다.
(1) HashMap 클래스는 remove 연산이 자주 발생하는데,
Open Addressing 방식은 remove 연산을 다루는데 효율적이지 않습니다.
예를 들어, hash(x) = hash(y) = hash(z) = i 라고 가정합시다.
이 경우 해시 충돌이 발생하기 때문에, Open Addressing 방식의 Linear Probing을 사용하면
table[i] = x, table[i+1] = y, table[i+2] = z가 저장됩니다.
이 때, 만약 i번째 위치의 x값을 remove한다면 table[i] = NULL이 됩니다.
그리고 z값의 위치를 찾기 위해서 hash(z) = i 로 table[i]에 접근하면
z가 아닌 NULL이 반환됩니다.
즉, z값의 위치를 찾기 위해서는 추가적인 작업이 필요합니다.
(2) Open Addressing 방식은 저장 공간(ex) 배열))의 크기가 작을 때는, 캐시 효율이 좋습니다.
하지만 저장 공간의 크기가 커질수록 L1, L2 캐시 적중률이 낮아지기 때문에, 효율이 떨어집니다.
따라서 HashMap 클래스는 Seperate Chaining 방식을 사용해서 구현됩니다.
2-2) HashMap 클래스는 Separate Chaining 방식 사용 시,
자바 7까지는 Linked List를 사용했으나, 자바 8부터는 Linked List와 Tree를 같이 사용
- 자바 7까지 HashMap은 Separate Chaining 방식을 Linked List를 사용해서 구현했습니다.
반면, 자바 8부터는 기존의 Linked List에 Tree를 추가적으로 제공합니다.
여기서 Tree는 Red-black Tree입니다.
Linked List는 검색 시 시간 복잡도가 O(N)이고,
Red-black Tree는 Self-balancing Tree이므로, 최악의 경우 O(logN)을 보장합니다.
그리고 이는 데이터의 개수가 늘어날 수록 더 큰 성능 차이로 이어집니다.
여기서 재밌는 점은 Linked List와 Tree가 동적으로 변경된다는 점입니다.
하나의 해시 버킷에 저장된 데이터의 개수가 6개 이하일 때는 Linked List를 사용하고,
8개 이상일 때 Tree로 변경됩니다.
6개 이하일 때 Linked List를 사용하는 이유는 데이터의 크기가 작아서 성능의 차이가 크지 않기 때문입니다.
그리고 6개와 8개라는 gap을 둔 이유는 한 개 단위로 차이를 두면 insert, remove가 자주 일어나는 경우
동적인 변경이 자주 일어나서 성능 저하로 이어질 수 있기 때문입니다.
2-3) HashMap 클래스는 해시 충돌을 줄이기 위해 보조 해시 함수를 사용
- 해시 함수는 일반적으로 int index = x.hashCode() % M 와 같이 나타낼 수 있습니다.
그리고 M이 소수일 때, 가장 균등하게 해시 값이 분포됩니다.
그런데 M값이 소수가 아니므로, 해시 값을 보다 균등하게 하기 위한 추가적인 작업이 필요하고,
이를 위해 보조 해시 함수를 사용합니다.
보조 해시 함수의 목적은 키의 해시 값을 변경하여 해시 충돌 가능성을 낮추는 것입니다.
자바 7까지는 다음과 같은 보조 해시 함수를 사용했습니다.
final int hash(Object k) {
// Java 7부터는 JRE를 실행할 때, 데이터 개수가 일정 이상이면
// String 객체에 대해서 JVM에서 제공하는 별도의 옵션으로
// 해시 함수를 사용하도록 할 수 있다.
// 만약 이 옵션을 사용하지 않으면 hashSeed의 값은 0이다.
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 해시 버킷의 개수가 2a이기 때문에 해시 값의 a비트 값만을
// 해시 버킷의 인덱스로 사용한다. 따라서 상위 비트의 값이
// 해시 버킷의 인덱스 값을 결정할 때 반영될 수 있도록
// shift 연산과 XOR 연산을 사용하여, 원래의 해시 값이 a비트 내에서
// 최대한 값이 겹치지 않고 구별되게 한다.
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
자바 8부터는 다음과 같은 보조 해시 함수를 사용합니다.
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
- 보조 해시 함수가 16비트 XOR 연산을 하는 것으로 매우 간단하게 바뀌었습니다.
이렇게 간단하게 바뀐데에는 2가지 이유가 있습니다.
첫째는, 자바 7과 달리 자바 8에서는 트리가 추가적으로 도입 되어, 해시 충돌 시 성능에 대한 이슈가
완화되었기 때문이고,
둘째는, 최근의 해시 함수는 균등 분포로 만들어지는 경우가 많기 때문입니다.
두 번째 이유가 더 크게 작용하여 보조 해시 함수의 구현이 변경되었습니다.
3) 결론
- HashMap 클래스의 성능이 개선되어 온 역사를 살펴보면,
HashMap 클래스에 대한 이해가 깊어지고,
자료구조에서 성능이 갖는 의미에 대해 생각해볼 수 있습니다.
참고
알고리즘 ) Red-Black Tree (tistory.com)
algorithm - Hash Table: Why deletion is difficult in open addressing scheme - Stack Overflow
Java HashMap은 어떻게 동작하는가? (naver.com)
Hashing | Set 2 (Separate Chaining) - GeeksforGeeks
'Java' 카테고리의 다른 글
| 자바 int와 long 자료형 (0) | 2022.07.31 |
|---|---|
| Java 8 람다 표현식 (0) | 2022.07.21 |
| Object 클래스 (0) | 2022.06.14 |
| Collection 인터페이스 (0) | 2022.05.30 |
| Serializable (0) | 2022.05.29 |
