[Kotlin] Collections 2 — Map (TreeMap, HashMap, LinkedHashMap)

이번 포스트에서는 Map의 하위 클래스라면 사용할 수 있는 함수들과, 객체로 만들어 사용할 수 있는 Map의 하위 클래스들에 대해 알아볼 것이다.

Map interface

Fig1. Map interface의 methods, propety

Fig1에서 연한 노란색이 읽기 전용인 Map의 메서드들이고, 주황색이 변경 가능한 MutableMap의 메서드이다. MutableMap은 Map를 상속받으므로, MutableMap라면 Map의 메서드들도 물론 사용 가능하다. 읽기 전용 Map와 변경 가능한 Map을 생성하는 방법은 Collections 사용하기 포스트에서 ‘Collections 생성 함수’ part를 참조하자. 다른 Collections 포스트와 다르게 Map에는 프로퍼티까지 표시했는데, 이유는 List나 Set에는 없는 key, value가 있기 때문이다. key는 중복될 수 없는 값이기 때문에 Set으로 반환되고, value는 중복이 있을 수 있기에 Collection으로 반환된다. entry란 key, value를 한 쌍으로 묶은 클래스이고, Map의 중첩 인터페이스로 존재한다.

또, Map은 get()과 set() 함수를 좀 더 간단한 문법으로 사용할 수 있다. get과 set이 operator overloading 되어있기 때문에, ‘[]’ 기호로 Map의 entry에 접근하는 것이 가능하다. 예를 들어 map이 MutableMap이고, key가 String 타입이고 value가 Int라고 하자. map.get(“something”) 대신 map[“something]으로 값을 가져오거나, map.set(“set something”,20) 대신 map[“set something”]=20 과 같이 데이터를 저장하는 것이 가능하다.

Map 종류

Fig2. Map interface의 Hierarchy(상속 관계)

만약 자료들을 보관할 자료구조로 Map을 선택하였다면, 다음은 Map 중 어떤 Map을 선택할 것인지 결정해야한다. Fig2는 Map 인터페이스의 하위클래스들이나 인터페이스 목록이다. Map의 종류는 Fig2와 같이 다양하지만, 중요하고 자주 사용할 Map은 TreeMap, HashMap과 LinkedHashMap이다.

Fig3. 포스트에서 다룰 Map들의 Hieararchy

TreeMap

TreeMap은 Tree라는 자료구조를 이용한 Map이다. 본 포스트에서 Tree에 대해서 자세히 다루지는 않지만, 간단히만 알아보자.

Collections1 포스트 에서 LinkedList를 다뤘었다. Fig3을 보면, Tree 역시 Node들이 연결되어 전체 데이터를 관리하는데, LinkedList와 다른 점은 선형적이지 않다는 것이다. LinkedList의 Doubly LinkedList도 하나의 Node가 두 개의 주소를 갖지만, 연결된 두 데이터의 주소가 서로를 가리키기 때문에 직선 형태를 이룬다. Tree는 직선 형태가 아닌 Graph의 한 종류로 2차원의 구조를 갖고, Fig3에서 가장 위에 있는 Node를 Root노드라고 부른다. 또 자신의 노드가 가리키는 노드를 child 노드라고 하고, 자신을 가리키는 노드를 parent 노드라고 한다. Root 노드는 parent 노드가 없는 노드라고 할 수 있다. Fig3에서 적은 주소값은 단순 예시일 뿐이며, Fig3의 단순 Int로 저장된 데이터는 TreeMap에서 key, value형식으로 존재한다.

Fig4. Tree의 구조

Fig4은 Tree 중에서도 Binary Search Tree(BST)라고 부르는 Tree이다. left child 노드의 데이터들은 parent 노드의 데이터 값보다 작고, right child 노드의 데이터들은 parent 노드의 데이터 값보다 크다. 또 Tree가 갖고 있는 노드 중 child의 개수가 2개를 넘지 않는다. LinkedList는 데이터를 검색하는데 O(N)의 시간복잡도를 보이지만, 이런 BST를 이용하면 log 스케일의 검색 속도를 보일 수 있다.

