[Java] HashMap, HashSet 이란? - (3) HashMap이란?

드디어 원래 목적이었던 HashMap, HashSet에 대해 작성한다.

하지만, 글이 또다시 길어져 HashMap에 대해서만 먼저 작성한다....

네이버 D2 블로그에서 HashMap에 관한 글을 발견하여 해당 글을 토대로 작성했다.

아래 두 글을 순서대로 읽고 오면 더욱 이해하기 쉽다.


[Java][자료구조] HashMap, HashSet 이란? - (1) collections란?

[Java][자료구조] HashMap, HashSet 이란? - (1) collections란?

[Java][자료구조] HashMap, HashSet 이란? - (2) Set, Map 이란?

[Java][자료구조] HashMap, HashSet 이란? - (2) Set, Map 이란?

 

---

 

HashMap 이란?

개념

단어 뜻 그대로, 이전 글에서 알아보았듯이,
Map 인터페이스의 구현체지만 Hash(해시)를 사용하여 데이터를 저장한다.

좀 더 자세히 정의하자면 아래와 같다.

'Key에 대한 Hash 값을 사용하여 Value를 저장하고 조회하며,
Key-Value 쌍의 개수에 따라 동적으로 크기가 증가하는 Associate Array (Associate Array의 예 -> Map, Dictionary, etc.)'

당연히 중복된 Key 값은 허용되지 않고, 데이터를 넣은 순서를 유지하지 않는다.
(Map 인터페이스를 구현한 또다른 구현체인 TreeMap 같은 경우는 그 순서를 유지한다)

또한 기본적으로 동기화(synchronized)가 되지 않지만,
colleciton framework가 메서드를 제공하므로 이를 이용해서 HashMap을 동기화시켜 멀티 쓰레드 환경에서 사용 가능하다.

 

HashMap vs HashTable

HashMap과 함께 자주 언급되는 HashTable은 Map 인터페이스를 구현하고 있기 때문에 위와 똑같은 기능을 한다.

하지만 HashMap은 Additional Hash Function(보조 해시 함수)를 사용하기 때문에
보조 해시 함수를 사용하지 않는 HashTable에 비해 해시 충돌이 덜 발생할 수 있어, 상대적으로 성능상 이점이 있다.

이러한 보조 해시 함수 뿐만 아니더라도,
현재의 HashTable은 최초 등장 때와 거의 차이가 없지만 HashMap은 지속적으로 개선되고 있다.

아래와 같은 HashTable과 HashMap의 선언부만 보더라도 Associative Array를 지칭하기 위해
HashTable에서는 Dictionary를 사용하고,
HashMap에서는 Map을 사용하고 있다.

 

public class 8ccce55530bc3477c678dd9921b60f3e.gifHashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { public class 928b3cc3fe40d69cd06cbe7f5f3767f8.gifHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

 

Java HashMap의 충돌 처리 방식

우선 Hash(해시)에 대해 다시 생각해보자.

해시는 임의의 길이의 임의의 데이터가 입력으로 들어오면 (해시 함수에 따라) 항상 일정한 길이의 데이터를 출력한다.

그러한 과정에서 다른 입력 데이터가 해시 함수로 들어가도 같은 출력값(해시 값)이 나올 수 있는데,
이러한 것을 '충돌'이라고 한다.

그럼 HashMap에서 이러한 해시를 사용하는 부분은 어딜까?

HashMap도 결국 데이터를 담는 '공간'이기 때문에,
Key-Value 형태의 데이터를 넣는 과정(put() 메서드)이나 조회하는 과정(get() 메서드) 등에서
Key 값을 결정하기 위해 hashCode() 라는 메서드를 사용하게 되는데,
바로 이 hashCode() 에서 해시를 사용하게 된다.

[자료구조][알고리즘] 해시(Hash)란? - (2) 해시 테이블에서 충돌 처리 방식 에서 해시 충돌과 처리 방식에 대해 알아보았듯이,
HashMap은 해시 충돌이 발생하면 Open Addressing과 Seperate Chaining 방법 중 Seperate Chaining 방법을 사용한다.

그 이유는 위 링크 글의 "Open Addressing vs Seperate Chaining" 파트를 참고하면 된다.

 

Java 8 HashMap에서의 Seperate Chaining

Java 7까지의 HashMap에서 Seperate Chaining 구현 알고리즘은 아래와 같았다.

'만약 객체의 해시 함수 값이 균등 분포(uniform distribution) 상태라면, get() 메서드 호출에 대한 기대값은 E(N/M)이다.'

하지만 Java 8에서는 이보다 더 나은 E(log N/M)을 보장한다.
이유는, Seperate Chaining에서 기존에 사용하던 Linked List(링크드 리스트) 대신 Tree(트리)를 사용하기 때문이다.

데이터의 개수가 많아질수록 N/M과 log N/M의 차이는 어마어마한데,
심지어 실제로는 해시 함수 값은 균등 분포가 아니며,
만약 균등 분포를 따른다고 하더라도 생일 문제(birthday problem, 이전 글 설명 참고) 현상으로 인해

일부 해시 버킷 몇 개에 데이터가 집중될 가능성이 높다.

그래서 데이터의 개수가 일정 기준 이상일 때는 링크드 리스트 대신 트리를 사용하는 것이 성능상의 이점이 있다.

Java 8 HashMap에서는 하나의 해시 버킷에 할당된 Key-Value 쌍의 개수로 링크드 리스트를 트리로 변경하는데,
그 기준은 상수 형태(8개)로 하고 있다.

 

만약 버킷의 데이터가 삭제되어 6개가 되면 다시 링크드 리스트로 변경한다.

그 이유는,
트리는 링크드 리스트보다 메모리 사용량이 많고,
데이터 개수가 적을 때는 그 둘의 Worst Case 수행 시간 차이 비교가 의미 없기 때문이다.

그렇다면 왜 8개와 6개로, 두 개의 차이를 두었을까?

만약 한 개라면,
어떠한 Key-Value 쌍이 반복되어 삽입/삭제되는 경우,
불필요하게 트리와 링크드 리스트를 왔다 갔다 변경하는 일이 반복되어 오히려 성능 저하가 발생할 수 있기 때문이다.

그럼 수많은 트리 구조 중 어떤 트리를 사용할까?

바로 Red-Black Tree이다.
Java Collections Framework의 TreeMap과 구현이 거의 같은데,
트리 순회 시 사용하는 대소 판단 기준은 해시 함수 값이다.

그런데 해시 값을 대소 판단 기준으로 사용하면 Total Ordering에 문제가 생기는데,
이를 tieBreakOrder() 메서드로 해결한다.

아래 코드를 자세히 살펴보고 공부해보자.

 

transient Node<K,V>[] table;


static class Node<K,V> implements Map.Entry<K,V> {  
  // 클래스 이름은 다르지만, Java 7의 Entry 클래스와 구현 내용은 같다. 
}


// LinkedHashMap.Entry는 HashMap.Node를 상속한 클래스다.
// 따라서 TreeNode 객체를 table 배열에 저장할 수 있다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {


