네이버 D2 - Java HashMap은 어떻게 동작하는가?를 읽고 초심자의 시선에서 조금 더 이해하기 쉽도록 정리해 보았습니다.
본 글의 이미지 출처는 네이버 D2 혹은 위키피디아입니다.

Map<String, Integer> scores = new HashMap<>();

JAVA를 다루며 흔히 사용하는 HashMap에 대해 자세히 알아보는 시간을 가져보도록 하겠습니다.
사전 지식으로 Hash, Map에 대해 먼저 알아보겠습니다.

Hash가 뭔가요?

해시의 정의는 임의 크기의 데이터를 고정된 크기의 데이터로 변환시키는 것입니다.
원본 데이터를 key, 변환 과정을 해싱, 도출 값을 해시값이라 합니다.
변환 과정은 주로 특정 함수를 통해 이루어지는데, 이를 해시 함수라 부릅니다.

해시 함수의 예시를 들어주세요

아주 간단한 예시를 들어보도록 하겠습니다.

public int createHash(int some) {
	return some % 10;
}

해당 함수는 어떠한 크기의 정수형 값이 들어오든, 0~9까지 한자리의 정수형 값만 반환합니다. 해시의 정의를 가장 쉽게 나타낸 함수입니다.
다만, 이는 완전한 해시 함수(perfect hash functions)로 볼 수 없습니다.

완전 해시 함수의 특징은 무엇이 있나요?

서로 다른 객체라면, 다른 해시값을 도출할 수 있어야 합니다.
위에 해당하는 해시함수는 9, 19, 29처럼 다른 값을 집어넣어도 해시값은 9로 같습니다. 완전한 해시 함수라 볼 수 없죠.

완전한 해시 함수를 어떻게 만들 수 있나요?

아쉽게도, 프로그래밍 상에서는 불가합니다.
프로그래밍에서는 제한된 범위가 있습니다. int를 예로 든다면, 나타낼 수 있는 경우의 수는 2^32입니다.

그러나, 특정 객체에 대해 표현할 수 있는 경우의 수는 위의 범위를 아득히 초과합니다. 간단하게 int형을 2개만 들고 있는 객체를 생각해봅시다.

public class Person {
	private final int teamCode;
    private final int nationCode;
}

팀코드와 국가코드의 조합에 따라 사람을 구별한다고 생각해 봅시다. 둘 다 int형이니, 나올 수 있는 경우의 수는 2^64일 것입니다.
여기에 사람의 이름, 나이, 주소 등등의 데이터가 추가된다면 나올 수 있는 경우의 수는 무한이겠죠.

그렇다고 해시값의 범위를 무한에 가깝게 늘린다면, 그만큼 자원을 많이 소모하게 될 겁니다.
즉, 프로그래밍에서는 어떠한 객체가 들어와도 모두 다른 해시값을 지니는 완전 해시 함수는 구현할 수 없습니다. 언젠가는 서로 다른 객체가 들어와도 같은 해시값을 지니는 경우가 필연적으로 생기기 때문입니다(이를 해시 충돌이라 합니다).

하지만 그렇다 한들, 해시 충돌을 최소화하는 좋은 해시 함수는 만들 수 있습니다.

좋은 해시 함수의 특징은 무엇이 있나요?

좋은 해시 함수의 특징은 다음과 같습니다.

• 해시 충돌이 최소화되어야 합니다.
• 해시값의 분포가 고르게 나타나야 합니다.
• 연산이 빨라야 합니다.
• 해시값을 통해 입력값을 추론해낼 수 없어야 합니다.
• 작은 입력값의 차이가 큰 해시값의 변화를 이끌어 냅니다.

맨 처음에 작성한 함수를 살펴보자면, 연산은 빠를 지언정 해시 충돌이 최소화되진 못 할 겁니다. 한자리 수만을 반환하기 때문에 엄청 많은 충돌이 일어나니까요.
또한 특정 경우에 따라 해시값의 분포가 고르지 않을 수 있습니다. 끝자리가 0, 1이 반복되는 경우 두 값에만 치중하게 되니 말입니다.
해시값을 통해 완전한 입력값을 추론할 수는 없겠지만, '끝자리가 이것이겠구나'같은 추론은 가능하기에 좋은 해시함수로는 볼 수 없겠네요.

좋은 해시 함수의 예시를 들어주세요

좋은 해시 함수 중 하나는 SHA-3입니다.
직접 테스트해보면 아시겠지만, 입력값의 작은 변화도 큰 차이의 해시값을 만들어 냅니다. 원본의 형태를 찾을 수 없기에 입력값을 추론하는 것은 매우 힘들어 보입니다.
연산도 빠르고, 분포 또한 고르게 나올 수 있도록 내부적인 설계가 되어 있다고 하네요.

다만 JAVA는 해시값의 범위가 int로 제한되니, JAVA에서의 기본적인 해시 함수 구현을 볼까요?

JAVA의 좋은 해시 함수 예시를 들어주세요

