HashMap 에 대하여

개요

Java의 HashMap 에 대한 공부.

자주 쓰지만, 실제로 어떻게 동작하는지에 대한 이해가 필요하고 Java에서 뿐만 아니라, NoSQL 등의 경우에도 사용되는 Hash의 개념과 Map의 개념에 대해 알아보자.

Hash

Hash 는 특정 input 값이 주어졌을 때 항상 동일값을 보장해주는 값이다.

주로 SHA256 MD5등과 같은 해시 알고리즘에 의해 많이 알려져 있다. 차이점이라고 하면 Hash를 할 때 충돌(collision)이 발생하게 되는데, 그런 충돌을 얼마나 더 효율적으로 방지할 것인가에 대한 정도가 되겠다.

Java에서 사용하는 String 클래스의 해시 함수를 살펴보자.

Hash != HashCode

Hash : 해시 함수

HashCode : 해시 해서 나온 값을 정수화 시킨 것

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            hash = h = isLatin1() ? StringLatin1.hashCode(value)
                                  : StringUTF16.hashCode(value);
        }
        return h;
    }

String이 Latin인 경우와 UTF-16 인 경우를 분기해서 해시를 계산하도록 되어 있다.

UTF-16을 기준으로 더 보게 되면 아래와 같다.

    public static int hashCode(byte[] value) {
        int h = 0;
        int length = value.length >> 1;
        for (int i = 0; i < length; i++) {
            h = 31 * h + getChar(value, i);
        }
        return h;
    }

Java String의 내부 구조는 char[] 로 이루어져 있다. 또한 이는 JVM의 constant pool에 저장되어 byte[] 데이터를 가질 수 있게 되는데, 해당 값으로 해시를 진행한다.

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 과 같은 꼴로 해시코드를 구하게 된다.

이러한 해시코드는 대부분 String마다 다름을 보장하지만, 그렇지 않을때도 있다.

특히나, HashMap의 경우에 Key가 되는 값이 String만 되는것이 아니라, Object가 되기 때문에 항상 같음 을 보장할 순 없다는 소리다.

해시 충돌(Hash Collision)

만약, 해시가 충돌하면 어떤일이 발생할까

Object a = new Object();
Object b = new Object();
HashMap<Object, String> map = new HashMap<>();

map.put(a, "a");
map.put(b, "b");

// map의 entry를 출력한 결과는 어떻게될까?
map.forEach((k,v) -> {
  System.out.println("key : " + k + " value :" + v);
});

위와 같이 a,b를 새로 생성하고, 객체를 Map에 그대로 담아보자.

물론 두 객체가 다르겠지만, 만약에 같게 된다면 map에는 a와 b의 해시코드가 같으니 마지막 값인 b로 덮어씌워지게 될 것이다.

(실제로 HashMap에 위와 같이 넣게 되면 a,b가 충돌해도 그대로 존재한다. 왜 인지는 아래에서 확인하자.)

위의 그림이 해시함수를 수행했을 때, 값이 충돌이 발생한 경우를 보여주는데

John Smith 와 Sandra Dee 가 같은 해시값을 나타내는 02가 나오게 되었다.

이런 경우, 값이 날아가는걸 막아야하는데 크게 두가지의 방법이 있다.

Open Addressing

해시의 충돌이 발생했을 때 충돌이 발생한 index의 뒤를 찾아서 빈 공간에 데이터를 넣는 방법이다.

빈 공간을 탐색하는 방법에는 Linear Probing , Quadratic Probing 등의 방법이 있다.

Seperate Chaining

Java HashMap에서 사용하는 방법이다.

충돌이 발생하는 key에 대한 값을 1개만 두지 말고, LinkedList 와 같은 방식으로 리스트를 넣는 방식이다.

즉,

HashMap<String, String> map = new HashMap<>();
map.put("a", "b");
map.put("c", "d");

와 같이 넣게 되면 내부적으로는

public boolean put(String key, String value){
  LinkedList valueChain = getValue(key); // key값으로 linkedList를 가져와봄
  if(valueChain == null){
    valueChain = new LinkedList<>(); // 없으면 새로 생성
  }
  valueChain.add(value);
}