TreeMap은 JVM8 시점에서 Fig4과 같은 Binary Search Tree 중에서도 Red-Black Tree라는 구조를 사용하고 있다. 단순한 Binary Search Tree를 사용하지 않는 이유는 Fig5를 보자.

Fig5. unbalanced BST

만약 처음 추가한 Root 노드의 데이터가 너무 작은 값이거나 너무 큰 값이라면, 극단적인 경우 Tree가 Fig5처럼 선형적으로 구성될 수 있다. 이는 LinkedList와 같은 형태기 때문에, BST의 장점인 빠른 검색 속도를 보일 수 없다. 따라서 BST중에서도 Tree가 LinkedList처럼 되지 않도록 균형을 유지해주는 Red-Black Tree를 이용한다. TreeMap을 iterate하면 데이터에 오름차순으로 접근한다.

TreeMap 생성하기

TreeMap은 다음과 같은 방법으로 생성할 수 있다.

Example1. TreeMap을 생성하는 다양한 방법
fun main(){
    val treeMap = TreeMap<Char, Int>()  //빈 treeMap 생성
    val treeMap2 = TreeMap<Char, Int> {c1, c2 -> c2.compareTo(c1)}  //Comparator를 인자로 받아 key값의 역순으로 정렬하는 treeMap 생성
    val treeMap3 = TreeMap<Char, Int>(treeMap2) //SortedMap이나 Map을 인자로 받아 treeMap 생성
}

단, TreeMap의 생성자에 첫 번째 인자인 Key의 자료형은 Comparable 인터페이스를 구현하고 있는 클래스이거나 Comparator를 입력해주어야 한다.

TreeMap— time complexity

Fig6. TreeMap BigO

TreeMap의 데이터 접근, 추가, 제거 모두 log 스케일의 속도를 보인다. 여기서 log의 밑은 BST이기 때문에 10이 아닌 2가 된다. 시간 복잡도를 표현할 때는 2를 생략하여 표기한다. 또 Key를 통한 검색은 똑같이 log 스케일의 속도이나 Value를 통한 검색은 O(N)의 시간 복잡도를 보인다.

TreeMap 사용하기

TreeMap을 생성했다면 본 포스트 위쪽의 Map Interface의 메서드를 사용하여 데이터에 접근, 데이터를 추가, 삭제, 검색 등을 할 수 있다. Map Interface는 Collection Interface를 상속받으므로, Collection Interface의 메서드도 사용하고 TreeMap의 다른 메서드들도 사용하면 된다. Fig3에서 볼 수 있듯이, TreeMap은 NavigableMap을 상속받고, NavigableMap은 SortedMap을 상속받는다. NavigableMap과 SortedMap에는 TreeMap이 정렬되어 있기에 사용할 수 있는 함수들을 포함하고 있다. TreeMap은 앞으로 살펴볼 HashMap이나 LinkedHashMap보다 전반적으로 더 느린 속도를 보이지만, NavigableMap과 SortedMap의 함수들을 사용하여 정렬된 상태에서 장점을 살리면 더 구체화된 목적에 사용할 수 있다.

Example2. TreeMap 사용하기
fun main() {

    //TreeMap 생성 및 값 입력하기
    val treeMap = TreeMap<Char, Int>()  //빈 treeMap 생성
    treeMap['C']=11
    treeMap['E']=8
    treeMap['D']=2
    treeMap['A']=14
    treeMap['B']=6

    //treeMap 출력하기
    println("println(treeMap) : $treeMap")
    println()

    //treeMap iterate하기
    println("iterating treeMap : ")
    for(entry in treeMap){
        println(entry)  //entry는 MutableMap.MutableEntry타입이다.
    }
    println()

    //treeMap 은 정렬되어 있는 것이 장점이다.
    println("pros of treeMap : ")
    println("treeMap.headMap('C') : ${treeMap.headMap('C')}")
    println("treeMap.tailMap('C') : ${treeMap.tailMap('C')}")
    println("treeMap.subMap('B','D'): ${treeMap.subMap('B','D')}")

}
/*결과 :
println(treeMap) : {A=14, B=6, C=11, D=2, E=8}
iterating treeMap : 
A=14
B=6
C=11
D=2
E=8
pros of treeMap : 
treeMap.headMap('C') : {A=14, B=6}
treeMap.tailMap('C') : {C=11, D=2, E=8}
treeMap.subMap('B','D'): {B=6, C=11}
Process finished with exit code 0
*/

