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가 되기 떄문에 항상 같음 을 보장할 순 없다는 소리다.