Intro

Array와 Map의 쓰임은 명백히 다르다.

• Array: 각 idx별 값 저장 → idx를 통한 random access ⇒ 주로 값 저장
• Map: 각 key별 값(value) 저장 → key(임의의 타입)를 통한 value 접근 ⇒ 주로 key의 상태 저장

하지만 key가 정수일 경우, Map 대신 Array를 사용할 수 있다.

Array는 별도의 과정(hash 값 계산, hash 충돌 처리, hash Table 확장)없이 값을 저장/조회할 수 있기 때문에 더 빠를 것이다.

정말 Map 대신 Array를 사용하는 것이 빠른지 확인해보자

코드 테스트

테스트1 - 단순 비교

단순히 주어진 반복 횟수 repeat 만큼 값을 저장하는 코드를 작성하였다.

Array와 HashMap 각각 몇초가 걸리는 지 확인해보자.

import kotlin.system.measureNanoTime

fun arrayTime(repeat: Int): Double {
    val value = "value"
    val a = Array<String>(repeat) { value }
    return measureNanoTime {
        for (j in 0 until repeat) {
            a[j] = value
        }
    } / 1000000000.0
}

fun mapTime(repeat: Int): Double {
    val a = hashMapOf<Int, String>()
    val value = "value"
    return measureNanoTime {
        for (j in 0 until repeat) {
            a[j] = value
        }
    } / 1000000000.0
}

fun main() {
    println("repeat 100만회, array: ${arrayTime(1000000)}, map: ${mapTime(1000000)}")
    println("repeat 1000만회, array: ${arrayTime(10000000)}, map: ${mapTime(10000000)}")
    println("repeat 2000만회, array: ${arrayTime(20000000)}, map: ${mapTime(20000000)}")
    println("repeat 3000만회, array: ${arrayTime(30000000)}, map: ${mapTime(30000000)}")
    println("repeat 4000만회, array: ${arrayTime(40000000)}, map: ${mapTime(40000000)}")
    println("repeat 5000만회, array: ${arrayTime(50000000)}, map: ${mapTime(50000000)}")
    println("repeat 6000만회, array: ${arrayTime(60000000)}, map: ${mapTime(60000000)}")
    println("repeat 7000만회, array: ${arrayTime(70000000)}, map: ${mapTime(70000000)}")
}

//출력
repeat 100만회, array: 0.012976, map: 0.1315592
repeat 1000만회, array: 0.1056955, map: 1.2990614
repeat 2000만회, array: 0.2796117, map: 1.8312339
repeat 3000만회, array: 0.307373, map: 2.7570212
repeat 4000만회, array: 0.4013876, map: 4.2946401
repeat 5000만회, array: 0.6792158, map: 5.4680324
repeat 6000만회, array: 0.8924631, map: 8.086752
repeat 7000만회, array: 0.7252884, map: 11.2050608

⇒ Array의 경우 횟수에 무관해 보일 만큼 소요시간의 차이가 없고 매우 빠르다.

⇒ HashMap의 경우 대략 1000만회당 1초가 소요된다.

HashMap이 느린 이유?

hashMap의 저장/접근의 시간복잡도는 O(1)로 Array와 동일하다.

그렇다면 왜 결과가 더 느리게 나온걸까..?

hashMap이 저장/접근이 O(1)이라고 하는 이유는 key를 hash값으로 바꾸는 과정이 단순 연산이기 때문이다. 하지만 이는 hash 충돌과 load factor에 따른 확장을 고려하지 않은 수치이다.

실제론 숨겨진 두개의 과정이 더 발생한다.

• hash 충돌 해결 방식에 따라 다르겠지만, hash 충돌이 발생하면 추가적인 탐색이 반드시 필요