HashMap

HashMap은 Hash라는 기법을 사용하여 구현된 Map이다. HashMap은 데이터가 추가되는 순서를 유지하지 않으나, Hashing 기법의 특징인 빠른 접근 속도가 장점이다. Hashing 기법이란 key 값에 산술적인 연산을 적용한 값을 table의 주소로 사용하여 데이터를 매핑 하는 것이다. Kotlin에서는 객체의 고유한 값이 key 값으로 사용해 그 결과 값을 객체가 저장된 배열의 주소로 나타낸다. 이 기법을 이용하면 데이터가 저장된 객체들과 일일이 동등성을 비교하지 않고 산술연산으로 데이터에 접근할 수 있기 때문에 빠른 접근 속도를 보인다. 아래 링크는 HashMap에 대해 다룬 포스트이다.

[Kotlin][Data Structure] HashMap

HashMap생성하기

Example3. HashMap을 생성하는 다양한 방법
fun main(){
    val hashMap = HashMap<String, Int>()  //빈 HashMap 생성(초기 용량:16, load factor:0.75)
    val hashMap2 = HashMap<String, Int>(5) //초기 용량이 5인 HashMap 생성
    val hashMap3 = HashMap<String, Int>(5,0.8f)   //초기 용량이 5이고 load factor가 0.8인 HashMap 생성
    val hashMap4 = HashMap<String, Int>(hashMap)  //Map을 인자로 받아 HashMap 생성
}

HashMap— time complexity

Fig7. HashMap BigO

Fig7 은 HashMap의 시간 복잡도를 나타내고 있다. HashMap에서는 collision이 일어날 수 있지만, collision은 고려하지 않은 시간 복잡도이다. 또 Key를 통한 검색은 O(1)의 시간 복잡도를 보이나 Value를 검색하는 것은 O(N)의 시간 복잡도를 보인다.(N은 HashMap이 보관하는 데이터의 개수)

HashMap사용하기

Example4. HashMap 사용하기
fun main() {
    //HashMap 생성 및 값 입력하기
    val hashMap = HashMap<String, Int>()
    hashMap["Apple"]=11
    hashMap["Banana"]=8
    hashMap["Cat"]=2
    hashMap["Dream"]=14
    hashMap["East"]=6

    //hashMap 출력하기
    println("println(hashMap) : $hashMap")
    println()

    //hashMap iterate하기
    println("iterating hashMap : ")
    for(entry in hashMap){
        println(entry)  //entry는 MutableMap.MutableEntry타입이다.
    }
    println()
}
/*결과 : 
println(hashMap) : {Dream=14, Apple=11, Cat=2, East=6, Banana=8}
iterating hashMap : 
Dream=14
Apple=11
Cat=2
East=6
Banana=8
*/

HashMap은 빠른 접근 속도를 보이나, 출력 결과를 보면 알 수 있듯이 데이터를 입력순서대로 저장하거나 정렬하여 저장하지 않는다. 만약 순서대로 저장하고 싶으면 LinkedHashMap을 사용할 수 있다. 또한 HashMap은 배열을 기반으로 데이터를 관리하기 때문에, 데이터의 총 개수를 미리 얼추 알고 있다면 초기 용량을 정해주는 것을 잊지말자.

LinkedHashMap

