출처: https://www.boostcourse.org/mo234/lecture/154316?isDesc=false

Set

• 정해진 순서가 없는 요소들의 집합
• 집합의 개념이기 때문에 동일한 요소를 중복해서 가질 수 없다.
• 생성 헬퍼 함수: 불변형은 setOf(), 가변형은 mutableSetOf()

불변형 Set

package chap05.section2

fun main() {
    val mixedTypeSet = setOf("Hello", 5, "world", 3.14, 'c')
    val intSet: Set<Int> = setOf<Int>(1, 4, 5, 5, 5) 
    println(mixedTypeSet)
    println(intSet) // 중복된 요소 중에 하나만 출력 
}

[Hello, 5, world, 3.14, c]
[1, 4, 5]

가변형 Set

package chap05.section2

fun main() {
    val animals = mutableSetOf("Lion", "Dog", "Cat", "Python", "Hippo")
    animals.add("Dog") // 이미 존재하므로 변화 없음.
    println(animals)
    animals.remove("Python")
    println(animals)
}

[Lion, Dog, Cat, Python, Hippo]
[Lion, Dog, Cat, Hippo]

Set의 여러가지 자료구조

hashSetOf() 함수

• 이 헬퍼 함수를 통해 생성하면, 해시 테이블에 요소를 저장할 수 있는 자바의 HashSet 컬렉션을 만든다.
• HashSet은 불변성 선언이 없기 때문에 기본적으로 추가 및 삭제가 가능하다.

cf) 해시 테이블: 내부적으로 키와 인덱스를 이용해 검색과 변경 등을 매우 빠르게 처리할 수 있는 자료구조

위의 그림에서 해시 함수를 통해 key에 해당하는 bucket을 빠르게 찾을 수 있다.

package chap05.section2

fun main() {
    val intHashSet: HashSet<Int> = hashSetOf(6, 3, 4, 7) // 불변성이 없음.
    intHashSet.add(5)
    intHashSet.remove(6)
    println(intHashSet)
}

[3, 4, 5, 7]

• HashSet의 요소들은 입력 순서와 상관없이 내부적으로 키에 따라 배치된다.
• 정렬 기능은 없지만, 해시 값을 통해 요소를 찾아내므로 검색 속도는 O(1)의 시간복잡도이다. (즉, 필요한 값을 요청과 즉시 바로 찾아냄.)

자바의 TreeSet 컬렉션

sortedSetOf() 함수

• 자바의 TreeSet 컬렉션을 정렬된 상태로 반환
• java.util.* 패키지를 import 해야함.
• TreeSet은 저장된 데이터의 값에 따라 정렬 (이진 탐색 트리의 단점을 보완한 레드-블랙 트리 자료구조 사용)
• HashSet 보다 성능이 조금 떨어지고 데이터를 추가 및 삭제하는데 시간이 걸리지만, 검색과 정렬이 뛰어나다는 장점을 갖고 있음.

이진 탐색 트리와 Red-Black 트리

이진 탐색 트리가 한쪽으로 치우친 트리 구조일 경우, 트리 높이 만큼 시간이 걸리는 최악의 경우가 발생할 수 있다.

레드-블랙 트리는 이 단점을 Red와 Black의 색상으로 치우친 결과 없이 구분되게 해서, 최악의 경우에도 검색 등의 처리에서 일정 시간을 보장해주는 자료구조이다.

package chap05.section2

import java.util.*

fun main() {
    val intSortedSet: TreeSet<Int> = sortedSetOf(4, 1, 7, 2)
    intSortedSet.add(6) 
    intSortedSet.remove(1) 
    println("intSortedSet = $intSortedSet") // 오름차순 정렬된 결과 
    intSortedSet.clear() 
    println("intSortedSet = $intSortedSet") 
}

intSortedSet = [2, 4, 6, 7]
intSortedSet = []

자바의 LinkedHashSet

linkedSetOf() 함수

• 자바의 LinkedHashSet 자료형을 반환하는 헬퍼 함수
• 자료구조 중 하나인 연결 리스트로 구현된 해시 테이블에 요소를 저장
• HashSet, TreeSet 보다 느리지만 데이터 구조상 다음 데이터를 가리키는 포인터 연결을 통해 메모리 저장 공간을 좀더 효율적으로 사용 → 데이터 추가 및 삭제에 용이

---

Map

• 키(key)와 값(value)으로 구성된 요소를 저장 (키와 값은 모두 객체)
• 키는 중복될 수 없지만 값은 중복 저장될 수 있다. (만약 기존에 저장된 키와 동일하면, 기존의 값은 없어지고 새로운 값으로 대체)
• 생성 헬퍼 함수: 불변형은 mapOf(), 가변형은 mutableMapOf()

불변형 Map

val map: Map<key type, value type> = mapOf(key to value [, ...])

package chap05.section2

fun main() {
    val langMap: Map<Int, String> = mapOf(11 to "Java", 22 to "Kotlin", 33 to "C++")
    for((key, value) in langMap){
        println("key = $key, value = $value")
    }
    println("langMap[22] = ${langMap[22]}")
    println("langMap.get(22) = ${langMap.get(22)}")
    println("langMap.keys = ${langMap.keys}") // 맵의 모든 키 출력 (읽기 전용 Set 반환)
}

key = 11, value = Java
key = 22, value = Kotlin
key = 33, value = C++
langMap[22] = Kotlin
langMap.get(22) = Kotlin
langMap.keys = [11, 22, 33]

가변형 Map

package chap05.section2

fun main() {
    val capitalCityMap: MutableMap<String, String>
            = mutableMapOf("Korea" to "Seoul", "China" to "Beijing", "Japan" to "Tokyo")
    println(capitalCityMap.keys)
    println(capitalCityMap.values)

    capitalCityMap.put("UK", "London")
    capitalCityMap.remove("China")
    println(capitalCityMap)

    val addData = mutableMapOf("USA" to "Washington")
    capitalCityMap.putAll(addData) // 맵 자체를 추가
    println(capitalCityMap)
}

[Korea, China, Japan]
[Seoul, Beijing, Tokyo]
{Korea=Seoul, Japan=Tokyo, UK=London}
{Korea=Seoul, Japan=Tokyo, UK=London, USA=Washington}

Map을 위한 기타 자료구조

• Map에서도 자바의 HashMap, SortedMap, LinkedHashMap 같은 자료구조를 사용할 수 있다.
• 생성 헬퍼 함수: hashMapOf(), sortedMapOf(), linkedMapOf()
• SortedMap은 기본적으로 키에 대해 오름차순 정렬된 형태로 사용
• 내부 구조는 앞서 설명했던 Set의 구조와 비슷하게 해시, 트리, 연결 리스트의 자료구조로 구현

package chap05.section2

import java.util.SortedMap

fun main() {
    val hashMap: HashMap<Int, String> = hashMapOf(1 to "Hello", 2 to "World")
    println("hashMap: $hashMap")

    val sortedMap: SortedMap<Int, String> = sortedMapOf(2 to "Apple", 1 to "Banana")
    println("sortedMap: $sortedMap") // 키에 대해 오름차순 정렬 

    val linkedHashMap: LinkedHashMap<Int, String> = linkedMapOf(1 to "Computer", 2 to "Mouse")
    println("linkedHashMap: $linkedHashMap")
}

hashMap: {1=Hello, 2=World}
sortedMap: {1=Banana, 2=Apple}
linkedHashMap: {1=Computer, 2=Mouse}