@Override
public int hashCode() {
    int hash = 7;
    hash = 31 * hash + (int) id;
    hash = 31 * hash + (name == null ? 0 : name.hashCode());
    hash = 31 * hash + (email == null ? 0 : email.hashCode());
    return hash;
}

해당 함수는 가장 표준이 되는 해시함수입니다.
id, 이름, 이메일 필드가 있는 객체 내에서 7과 31을 사용해 해시값을 구하는 구조입니다.
(7과 31을 사용하는 이유는 2^n - 1이자 소수이기 때문입니다만, 다른 특정한 값을 사용해도 무관합니다.)

엇, 근데 이름과 이메일은 String일 텐데 어떻게 해시를 구할 수 있는 걸까요?

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

JAVA의 String 해시함수입니다.

public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

StringLatin1의 해시함수입니다.

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;
}

StringUTF16의 해시함수입니다.

보시면, 둘 다 내부 char를 순회하며 값을 늘려간 후 반환하는 구조로 되어있습니다.

해시를 어느 정도 살펴봤으니, Map에 대해 간단히 살펴봅시다.

Map은 뭔가요?

Map은 어떠한 값(value)을 특정 키(key)와 연결시켜 놓는 것을 말합니다.
원래 수학 함수에서의 대응 관계를 지칭하는 용어라고 해요.

키는 우리가 값을 쉽게 찾기 위한 역할이기에, 중복되서는 안 됩니다.
다만 서로 다른 키라도 같은 값을 연결하는 건 허용됩니다.

값을 연결시키고 가져오는 메서드 등에 대해 설명할 수도 있지만, 내부 구조를 중점으로 파악하는 중이기에 넘어가도록 하겠습니다.

HashMap은 어떻게 이루어져있나요?

이제 본격적으로 HashMap을 살펴봅시다.

해시 버킷

HashMap은 내부적으로 해시 버킷이라는 배열을 지니고 있습니다.
initSize를 주지 않으면 기본 길이는 16입니다.

사람 이름을 key로, 전화번호를 value로 두고 HashMap에 저장하는 과정을 예시로 들겠습니다.

John Smith의 해시값이 34라고 가정합시다.
그림처럼 해시 버킷의 현재 사이즈는 16입니다. 따라서 해시 버킷의 내부에 저장되는 방법은
해시 버킷[해시값 % 해시 버킷의 사이즈] = 해시 버킷[34 % 16] = 해시 버킷[2]에 저장이 됩니다.
나머지 값들도 이처럼 해시 버킷의 사이즈로 나눈 나머지 인덱스에 저장이 됩니다.

해시값이 아무리 균등분포가 되어 있더라도, 인덱스 충돌이 날 수 밖에 없는 구조입니다.

내부적으로 인덱스 값이 충돌된다면 어떻게 되나요?

충돌이 발생하더라도 마치 '충돌이 발생하지 않은 것처럼' 데이터를 관리해야 합니다.
데이터를 관리하는 방식은 대표적으로 두 가지가 있습니다.

Open Addressing

John Smith의 인덱스가 152로 판단되어, 해시 버킷[152]에 John Smith의 데이터를 넣습니다.
Sandra Dee의 인덱스도 152가 나왔습니다. 다만, 해시 버킷[152]에는 John Smith가 이미 있으므로 인덱스++을 반복하며 빈 해시버킷을 찾아갑니다.
빈 인덱스를 찾으면 해당 인덱스에 값을 넣습니다.

이처럼 Open Addressing은 이미 선점된 데이터가 있다면, 인덱스에 변화를 주면서 빈 공간을 찾아가는 방식입니다. 위의 예시처럼 1씩 더할 수도 있고, 제곱을 하거나 다른 보조해시함수를 통해 빈 공간을 찾는 방식도 있습니다. 이를 탐사라 합니다.

기존에 넣은 값을 찾기 위해선 탐사 과정을 다시 거치게 됩니다. 이 때, 중간에 거쳐가는 값이 삭제가 되어 완전히 빈 인덱스가 되어버린다면 탐색 과정에서 오류가 발생합니다(Sandra Dee의 데이터가 삭제 -> Ted Baker 탐색 -> 해시 버킷[153]이 비어있으므로 Ted Baker를 찾을 수 없음).

따라서, 삭제된 값이 있다면 해당 공간을 삭제되었다고 명시해줘야 합니다.

해당 방식은 삭제되는 값이 많다면 불필요하게 해시 버킷을 점거하는 데이터가 많아집니다. 따라서 HashMap에서는 해당 방식을 사용하지 않습니다.

Separate Chaining

Separate Chaining은 HashMap이 사용하는 방식입니다.
각각의 해시 버킷마다 LinkedList를 소유하고, 인덱스 충돌이 일어난 경우 기존의 값과 새로운 값을 연결합니다.
이렇게 유지하면 값의 삭제와 추가가 굉장히 쉬워집니다.

