List, Set, Map to Kotlin

우리는 자료구조를 분류할때 선형과 비선형을 기준으로 분류를 했었다. 그리고 분류한 자료구조들을 하나씩 공부해나갈 예정이다. 하지만 그 전에 Collection에있는 List, Set, Map을 학습하고자 한다.

 

Kotlin에는 크게 List, Set, Map 3가지 Collection이 있다.

이 3가지 Collection은 중복을 허용하는지, 순서가 보장되는지에 따라 구분할 수 있다.

참고로, Kotlin Collection은 Mutable Collection과 Immutable Collection으로 구분해 사용한다. 둘의 차이는 변경이 가능한가, 불가능한가이다. List, Set, Map 모두 Mutable과 Immutable Collection을 지원한다.

 

List

---

List는 데이터가 저장될때 필요에 의해 자동으로 늘어나며 데이터가 저장되거나 삭제될 때 순서를 지키는 Collection이다.

List는 get(index)도 지원하고 배열처럼 [index]도 지원한다.

val list = listOf<String>("a", "b", "c", "d")
// val list = mutableListOf<String>("a", "b", "c", "d") - Mutable Collection
println("list.size: ${list.size}")
println("list.get(2): ${list.get(2)}")
println("list[3]: ${list[3]}")
println("list.indexOf(\"d\"): ${list.indexOf("d")}")

List의 내부 항목은 다른 게시글에서 상세히 다뤄보겠다.

 

 

Set - HashSet, TreeSet

---

Set은 중복을 허용하지 않는 Collection이다. Set에 있는 아이템들의 순서는 특별히 정해저 있지 않으며 Null을 가질 수 있다. Set은 List와 같이 Index를 통한 객체 접근은 불가능하다. 

 

val set = setOf<String>("a", "b", "c", "d")
// val set = mutableSetOf<String>("a", "b", "c", "d") - Mutable Collection
println(set)
println("set.size: ${set.size}")
println("set.contains(a): ${set.contains("a")}")
println("set.isEmpty(): ${set.isEmpty()}")

 

HashSet vs Set

HashSet과 Set의 가장 중요한 차이점은 Mutability 라 할 수 있다. Set을 MutableSet으로 사용하는 방법을 방금 배웠기 때문에 왜 굳이 HashSet을 사용해야 하는지 물을 수 있다. HashSet은 구체적인 유형을 지정하지 않는다. 이는 성능, 메모리 사용 등을 개선하기 위해 향후에도 변경될 수 있도록 하기 위한 것이다.

이런 의미에서 Set은 효율적이고 Immutable이며 구체적인 유형을 지정할때 사용되어야 한다.

만약 구체적인 유형을 지정하고 Mutable이고 싶다면 그때는 MutableSet을 사용하면 된다.

val hashSet = HashSet<String>()  //빈 HashSet 생성
val hashSet2 = HashSet<String>(5) //초기 용량이 5인 HashSet 생성
val hashSet3 = HashSet<String>(5,0.8f)   //초기 용량이 5이고 load factor가 0.8인 HashSet 생성
val hashSet4 = HashSet<String>(hashSet)  //Collection을 인자로 받아 HashSet 생성

 

TreeSet vs HashSet

우리는 이전의 게시글에서 Tree라는 자료구조가 있다는것을 알았다. TreeSet은 바로 이 Tree라는 자료구조를 이용한 것이다.

Tree의 구조에 대해서 간단하게 설명하자면 Tree는 계층적인 자료를 표현하는데 주로 이용되는 자료구조이다. 그림의 원들은 노드라고 하며 관계에 따라 이름이 주어지게 된다. 노드들이 연결되어 전체 데이터를 관리하게 된다.

 

TreeSet이 바로 이런 Tree의 특징을 이용한 것이라고 할 수 있다. 랜덤한 순서를 갖는 HashSet과 다르게 TreeSet은 정렬된 순서를 가지게 된다. TreeSet의 단점은 Null값을 가질 수 없다는 것이다. 당연하게도 순서를 가지면 성능은 자연스럽게 안좋아지기 마련이다. TreeSet은 HashSet보다 느리다는 단점도 있다.

val treeSet = TreeSet<Int>()    //빈 TreeSet 생성
val treeSet2 = TreeSet<Int>{ o1, o2 -> o2.compareTo(o1) } //Comparator를 인자로 받아 역순으로 정렬하는 TreeSet 생성
val treeSet3 = TreeSet(treeSet) //SortedSet을 인자로 받는 TreeSet
val treeSet4 = TreeSet(arrayListOf(2,2,3,4))    //Collection을 인자로 받는 TreeSet

	순서	Null	시간 복잡도
HashSet	랜덤한 순서	가능	O(1)
TreeSet	정렬된 순서	불가능	O(logN)

 

 

Map - HashMap, TreeMap, Hashtable

---

Map은 key와 value를 짝지어 저장하는 Kotlin Collection이다. Map의 key는 유일해야하며 동일한 key는 허용되지 않으며 순서를 보장하지 않는다. Map은  get(index)도 지원하고 배열처럼 [index]도 지원한다. keys와 values를 호출하게 되면 key와 value값으로 구성된 Set을 리턴해준다

 

val numbersMap = mapOf<String, String>("1" to "one", "2" to "two", "3" to "three")
println("numbersMap: $numbersMap")
// val numbersMap = mutableMapOf<String, String>("1" to "one", "2" to "two", "3" to "three")
val numbersMap2 = mapOf(Pair("1", "one"), Pair("2", "two"), Pair("3", "three"))
println("numbersMap2: $numbersMap2")

 

사실 위에서 공부했던 HashSet과 TreeSet은 HashMap과 TreeMap을 기반으로 만들어진 것들이다. 그래서 각각을 생성하는 방법만 나열하고 지나가도록 하겠다.

TreeMap

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 생성

 

HashMap

val hashMap = HashMap<String, Int>()  //빈 HashMap 생성
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 생성

 

Hashtable

Hashtable은 HashMap과 같이 Key와 Value로 데이터를 저장하는 자료구조이다. 사실 Hashtable을 HashMap의 어머니 격이라고도 말할 수 있겠다. Hashtable을 개선한 버전이 HashMap이라고 말할 수 있기 때문에 우리는 굳이 Hashtable을 쓸 필요가 없다.

 

Hashtable vs HashMap

둘의 사용법은 거의 동일하다. 다만 몇가지의 차이가 존재한다.

1. Hashmap은 동기화가 되지 않으며 Hashtable은 동기화 된다.

2. Hashmap은 하나의 null key 와 여러개의 null value 를 허용하지만 Hashtable은 null이 허용되지 않는다.

 

---

이렇게 해서 간단하게 List, Set, Map이 무엇인지, 어떻게 만드는지 알아보았다. 알고리즘을 이용하는 과정에서 수 없이 이것들을 사용하게 될 것이니 확실하게 구조를 파악할 필요가 있다.

 

Reference

https://milkoon1.tistory.com/44

자료 구조 list, set, map의 차이

https://codechacha.com/ko/collections-in-kotlin/

Kotlin - Collections 소개 및 사용법 정리 (List, Map, Set)

https://stackoverflow.com/questions/59620326/difference-between-setof-and-hashsetof-in-kotlin

Difference between setOf and hashSetOf in Kotlin