[코틀린] HashMap Deep-Dive

안녕하세요 주코입니다.

최근, 예전부터 HashMap을 잘 다루고 싶었지만, 흉내는 낼 뿐 잘 사용하지 못했었습니다. 그러다 최근, 시간 복잡도 문제들을 만나며 중요도를 알게 되었고, 정확하게 그리고 딥하게 학습하고 기록하고자 이렇게 글을 쓰게 되었습니다.

 

해시맵 (HashMap) 이란?

해시(hash) 기법을 사용해 맵(map)으로 데이터를 저장하기 위한 자료구조입니다.

즉, 키(key)와 값(value)의 쌍으로 데이터를 저장하는 해시 기반 컬렉션입니다.

평균 시간 복잡도는 O(1)을 가지고 있으며, 최악의 경우 O(log n)의 시간복잡도를 갖습니다.

그렇다면 해시는 무엇이고 맵은 무엇일까?

해시 (Hash) 란?

해시(hash)는 입력 데이터를 고정된 길이의 고유한 값(해시값)으로 변환하는 과정을 의미합니다.

해시값은 일반적으로 정수(int)로 표현되며 같은 입력은 항상 같은 해시값으로 반환합니다.

fun main() {
    val test1 = "a"
    val test2 = "b"
    val test3 = "ab"
    println("a = ${test1.hashCode()}")
    println("b = ${test2.hashCode()}")
    println("ab = ${test3.hashCode()}")
}

예를들어 위 처럼 각 문자열을 hashCode()로 변환하면

a = 97
b = 98
ab = 3105

위와 같은 값으로 변환시킵니다.

이는 키를 빠르게 찾기 위한 수학적 기법입니다.

 

맵 (Map) 이란?

맵(map)은 키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료구조를 의미합니다.

일반적인 배열(List)은 인덱스를 통해 접근하지만, map은 "키"라는 고유값으로 데이터에 접근합니다.

내부적으로 키와 값을 묶은 Entry(Node) 객체들을 저장하는 배열기반 구조 입니다.

 

즉, 키를 통해 원하는 값을 빠르게 찾을 수 있습니다.

 

그럼 HashMap은 무엇이고 Map은 무엇인가?

HashMap(해시맵)은 class이고 Map은 Interface 입니다.

class HashMap<K, V> : MutableMap<K, V>

실제 해시맵은 위와 같은 형태를 띄고 있으며, Map을 어떻게 동작하는지를 구현함에 따라

HashMap, LinkedHashMap, TreeMap등으로 동작할 수 있습니다.

 

여기서 헷갈리면 안되는것은

Map = 읽기전용

MutableMap = 읽기, 쓰기 전용 입니다.

 

HashMap의 내부구조가 어떠한가?

해시맵(HashMap)은 빠른 탐색을 위해 꽤나 복잡한 구조를 가지고 있습니다.

대략적인 흐름을 알아보도록 하겠습니다.

 

1. 해시맵은 키에서 해시 값을 얻습니다.

hashCode()를 호출해 정수형 해시값을 얻습니다.

이 때 이 값은 HashMap 내부적으로 hash()라는 이름의 함수에서 다시 처리 되며, 비트 연산으로 추가 분산(spreading)이 이루어집니다.

 

2. 해시값을 이용해 배열 인덱스를 계산합니다.

index = (BUCKET_SIZE - 1) & hash

위 연산으로 저장 위치를 결정합니다.

이때 BUCKET_SIZE는 항상 2의 거듭 제곱입니다.

 

3. 이제 해시맵은 해당 인덱스(bucket)에 key-value 쌍을 저장합니다.

만약 해당 자리에 이미 노드가 있다면 (충돌이 발생 했을시), 연결 리스트 또는 트리 구조로 이어 붙입니다.

이때 키가 같으면 덮어쓰고 다르면 체이닝됩니다.

 

4. BUCKET_SIZE(용량)를 초과한다면?

저장된 데이터수가 용량(BUCKET_SIZE * loadFactor)를 넘으면 리사이징이 발생하며, 기존 데이터를 새로운 버킷에 재배치합니다.

 

그래서 왜 빠른건데?

hashCode()는 단순히 정수(int)를 반환하는 간단한 연산입니다.

그런데 대부분의 메서드들은 필드 값들을 정수로 계산하여 조합하거나 메모리 주소 기반으로 생성이되는데

이 계산은 CPU 연산 한두 번으로 끝나기 때문에 매우 빠릅니다.

 

또 해시맵은 내부적으로 배열을 사용하는데, 해시값을 통해 인덱스를 계산한 뒤, 배열 인덱스로 직접 접근 하기 때문입니다.