LinkedHashMap 역시 Hash 기법을 사용하여 구현된 Map이다. HashMap과 다른 점은 기본적으로 데이터를 추가한 순서대로 데이터들을 보관한다는 점이다. 따라서 LinkedHashMap을 iterate하면 추가한 데이터 순서대로 접근할 수 있다. 순서를 유지하면서도 데이터 접근, 추가, 제거, key검색은 HashMap과 동일한 시간 복잡도를 유지하기 때문에 유용한 자료구조이다. 데이터 저장 순서를 기억하기 위해 데이터는 다음 데이터를 가리키는 곳을 알고 있어야한다. 그렇기 때문에 HashMap보다는 저장 공간을 더 필요로 한다. Fig8은 HashMap과 LinkedHashMap의 다른 점을 이해하기 위해 간단히 도식화한 것이다.

Fig8. HashMap, LinkedHashMap 비교

LinkedHashMap 생성하기

Example5. LinkedHashMap을 생성하는 다양한 방법
fun main(){
    //빈 LinkedHashMap 생성(초기 용량:16, load factor:0.75)
    val linkedHashMap = LinkedHashMap<Char, Int>()
    //초기 용량이 5인 LinkedHashMap 생성
    val linkedHashMap2 = LinkedHashMap<Char, Int>(5)
    //초기 용량이 5이고 load factor가 0.8인 LinkedHashMap 생성
    val linkedHashMap3 = LinkedHashMap<Char, Int>(5, 0.8f)
    //초기 용량이 5이고 load factor가 0.8이며 Map에 추가한 순서대로 LinkedHashMap 생성
    val linkedHashMap4 = LinkedHashMap<Char, Int>(5, 0.8f, false)
    //Map을 인자로 받아 LinkedHashMap 생성 
    val linkedHashMap5 = LinkedHashMap<Char, Int>(linkedHashMap)
    //빈 HashMap 생성(초기 용량:16, load factor:0.75)
    val linkedHashMap6 = mutableMapOf<Char, Int>()
    //들어갈 key, value 쌍을 나열해서 LinkedHashMap 만들기
    val linkedHashMap7 = mutableMapOf('A' to 0, 'B' to 1, 'C' to 2) 
}

LinkedHashMap— time complexity

Fig9. LinkedHashMap BigO

LinkedHashMap사용하기

Example6. LinkedHashMap 사용하기
fun main() {
    //LinkedHashMap 생성 및 값 입력하기
    val linkedHashMap = LinkedHashMap<String, Int>()
    linkedHashMap["Apple"]=11
    linkedHashMap["Banana"]=8
    linkedHashMap["Cat"]=2
    linkedHashMap["Dream"]=14
    linkedHashMap["East"]=6

    //linkedHashMap 출력하기
    println("println(linkedHashMap) : $linkedHashMap")
    println()

    //linkedHashMap iterate하기
    println("iterating linkedHashMap : ")
    for(entry in linkedHashMap){
        println(entry)  //entry는 MutableMap.MutableEntry타입이다.
    }
    println()
    //이미 key 값이 존재한다면 그 entry의 순서는 바뀌지 않음
    linkedHashMap["Apple"]=3
    println("println(linkedHashMap) : $linkedHashMap")
    println()
}
/*결과 :
println(linkedHashMap) : {Apple=11, Banana=8, Cat=2, Dream=14, East=6}
iterating linkedHashMap : 
Apple=11
Banana=8
Cat=2
Dream=14
East=6
println(linkedHashMap) : {Apple=3, Banana=8, Cat=2, Dream=14, East=6}
*/

HashMap과는 다르게, LinkedHashMap의 출력 결과를 보면 알 수 있듯이 linkedHashMap은 추가한 key,value쌍 순서대로 출력한다. LinkedHashMap 역시 HashMap과 마찬가지로 배열을 기반으로 데이터를 관리하기 때문에, 데이터의 총 개수를 미리 얼추 알고 있다면 초기 용량을 정해주는 것을 잊지말자.

Reference

TreeMap part

1. [Oracle] “TreeMap (Java Platform SE 7 ) — https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

LinkedHashMap part

2. [Dinesh on Java] “Internal Working of LinkedHashMap in Java” — https://www.dineshonjava.com/internal-working-of-linkedhashmap-in-java/