Set과 Queue -Reboot(3)

학습목표

• Set이 무엇인지
• Queue가 무엇인지
• 왜 Set 을 써야하는지
• 왜 Queue를 써야하는지
• Set은 어디에 쓰이는지
• Queue는 어디에 쓰이는지
• Set의 다른 자료구조와의 차이점은 무엇인지
• Queue의 다른자료구조와의 차이점은 무엇인지
• Set을 구현한 구현체들은 무엇이 있고, 각 차이점은 ?
• Queue를 구현한 구현체들은 무엇이 있고, 각 차이점은?

LinkedHashSet

• LinkedHashSet이란?
• 왜? 어디에 쓰이는가?
• LinkedHashSet의 특징 과 구현원리
• LinkedHashSet이 성능이 제일 안좋다고 했는데 왜 일까??

LinkedHashSet이란?

LinkedHashSet은 순서가 없고 중복이 없는 Set의 특징에서 조금 다르다. 중복은 허용하지 않지만, 입력된 순서를 기억하고있다. 즉, Queue처럼 입력받은 순으로 출력한다.

어디에 쓰일까??

입력된 순서를 받는 Set이므로 ,중복이 없어야 하나, 입력된 순서는 기억하고 있어야 할때 사용될 것이다.

LinkedHashSet의 특징과 구현원리

LinkedHashSet은 HashSet을 상속받았고, 내부적으로 LinkedHashMap을 호출한다.

linkedHashMap은 HashMap에 들어가는 Node에 Key와 Value만 있는것이 아니라, next,prev변수가 추가되어 자기자신의 이전, 이후 노드를 알아낼수 있다. 즉 HashMap에 저장되는 데이터를 DoublyLinkedList의 형태로 저장한것...

아래의 코드를 보면 LinkedHashMap이 forEach문을 사용할때 어떻게 작동하는지 알수 있다.

public final void forEach(Consumer<? super K> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                action.accept(e.key);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }

처음 head부터 tail까지 게속해서 반복하는것을 알수있다. 이런식으로 순서를 유지한체 출력 할 수있는것이다! 이외에는 HashSet과 똑같으므로 생략한다.

알게 된 점

• Set이 무엇인지
  • Set은 Collection을 확장한 인터페이스로, 순서가 없으며 중복을 허용하지 않는 자료구조이다.
• Queue가 무엇인지
• 왜 Set 을 써야하는지
  • 순서가 없고 중복을 허용하지 않기 때문에, 이런 작업에 있어서는 Set을 쓰는것이 성능상 이롭다.
• 왜 Queue를 써야하는지
• Set은 어디에 쓰이는지
  • 순서가 관계없고 데이터가 존재하는지 없는지 여부만 중요할때 쓰인다.
• Queue는 어디에 쓰이는지
• Set의 다른 자료구조와의 차이점은 무엇인지
  • 순서가 없고, 중복을 허용하지 않는다.
• Queue의 다른자료구조와의 차이점은 무엇인지
• Set을 구현한 구현체들은 무엇이 있고, 각 차이점은 ?
  • HashSet
    • HashSet은 내부적으로 HashMap을 호출, 구성관계를 가지고 있다.
    • 순서가 없고, 정렬되어있지 않으며 HashMap을 사용하므로, 추가,삭제, contain등의 시간복잡도는 O(1)이다.
  • TreeSet
    • TreeSet은 이진탐색트리의 형태로 데이터를 저장 한다. 자바에서는 더 개선된 Red-BlackTree로 구현되어있다.
    • 이진탐색트리란 이진탐색과 연결리스트(LinkedList)를 결합한 자료구조이다. 정렬된 탐색에서 큰 효율을 보이는 이진탐색과 추가와 삭제가 가능한 연결리스트를 결합했다.
    • 이진탐색의 뜻은 찾고자하는 배열의 탐색범위가 단계를 거칠수록 반절로 줄어들기 때문에 붙여졌다.
    • 이진탐색은 탐색하고자 하는 범위의 임의의 중간값 X를 선택, 찾고자 하는 값 Y와 비교하여 Y가 작으면 좌측으로, 크면 우측의 범위를 대상으로하여 동일한 탐색을 실행한다.(술게임 업다운에 적용됨)
    • 이때 이진탐색의 시간복잡도는 O(logN)을 보장한다.
    • 빅오표기법은 알고리즘의 효율성을 나타내는 지표로, 시간복잡도와 공간복잡도가 있다.
    • 빅오표기법은 상수항을 무시하고, 가장 지배적인 항을 제외한 나머지 항은 무시한채 표기한다.
    • N개의 노드를 가진 일반적인 이진탐색트리는 모든연산에 대해 O(log₂N)을 보장한다. 하지만 편향적인 이진탐색트리에서는 노드의 갯수 N = 높이 H 가 되는 일도 발생할 수있다. 즉 최악의 경우 O(N)이 되어버린다.
    • 최악의 경우 O(N)의 시간복잡도를 갖게 되는 이진탐색트리를 개선한 것이 Red-Black트리이다. Red-Black트리는 높이를 log₂N으로 한정할수있다. 즉 모든 연산에 대해서 시간복잡도가 O(log₂N)을 보장한다.
    • Red-Black 트리의 회전,삽입,삭제 연산에 대해서 꼭! 이해하자
  • LinkedHashSet
    • LinkedHashSet이란?
      • 입력된 순서를 기억하고, 그 순서대로 출력한다. TreeSet처럼 정렬이 아닌, 입력순서대로 순서를 기억한다.
    • 왜? 어디에 쓰이는가?
      • 중복을 허용하지 않고, 입력된 순서를 기억해야 할때 쓰인다.
    • LinkedHashSet의 특징 과 구현원리
      • LinkedHashSet은 HashSet에 들어가는 노드들이 key와 value외에, next,prev 값을 가짐으로써, 나 이전과 이후의 순서를 기억하고 있는 자료구조이다.
      • forEach문코드를 보면 head 노드부터 next의 변수를 차례로 호출하는것을 볼수있다.
      • 이외에는 HashSet과 같은 원리이다.
    • LinkedHashSet이 성능이 제일 안좋다고 했는데 왜 일까??
      • 알수없음.... 책이 잘못나온걸까?... 인터넷에 검색해봐도 나오지 않음 일단 질문했음
• Queue를 구현한 구현체들은 무엇이 있고, 각 차이점은?

Reference

레드블랙트리-1(개요와 삽입까지)

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

[Java] 트리 Tree 3 - 이진 탐색 트리

알고리즘 :: 이진트리와 순회 전위순회(preorder), 중위 순회(inorder), 후위 순회(postorder) C/C++ 구현

트리(tree)와 이진트리(binary tree)

탐색, 삽입, 삭제 알고리즘 및 시간복잡도 분석