이 과정이 O(1) 입니다.

즉, 데이터를 탐색할 때 비교없이 곧장 해당 버킷으로 접근할 수 있어 빠르다는걸 알 수 있었습니다.

 

여기 까지만 봤을땐 hashCode()를 통해 각 값들을 정수형으로 반환시키고, key-value 쌍으로 저장하고 탐색할 수 있어 빠르다는건 알 수 있었습니다. 하지만, 더 정확한 이유를 위해 이 값들을 어떻게 저장시키는지 bucket과 BUCKET_SIZE에 대해 더 자세히 알 필요가 있었습니다.

 

버킷(Bucket) 이란?

해시맵은 데이터를 저장하기 위해 내부적으로 배열(table)을 사용합니다.

이때 이 배열의 각 칸을 버킷(bucket) 이라고 부릅니다.

해시값을 이용해 이 배열의 인덱스를 계산하고 해당 버킷에 데이터를 저장합니다.

계산은

 key.hashCode() % BucketSize

위 와같은 형태로 계산하여 인덱스를 계산합니다.

 

버킷 사이즈(Bucket size)란?

해시맵(hashMap) 에서 가장 중요하다고 생각하는 버킷 사이즈입니다.

해시맵에는 버킷 사이즈(Bucket size)가 있습니다. 이 버킷 사이즈는 내부 배열의 크기이고 이 배열에 데이터를 해시함수로 계산된 인덱스에 저장합니다.

버킷 사이즈는 초기에 16을 가지고 있으며, 2의 제곱수이며 2배씩 늘어납니다.

 

1. 버킷 사이즈는 충돌을 줄이기 위해 꼭 필요합니다.

예를들어 "abc"와 같은 여러 키(key)가 같은 index(버킷)에 저장될 수 있습니다.

이때 버킷이 너무 작으면 충돌이 많이 발생하여 성능이 떨어질것입니다. 반대로 버킷이 너무 크면 메모리가 낭비 되고 성능 향상 대비 효율이 떨어 질것입니다.

 

2. 만약, 충돌이 발생하면 어떻게 되나?

우선 hashCode가 같으면 무조건 충돌을 합니다. 

예를들어

    println("Ea".hashCode())
    println("FB".hashCode())

위와 같이 "Ea" 와 "FB"는 2236 이라는 같은 hashCode를 갖습니다.

그렇기에 이 충돌을 피하기위해 해시맵 내부에서는 같은 해시값이여도 키 까지 비교를 합니다.

 

하지만 만약 아래 처럼 생각을 해본다면,

val map = HashMap<String, Int>()
map["abc"] = 1
map["acb"] = 2

위 코드의 "abc"의 해시코드는 123456 입니다.

"acb"의 해시코드는 234567 입니다.

이때 인덱스는

 key.hashCode() % BucketSize

위 계산식으로 계산을 하면 5번 index(버킷)로 같은 공간에 할당 되게 됩니다.

이때, 버킷 사이즈는 자동으로 초기값의 2배인 32로 리사이징이 됩니다.

 

또한 기본 LoadFactor는 0.75로 

BucketSize * LoadFactor

위 계산식으로 초기 버킷 사이즈 16을 대입하여 초기 배열의 크기는 16 x 0.75 = 12가 할당이 되게 됩니다.

즉, 13번째 데이터를 넣는 순간 버킷 사이즈는 32로 증가하며 이때 기존 데이터를 모두 다시 해싱하여 새로운 버킷에 재배치합니다.

 

3. 그럼 버킷 사이즈를 내가 정할 수 있나?

가능합니다.

val map = HashMap<String, Int>(16) // 초기 버킷 사이즈를 16으로 설정

위 와 같은 방식으로 초기 버킷 사이즈를 정의할 수 있습니다.

다만, 앞서 말씀 드린것처럼 버킷 사이즈가 너무 작을 경우 충돌이 많아지고, 너무 클경우 메모리가 낭비 될 것입니다.

 

직접 코드로 구현해보면서 이해를 해보자

이렇게 이론을 알아보고 해시 맵(hashMap)의 구조 또한 알아 봤습니다.

이제 저는 직접 코드를 구현해보면서 더 이해도를 높여 보려고합니다.

해당 코드는 HashMap을 사용하지않고 List 형태로 정의해보면서 알아 보겠습니다.

 

BucketSize

private const val BUCKET_SIZE = 16

버킷 사이즈를 정의합니다. 초기 값 그대로 16을 정의하겠습니다.

 

Bucket

데이터를 담아둘 배열을 정의합니다.

