해시맵(HashMap)

이번 글에서는 HashMap에 대해서 알아보도록 할텐데, 그 전에 먼저

Hash와 Map에 대해서 알아보도록 하자.

 

해시(Hash)와 맵(Map)

---

해시(Hash)는 어떠한 임의 길이의 데이터(Key)를 고정된 길이의 해시값으로 변경하는 단방향 암호화를 말한다.

이러한 해시값은 해시함수에 의해서 결정되며, 해시값으로부터 원본 데이터인 Key를 구할 수 없다는 특징이 있다.

좀 더 자세한 설명은 아래의 링크에서 확인할 수 있다.

https://angangmoddi.tistory.com/289

해시(Hash)란?

 

그렇다면 맵(Map)은 무엇일까?

맵은 자료구조의 하나로서, Key와 Value쌍으로 이루어져 Key를 통해 Value에 접근하도록 되어있다.

위의 그림을 보면 왼쪽이 Key, 오른쪽이 Value로써 이름이라는 Key를 통해 홍길동이라는 Value에 접근할 수 있다.

이렇게 Key와 Value가 매칭되는것을 매핑(mapping)이라고 한다.

 

또한 Map은 Key의 중복을 허용하지 않는다는 특징을 가지고 있다.

Java나 Kotlin등에선 Map으로, Python등에선 Dictionary라는 이름으로 명칭된다.

 

해시맵(HashMap)

---

이제 해시맵이 무엇인가에 대해서 알아보도록 하자.

위에서 말한 해시와 맵을 결합하여, Key를 해싱하여 해싱한 해시값을 통해 Value에 접근하는 구조로 되어있다.

 

그러면 이러한 해시맵은 왜 사용하는걸까?

기존의 맵의 경우 Key를 통해서 Value에 접근하는데, 이를 위해서는 우리가 입력한 Key를 맵에서 조회해야한다.

이때 Key를 조회하기 위해서 선형 탐색(Linear Search)을 사용하는데,

이 작업은 각각의 Key들을 일일이 대조해보기 때문에 평균적으로 O(n)의 시간을 소비하게된다.

 

이는 맵의 크기, 즉 저장된 데이터가 많아질수록 계속해서 늘어나게 되기 때문에

이러한 불필요한 시간을 줄이기 위하여 해시맵을 사용하여 해시 탐색을 통해 해싱된 Key로 빠르게 Value에 접근하는 것이다.

해시 탐색을 사용하면 어떤 데이터에 접근하든 O(1)의 시간을 소비하기 때문에 Value접근 시간을 줄일 수 있다.

(충돌이 일어나지 않는다는 가정하에)

 

선형 탐색이나 해시 탐색이 뭔지 궁금하다면 아래의 링크로 가시길 바란다.

https://angangmoddi.tistory.com/273

탐색 알고리즘(선형, 이진, 해시)

전화번호부를 이러한 해시맵 구조로 구현한다고 생각해보자.

그러면 위와 같이 Key를 해싱한 해시값을 Index로 하여, 이와 매칭되는 Value(Bucket)에 바로 접근이 가능하다.

 

그럼 이제 실제로 Kotlin에서 해시맵을 사용해보도록 하자.

Kotlin에서 이미 HashMap이 구현되어 있기 때문에, 우리가 힘들게 이를 구현할 필요는 없다.

fun main() {
    val t_directory = HashMap<String, String>()   //HashMap선언, Generic의 앞은 Key, 뒤는 Value

    //HashMap에 데이터 추가(put)
    t_directory.put("고길동", "010-1234-xxxx")
    t_directory.put("둘리", "010-2345-xxxx")
    t_directory.put("도우너", "010-3456-xxxx")
    t_directory.put("또치", "010-4567-xxxx")
    t_directory.put("마이콜", "010-5678-xxxx")
    t_directory.put("희동이", "010-6789-xxxx")

    println(t_directory)

    //HashMap에서 Key와 매칭되는 Value획득(get)
    println("고길동 : ${t_directory.get("고길동")}")

    //HashMap에 있는 Key에 매칭되는 Value를 변경(앞은Key, 뒤는 변경할 Value)
    t_directory.replace("둘리", "010-9874-oooo")

    //HashMap에 해당 Key가 존재하는지 확인(True, False반환)
    println(t_directory.containsKey("둘리"))

    println("Keys: ${t_directory.keys}")

    //HashMap에서 해당 Key와 그에 매칭되는 Value쌍 삭제
    t_directory.remove("도우너")

    println(t_directory)

    //HashMap초기화(비우기)
    t_directory.clear()
}

 

이외의 HashMap관련 함수는 Kotlin공식 문서에서 확인할 수 있다.

https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-hash-map/

HashMap - Kotlin Programming Language