[Kotlin] HashMap, HashSet, LinkedHashSet

 

HashMap

 

Q. Search 연산시 HashMap 에서는 무조건 bucket index 부터 찾고 LinkedList 를 순회하나?

yes, Separate chaining 을 사용하나, java 8 부터는 내부 노드 개수가 8개 이상이면 Red-Black Tree 를 사용한다.

  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        // ..
}

여기서 hash 는 무엇일까..

 

Q. Wrapper class (Integer, Long)  는 key == value 인가?

 

Q. HashCode 비교 -> Key 비교 아닌가?

 

Q. HashCode 자체는 HashMap 에 자체적으로 저장을 하지 않는 구조인가?

 

HashSet

해시테이블로 자신의 키가 곧 값이 되는 자료구조다.

2가지 특징을 알고있어야한다.

1. 데이터 저장과 입/출력의 순서 보장을 하지 않음
2. 배열 기반으로 데이터 관리

 

    @Test
    fun testHashSet() {
        val hashSet = HashSet<Int>(16, 0.75f)
		30 -> 28 -> 26 ... 2
        for (num in 30 downTo 1 step 2) {
            hashSet.add(num)
        }

        for (num in hashSet) {
            print("$num ")
        }
        // [Print]
        // 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
    }

이 예제를 보면 어? 입력 순서가 보장되지 않는다고 했는데 오름차순으로 출력되는 것을 볼 수 있다.

입출력 순서를 보장한게 아니라 해시테이블 내에 저장될 때 정렬 기준인 hashCode() 가 숫자라 작은 수에 대한 해시 값이 테이블 상단에 위치했을 뿐이다.

이는, 문자열로 다시 테스트해보면 입출력 순서가 보장되지 않음을 알 수 있다.

    @Test
    fun testHashSet() {
        val hashSet = HashSet<String>(16, 0.75f)

        hashSet.add("Falcon")
        hashSet.add("NAVER Webtoon")
        hashSet.add("NAVER Financial")

        for (str in hashSet) {
            println("$str")
        }
        // [Print]
        // NAVER Webtoon
        // NAVER Financial
        // Falcon
    }

 

LinkedHashSet

1. 데이터 저장과 입/출력 순서를 보장함
2. 배열 기반으로 데이터 관리 

HashSet 과 달리 입력한 순서에 따라서 저장된다.

    @Test
    fun testHashSet() {
        val hashSet = LinkedHashSet<String>(16, 0.75f)

        hashSet.add("Falcon")
        hashSet.add("NAVER Webtoon")
        hashSet.add("NAVER Financial")

        hashSet.forEachIndexed { index, str ->
            println("index: "+ index + " string: " + str)
        }
        // [Print]
        // index: 0 string: Falcon
        // index: 1 string: NAVER Webtoon
        // index: 2 string: NAVER Financial
    }

 

사용시 팁

둘다 내부적으로 리사이즈가 일어나는 배열 기반으로 데이터를 관리하기 때문에

초기 capacity 와 load factor 를 적절히 지정해줘야한다.

Capacity

해시 테이블이 가지고 있는 bucket 의 크기

 

load factor

$$ load factor = \frac{기준\;데이터\;수}{Capacity} $$

 

초기 Capacity 가 16이고 load factor 가 0.75로 지정되어 있다면

HashSet 의 데이터 갯수가 12개를 초과할 때 * 2배로 크기를 늘려(capacity 16 -> 32) 리해싱을 실행한다.

 

리해싱을 자주하는 것은 성능에 영향을 미치므로 (Linked)HashSet 에 담을 데이터 수를 예상할 수 있다면 적절한 Capacity 와 load factor 를 가지고 초기화 해주는 것이 좋다.

 

 

 

참고 자료

https://d2.naver.com/helloworld/831311