헌데 만약, 16개의 해시 버킷을 지니는 HashMap에 천만 개의 값을 저장한다면 어떻게 될까요?
하나의 인덱스에도 수많은 값이 몰릴 것이고, LinkedList 형태만으로는 빠른 응답을 하지 못 할 것입니다.

이러한 상황을 최적화하기 위해서는 추가적인 설계가 더 필요합니다.

충돌 최적화

LinkedList -> RedBlackTree

첫번째로, LinkedList 대신 Tree를 이용한 방법이 있습니다.

LinkedList는 값을 조회할 때 최대 O(N)의 시간복잡도를 가집니다.
맨 마지막에 추가된 값을 조회할 때 (순환 연결 리스트가 아니라면) 최대 N만큼 다음 노드를 찾아야 하기 때문입니다.

반면 자가 균형 이진 탐색 트리의 일종인 RedBlackTree를 이용하면 시간복잡도는 O(logN)이 됩니다.
JAVA8부터는 해당 방법을 사용하여, LinkedList의 사이즈가 8을 넘어가면 RedBlackTree로 변형이 이뤄집니다.
또한 사이즈가 6 이하로 줄어들면, 다시 LinkedList로 변형됩니다.
7이 아닌 6인 이유는, 만약 데이터가 7~8을 왔다갔다한다면 자료구조를 계속 변형시키는 데 리소스가 더 많이 들어가기 때문입니다.

(LinkedList와 RedBlackTree를 이 글에서 설명하기엔 너무 방대한 자료라, D2 문서 혹은 추후 작성할 자료구조 글을 봐주시면 감사하겠습니다.)

해시 버킷 사이즈를 늘린다면?

두번째 방법은 해시 버킷 사이즈 자체를 늘리는 겁니다.
실제로 HashMap은 데이터의 개수가 load factor * 현재 해시 버킷 개수에 도달할 때 해시 버킷 사이즈를 2배로 늘립니다. 기본 load factor는 0.75이며, HashMap 생성 시 다른 값으로 줄 수 있습니다.

해시 버킷 사이즈를 늘릴 때 주의할 점은 2가지입니다.
1. 새로운 버킷 사이즈는 기존 버킷 사이즈 * 2이다.
2. 기존의 모든 데이터를 가져와 새로운 해시 버킷에 옮긴다.

2번의 문제점은 해시 버킷 인덱스가 늘어난 만큼, 새로운 인덱싱 과정을 겪는 당연한 수순이기에 넘어가도록 하겠습니다.
이는 많은 데이터 추가가 예상된다면 해시 버킷 사이즈를 그만큼 크게 잡으면 해결되는 문제입니다.

1번에서 생기는 문제점은, HashMap의 기본 해시 버킷 사이즈인 16은 2^4입니다.
이 때 해시 버킷의 사이즈가 계속해서 2배로 늘어나게 되면 버킷 사이즈는 2^x 형태가 되고, 인덱스 값은 해시값 % 2^x이므로 0 ~ 2^(x-1)로 고정이 됩니다. 즉, x-1개의 하위 비트만 사용하게 됩니다.

..무슨 소리에요?

해시 버킷 사이즈가 32인 경우를 예시로 들어보겠습니다.
32는 2^5이므로 하위 8개의 비트만 표현해보면 다음과 같습니다.
b0001 0000
이 때의 나머지 연산을 통해 나오는 비트의 범위는
b0000 0000 ~ b0000 1111입니다.

즉, 어떠한 해시값이 입력되어도 해시 버킷 인덱스를 구할 때는 하위 x-1개의 비트만으로 인덱스가 결정이 됩니다.
이는 맨 처음에 설명드렸던 해시 함수와 같은 결의 문제점을 소유하게 됩니다.

이러한 상황을 방지하기 위해, 인덱스 결정 전 보조 해시 함수를 사용합니다.

보조 해시 함수

보조 해시 함수는 기존의 해시값을 다시 설정한다고 보시면 됩니다.
하위 비트만 사용되는 상황을 막고자, 상위 비트를 통해 하위 비트를 변형시키는 구조입니다.

JAVA8 이전에는 현재 해시값을 h로 두고
return h ^ (h >>> 20) ^ (h >>> 12) ^ (h >>> 7) ^ (h >>> 4);
의 과정을 거쳤습니다.
(String인 경우에는 return sun.misc.Hashing.stringHash32((String) k);을 했습니다.)

다만 JAVA8 이후에는 RedBlackTree를 이용하여 더 빠른 접근을 가능케 만든 점, 사용되는 해시 함수들이 해시값을 고르게 반환하는 점들을 고려해
h ^ (h >>> 16)으로 완화되었습니다.

마치며

이렇게 해서 기본적인 HashMap의 구조에 대해 알아보았습니다.
동시성을 해결해주는 HashTable에 대해서도 같이 설명드릴까 했으나 현재는 업데이트되지 않는 자료구조이기도 하고, 동시성을 만족하는 ConcurrentHashMap이 있기에 넘어가도록 하겠습니다.
질문 있으시면 언제든 댓글로 남겨주세요.
감사합니다.