Set 자료구조
Q. Set이란 무엇이며, 자바가 제공하는 Set 자료 구조는 어떠한 것이 있나요?
Set은 중복을 허용하지 않고 순서가 없는 데이터의 집합을 의미하는 자료 구조입니다.
자바는 Set 인터페이스를 통해 Set 자료 구조를 제공합니다. 이 인터페이스는 Collection 인터페이스를 상속하며, Set에 특화된 몇 가지 메소드를 추가로 정의합니다. 자바에서 제공하는 주요 Set 구현체는 HashSet, LinkedHashSet, TreeSet 이 있습니다.
Q. 구현체의 대해서 조금 더 자세하게 설명해주세요.
HashSet은 가장 일반적으로 사용되는 Set 구현체로, 내부적으로 해시 테이블을 사용하여 요소들을 저장합니다. 요소들은 저장된 순서와 관계없이 임의의 순서로 저장되며, 평균적으로 O(1)의 시간복잡도를 가집니다.LinkedHashSet은 앞서 HashSet의 특성에서 순서를 추가한 자료구조 입니다. 테이블에 값을 추가하는 것이 아닌 Node 타입을 저장하여 요소의 순서를 저장합니다. 평균적으로 O(1)의 시간복잡도를 가지지만 HashSet보다는 약간 느립니다.TreeSet은 내부적으로 레드-블랙 트리를 사용하여 요소를 정렬된 상태로 유지합니다. 평균적으로 O(log n )의 시간복잡도를 가집니다.
Q. 해시 테이블은 뭔가요?
해시 테이블은 데이터를 저장하고 검색하는 데 효율적은 자료 구조 입니다. 해시 테이블은 해시 함수(Hash Function)를 사용하여 데이터를 배열의 인덱스로 변환한 후, 해당 인덱스 위치에 데이터를 저장하는 방식으로 동작합니다. 이 방식 덕분에 데이터의 삽입, 삭제, 검색 작업을 평균적으로 O(1)의 시간복잡도로 수행 할 수 있습니다. 여기서 간혈적으로 서로 다른 두 개 이상의 데이터가 동일한 해시 값을 가지게 되는 경우가 있는데, 이러한 것을 해시 충돌이라고 합니다.
Q. TreeSet의 레드-블랙 트리가 뭔가요?
레드-블랙 트리는 자가 균형 이진 탐색 트리 중 하나로, 각 노드에 레드 또는 블랙을 부여하여 트리의 균형을 유지하여 삽입, 삭제 모든 경우에서 O(log N)의 시간복잡도를 가지게 합니다. 레드-블랙 트리는 5가지 조건을 가지고 있습니다.
모든 노드는 빨간색 혹은 검은색이다.
루트 노드는 검은색이다.
모든 리프 노드들은 검은색이다.
빨간색 노드의 자식은 검은색이다. 또는 빨간색 노드가 연속으로 나올 수 없다.
모든 리프 노드에서 Black Depth는 같다. 레드-블랙 트리는 삽입할 때 항상 빨간색으로 삽입하고 삼촌 노드의 색깔에 따라 Restructuring과 Recoloring을 시행해서 균형을 맞춥니다.
Last updated