        TreeNode<K,V> parent;  
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;   

        // Red Black Tree에서 노드는 Red이거나 Black이다.
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        final TreeNode<K,V> root() {
        // Tree 노드의 root를 반환한다. 
        }

        static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
        // 해시 버킷에 트리를 저장할 때에는, root 노드에 가장 먼저 접근해야 한다.
        }


        // 순회하며 트리 노드 조회 
        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {}
        final TreeNode<K,V> getTreeNode(int h, Object k) {}


        static int tieBreakOrder(Object a, Object b) {
         // TreeNode에서 어떤 두 키의 comparator 값이 같다면 서로 동등하게 취급된다.
         // 그런데 어떤 두 개의 키의 hash 값이 서로 같아도 이 둘은 서로 동등하지 
         // 않을 수 있다. 따라서 어떤 두 개의 키에 대한 해시 함수 값이 같을 경우, 
         // 임의로 대소 관계를 지정할 필요가 있는 경우가 있다. 
        }


        final void treeify(Node<K,V>[] tab) {
          // 링크드 리스트를 트리로 변환한다.
        }



        final Node<K,V> untreeify(HashMap<K,V> map) {
          // 트리를 링크드 리스트로 변환한다.
        }

        // 다음 두 개 메서드의 역할은 메서드 이름만 읽어도 알 수 있다.
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {}
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {}


        // Red Black 구성 규칙에 따라 균형을 유지하기 위한 것이다.
        final void split (…)
        static <K,V> TreeNode<K,V> rotateLeft(…)
        static <K,V> TreeNode<K,V> rotateRight(…)
        static <K,V> TreeNode<K,V> balanceInsertion(…)
        static <K,V> TreeNode<K,V> balanceDeletion(…)



        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
        // Tree가 규칙에 맞게 잘 생성된 것인지 판단하는 메서드다.
        }
    }

 

해시 버킷 동적 확장 - 개념

만약 해시 버킷의 개수가 적다면,
메모리 사용을 아낄 수는 있지만 해시 충돌이 자주 발생하여 성능상 손실이 발생한다.

그래서 HashMap은 Key-Value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 수를 두 배 늘린다.

이렇게 수를 늘리면 해시 충돌로 인한 성능 손실을 어느 정도 해결 가능하다.

해시 버킷 개수의 default 값은 16이고,
데이터가 일정 개수(즉, 임계점)가 될 때마다 해시 버킷 개수의 크기를 두 배씩 증가시켜,
최대 2^30개까지 확장시킬 수 있다.

이러한 임계점을 찾아내는 계산 식은 아래와 같다.

'{현재의 데이터 개수}' == '{Load Factor} * {현재의 해시 버킷 개수}'
(여기서 {Load Factor}는 0.75, 즉, 3/4)

하지만 이렇게 버킷 개수를 두 배로 늘릴 때마다 기존의 모든 Key-Value 데이터를 읽어,
새로운 해시 버킷에 새로운 Seperate Chaining을 구성해야 하는 문제가 발생한다.