위와 같이 넣게 되는 것이다(실제 로직은 저보다 복잡하지만, 단순화를 시켰다)

이렇게되면 Hash를 해서 가져왔을 경우에 시간복잡도가 원래 O(1) 이지만, 최악의 경우 LinkedList를 전부 순회를 해야할 수도 있으므로 O(n) 까지 갈 수도 있다.

실제로 사용할 때 대부분의 경우는 O(1) 에 가져오겠지만, 충돌이 많은 경우는 성능이 더 안좋을 수도 있다.

Map

위에서 해시와 해시 충돌에 대해서 알아봤다.

그럼 Java HashMap의 구현에 대해서 조금 더 파보도록 하자.

Map의 인터페이스는 아래와 같다

public interface Map<K, V> {
  V put(K key, V value);
  V get(Object key);
}

그 밖에 유틸성 메서드가 많지만, 매우 간략하게 보자면 위와 같은 메서드가 제공이 되어야 한다.

Key 와 Value 를 매핑할 수 있는 자료구조인 것이다.

Map의 구현체로는 HashMap, TreeMap, LinkedHashMap 등이 있다. 각기 다른 구조로 구성이 되어 있는데 이번엔 기본이 되는 HashMap에 대해서만 알아보자.

HashMap같은 경우는 associate array로도 불리우는데, 최초 bucket의 크기가 정해져 있고 데이터가 추가될수록 이를 증가시켜서 커지는 구조로 되어 있다.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

최초 크기는 16개의 bucket으로 생성이 되게 된다

static final float DEFAULT_LOAD_FACTOR = 0.75f;

그리고 Load Factor 라는 개념의 값이 있는데, HashMap의 생성자로 특별히 지정을 하지 않는 이상 75%의 load factor를 가지고 있다.

이 말은, 위의 최초 생성 크기가 16개의 bucket으로 시작한다고 했는데 16의 75%인 12개의 bucket을 사용하게 된다면 그 크기를 2배로 늘린 32개의 bucket으로 증가시킨다는 말이다.

static final int TREEIFY_THRESHOLD = 8;

이 부분이 흥미로운데 아까 말했듯이 Java에서는 seperate chaning 방식을 사용하므로, 해시의 충돌이 일어났을 때 LinkedList를 사용해서 해결을 한다고 했다.

근데 LinkedList의 특성상 탐색이 느린 단점(O(n)) 때문에 성능의 저하가 되니, 이를 TREEIFY 임계점을 지정하여 동일한 key에 대해 충돌이 자주 발생할 경우(기본 8개) 이를 Tree구조로 변경을 한다는 점이다.

TreeNode로 변경을 할 경우 O(n) 에서 탐색 시 O(log n) 으로 개선이 가능한 부분을 적용한 것이다.

static final int UNTREEIFY_THRESHOLD = 6;

Map의 삭제 혹은 크기 재조절 시 해당 LinkedList 혹은 TreeNode의 element개수가 또 적어질수도 있는데, 이런 경우에 6개 이하의 element가 될 경우 탐색시간이 그리 소요되지 않으니 LinkedList로 다시 변경하는 임계점이 존재한다.

public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

또한 데이터노드의 hashCode를 계산하는 부분이 위와는 또 사뭇 다른데, 잘 보면 key에 대한 hash와 추가적으로 value에 대한 hash값을 XOR한 값을 hashCode로 사용하는 것을 알 수 있다.

이는 key로만 hashing했을 경우 충돌이 발생하는 케이스를 더 줄이고자 value까지 hashing을 해서 XOR하는 알고리즘으로 구현이 되어 있다(보조해시함수)

그렇기에 대~부분 충돌이 잘 발생안할것으로 예상하지만 내부적으로 충돌발생 시 어떤 동작을 취하는지는 알아두면 좋을것 같다.

Thread-safety

HashMap의 경우 Thread-safe하지 않다.

이런 경우 사용하는 대안이 HashTable 과 ConcurrentHashMap 이 존재하는데, 이 부분은 뒤이어 차이점에 대한 포스팅을 할 예정이다.