이는 해시맵(hashMap)의 구조를 List 형태로 정의해봤습니다.

private val buckets = MutableList<MutableList<Pair<String, String>>>(BUCKET_SIZE) { mutableListOf() }

 

내부 hash() 함수

import kotlin.math.absoluteValue

fun hash(key: String): Int {
    return key.hashCode().absoluteValue % BUCKET_SIZE
}

내부 hash 함수를 정의합니다.

hashCode()는 음수형태로 나올 수 있기에

절댓값으로 변환합니다. hashCode의 key 를 absoluteValue로 바꿔줍니다.

 

전체 메서드 구현

위를 통해 기본적인 베이스를 잡았습니다.

이제 기본적인 해시맵(hashMap)의 메서드 put get containsKey remove clear isEmpty 구현 전체 코드를 짜보겠습니다.

 

import kotlin.math.absoluteValue

private const val BUCKET_SIZE = 16
private val buckets = MutableList<MutableList<Pair<String, String>>>(BUCKET_SIZE) { mutableListOf() }
fun main() {
    println("====== 기본 put/get 테스트 ======")
    put("apple", "사과")
    put("banana", "바나나")
    println("apple → ${get("apple")}")    // 기대: 사과
    println("banana → ${get("banana")}")  // 기대: 바나나
    println("grape → ${get("grape")}")    // 기대: null

    println("\n====== 충돌 테스트 (Ea vs FB) ======")
    put("Ea", "E값")
    put("FB", "F값")
    println("Ea → ${get("Ea")}")          // 기대: E값
    println("FB → ${get("FB")}")          // 기대: F값

    println("\n====== containsKey 테스트 ======")
    println("contains Ea → ${containsKey("Ea")}") // 기대: true
    println("contains FB → ${containsKey("FB")}") // 기대: true
    println("contains grape → ${containsKey("grape")}") // 기대: false

    println("\n====== keys 출력 테스트 ======")
    println("keys → ${keys()}")           // 기대: apple, banana, Ea, FB

    println("\n====== remove 테스트 ======")
    remove("banana")
    println("keys after remove → ${keys()}")   // 기대: apple, Ea, FB
    println("contains banana → ${containsKey("banana")}") // 기대: false

    println("\n====== clear / isEmpty 테스트 ======")
    clear()
    println("isEmpty → ${isEmpty()}")     // 기대: true
    println("keys after clear → ${keys()}") // 기대: (빈 문자열)

    println("\n====== 전체 buckets 내용 확인 ======")
    printAll() // 기대: 아무 출력 없음 (모든 버킷이 비어있음)
}


fun printAll() {
    for ((i, bucket) in buckets.withIndex()) {
        if (bucket.isNotEmpty()) {
            println("buckets[$i] → $bucket")
        }
    }
}

fun hash(key: String): Int {
    return key.hashCode().absoluteValue % BUCKET_SIZE
}

private fun put(key: String, value: String) {
    val index = hash(key)
    val bucket = buckets[index]

    for (i in bucket.indices) {
        if (bucket[i].first == key) {
            bucket[i] = key to value
            return
        }
    }

    bucket.add(key to value)
}

fun get(key: String): String? {
    val index = hash(key)
    val bucket = buckets[index]
    return bucket.firstOrNull { it.first == key }?.second
}

private fun keys(): String {
    val hashMapKeys = mutableListOf<String>()

    for (i in buckets.indices) {
        for (j in buckets[i].indices) {
            hashMapKeys.add(buckets[i][j].first)
        }
    }

    return hashMapKeys.joinToString(", ")
}

private fun containsKey(str: String): Boolean {
    val index = hash(str)
    val bucket = buckets[index]
    for (i in bucket.indices) {
        if (bucket[i].first == str) return true
    }
    return false
}

private fun remove(key: String) {
    val index = hash(key)
    buckets[index].removeIf { it.first == key }
}


private fun clear() {
    for (bucket in buckets) {
        bucket.clear()
    }
}

private fun isEmpty(): Boolean {
    return buckets.all { it.isEmpty() }
}

 

위 코드는 제가 이해를 위해 작성한 코드이며 직접 작동해가며 HashMap을 이해해 보시면 좋을듯 합니다!

 

마무리

이렇게 HashMap에 대해 알아보았습니다.

실제 이해를위해 List형태로 정의하여 각 메서드들을 구현 또한 해보았습니다.

이렇게 하나하나 알아보니 확실히 지식도 늘고 실제 알고리즘 풀때에도 도움이 많이 되었습니다.

다음 부터는 이런 방식으로 모르는것들이 있으면 하나하나 알아가보려고합니다!