그래서 HashMap 생성자의 인자 중 하나로 초기 해시 버킷 개수를 지정 가능하므로,
내가 만들 HashMap 객체에 저장될 데이터의 개수를 어느 정도 예측이 가능하면 해당 숫자를 생성자 인자로 넣어,
불필요한 Seperate Chaining 재구성을 막을 수 있다.

그럼 이렇게 초기 해시 버킷 개수를 지정해주면 어느 정도의 성능 차이가 날까?

만약, 초기 해시 버킷 개수를 지정하지 않고 N개의 데이터를 삽입했을 때의 Key-Value 쌍 접근 횟수는 아래와 같다.

 

출처) https://d2.naver.com/helloworld/831311

 

위에서 볼 수 있듯이,
기본 생성자로 생성한 HashMap을 이용하며 많은 양의 데이터를 삽입할 때에는

최적의 해시 버킷 개수를 지정한 것보다 약 2.5배 많이 Key-Value 쌍 데이터에 접근해야 한다.

즉, 수행 시간이 2.5배 길어진다는 것이다.

따라서 성능을 높이고 수행 시간을 짧게 하려면,

HashMap 객체를 생성할 때 적절한 해시 버킷 개수를 지정해야 한다.

참고로, 초기 해시 버킷 개수뿐만 아니라, Load Factor 값 또한 HashMap 생성자의 인자로 넣을 수 있다.

 

보조 해시 함수

그런데 이런 두 배 확장에는 문제가 있다.

해시 충돌 글에서 해시 버킷의 index를 구하는 방법은,
X라는 객체와 해시 버킷의 수가 M일 때,
index = X.hashCode() % M
으로 구한다고 했었다.

하지만 해시 버킷의 수가 두 배씩 늘어나기 때문에 M은 2^a 형태가 되고,
위의 index 계산 식에서 계산을 하게 되면 하위 a개의 비트만 사용하게 된다.

즉, 해시 함수가 32비트 영역을 고르게 사용하도록 만들었어도,
해시 값을 2의 승수로 나누게 되어 해시 충돌이 쉽게 발생한다는 것이다.

이 때문에 위의 HashMap vs HashTable 파트에서도 언급한 보조 해시 함수가 필요하다.
이 보조 해시 함수의 목적은 Key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다.

보통 M 값이 소수일 때 index 값 분포가 가장 균등할 수 있다고 한다.

그러나 M 값이 소수가 아닌 2^a 형태이기 때문에,

별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 한다.

 

String 객체에 대한 해시 함수

'갑자기 String 객체?' 라고 생각할 수 있겠지만,
HashMap에서 Key 값에 넣는 데이터 형으로 String과 Integer를 많이 사용하기 때문이다.

가끔 Custom한 Object를 사용하기도 하지만 추후 글에서 다룰 내용이다.

하여튼, String 객체에 대한 해시 함수 수행 시간은 문자열의 길이에 비례한다.

때문에 JDK 1.1에서는 빠르게 해시 함수를 수행하기 위해 일정 간격 문자에 대한 해시를 누적한 값을 문자열에 대한 해시 함수로 사용했다.

 

말이 좀 어려운데, 아래 JDK 1.1에서의 String 클래스 해시 함수 코드를 보자.

 

public int hashCode() { int hash = 0; int skip = Math.max(1, length() / 8); for (int i = 0; i < length(): i+= skip) hash = s[i] + (37 * hash); return hash; }

위처럼 문자열의 모든 문자에 대한 해시 함수를 계산하지 않고,
문자열의 길이가 16을 넘으면 최소 하나의 문자를 skip 해 가며 해시 함수를 계산했다.

하지만 이러한 방식은 웹 상의 URL에서 심각한 이슈가 발생했다.

URL은 길이가 수십 글자에 이를 정도로 길지만, 앞 부분은 동일하게 구성되는 경우가 많다.
이러한 경우에는 서로 다른 URL 임에도 불구하고 해시 값이 같아지는 빈도가 매우 매우 높아지게 된다.

그래서 위와 같은 방식은 곧 폐기되었고, 아래의 방식을 Java 8까지도 계속 사용하고 있다.

 

public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

 

위 방법은 Horner's method라는 것을 구현한 것이다.
(Horner's method에 대한 자세한 내용은 검색)

여기서 '31'이라는 숫자가 눈에 띄는데,
31은 소수이며,
어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문에 사용한다.

어떻게 빠르게 계산할 수 있냐하면,
31 * N = 32N - N이고,
32는 2^5이므로,
어떤 수(N)에 대한 32를 곱한 값은
아래처럼 shift 연산으로 쉽게 구현할 수 있다.

31N == (N << 5) - N

이렇게 31을 곱하는 연산은 최적화된 머신 코드로 생성 가능하기 때문에
String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.

---

 

WAS(Web Application Server)의 경우에는 HTTPRequest가 생성될 때마다,
여러 개의 HashMap이 생성된다고 한다.

수많은 HashMap 객체가 1초도 안되는 시간에 생성되고, 또 GC(Garbage Collection)의 대상이 된다.

컴퓨터 메모리 크기가 보편적으로 증가함에 따라 메모리 중심적인 애플리케이션 제작도 늘었다.

따라서 갈수록 HashMap에 더 많은 데이터를 저장하고 있다.


끝!