Set 자료구조
Q. Set이란 무엇이며, 자바가 제공하는 Set 자료 구조는 어떠한 것이 있나요?
Set은 중복을 허용하지 않고 순서가 없는 데이터의 집합을 의미하는 자료 구조입니다.
자바는 Set 인터페이스를 통해 Set 자료 구조를 제공합니다. 이 인터페이스는 Collection 인터페이스를 상속하며, Set에 특화된 몇 가지 메소드를 추가로 정의합니다. 자바에서 제공하는 주요 Set 구현체는 HashSet, LinkedHashSet, TreeSet 이 있습니다.
Q. 데이터를 set을 구현체로 사용하는 collection에 넣으면 이상하게도 ordering을 보장하지 않는 특성을 가짐에도 여러번 반복적으로 데이터를 담은 뒤 관측했을때 순서를 보장하는 것처럼 보이는 경우가 있습니다. 왜 그런 것일까요?
순서를 보장하지 않은 HashSet은 내부적으로 HashMap을 사용해서 데이터를 저장합니다. HashMap은 해시 함수를 통해 각 요소에 해시값을 게산하고, 그 값을 기반으로 데이터를 해시 테이블의 특정 버킷에 배치합니다. 여기서 중요한 점은 해시 함수가 동일한 입력에 대해 항상 동일한 해시값을 반환한다는 점 입니다.
그렇기 때문에, 만약 사용자가 동일한 데이터를 동일한 순서로 HashSet에 넣고, JVM등 환경이 변하지 않는다면, 해시값 계산과 버킷 배치가 매번 똑같이 일어나면서 출력 순서가 우연히 일정하게 보일 수 있습니다. 특히 데이터 크기가 작고 해시 충돌이 거의 없을 때, 내부 배열의 인덱스 순서대로 요소가 배치되면서 삽입 순서와 비슷하게 출력될 가능성이 높아지기도 합니다.
Q. 구현체의 대해서 조금 더 자세하게 설명해주세요.
HashSet은 가장 일반적으로 사용되는 Set 구현체로, 내부적으로 해시 테이블을 사용하여 요소들을 저장합니다. 요소들은 저장된 순서와 관계없이 임의의 순서로 저장되며, 평균적으로 O(1)의 시간복잡도를 가집니다.LinkedHashSet은 앞서 HashSet의 특성에서 순서를 추가한 자료구조 입니다. 테이블에 값을 추가하는 것이 아닌 Node 타입을 저장하여 요소의 순서를 저장합니다. 평균적으로 O(1)의 시간복잡도를 가지지만 HashSet보다는 약간 느립니다.TreeSet은 내부적으로 레드-블랙 트리를 사용하여 요소를 정렬된 상태로 유지합니다. 평균적으로 O(log n )의 시간복잡도를 가집니다.
Q. HashSet과 TreeSet을 비교했을 때, 어떤 상황에서 TreeSet을 굳이 사용할 필요가 없을까요?
HashSet은 평균적으로 O(1)의 시간복잡도를 제공하는 반면, TreeSet은 내부적으로 레드-블랙 트리를 사용하기 때문에 삽입, 삭제, 검색에서 O(log n)의 시간복잡도를 가집니다. 이런 차이 때문에 단순히 중복 제거나 빠른 검색만 필요한 상황에서는 TreeSet을 굳이 사용할 필요가 없죠. TreeSet은 데이터를 정렬된 상태로 유지하는 데 추가적인 연산 비용이 들기 때문에, 정렬이 필요 없는 경우엔 오버헤드가 될 수 있습니다.
예를 들어, 데이터가 정렬될 필요 없이 그냥 중복 없이 저장만 하면 되는 경우라면 HashSet이 훨씬 효율적입니다. 만약 대용량의 데이터를 중복없이, 정렬이 필요한 경우 TreeSet을 사용하는게 더 효과적입니다.
Q. 해시 테이블은 뭔가요?
해시 테이블은 데이터를 저장하고 검색하는 데 효율적은 자료 구조 입니다. 해시 테이블은 해시 함수(Hash Function)를 사용하여 데이터를 배열의 인덱스로 변환한 후, 해당 인덱스 위치에 데이터를 저장하는 방식으로 동작합니다. 이 방식 덕분에 데이터의 삽입, 삭제, 검색 작업을 평균적으로 O(1)의 시간복잡도로 수행 할 수 있습니다. 여기서 간혈적으로 서로 다른 두 개 이상의 데이터가 동일한 해시 값을 가지게 되는 경우가 있는데, 이러한 것을 해시 충돌이라고 합니다.
Q. 해시 충돌이 발생했을 때 HashSet은 어떻게 처리하나요?
HashSet은 자바에서 내부적으로 HashMap을 기반으로 구현되어 있습니다. HashMap은 키-값 쌍을 저장하는데, HashSet은 이 구조에서 값을 저장하는 대신 키만 사용해서 중복을 방지합니다. 여기서 해시 충돌이 발생 하면 'Searate Chaining'이라는 방식을 사용합니다.
Searagte Chaining은 같은 해시값을 가진 요소들을 하나의 '해시 버킷'에 연결 리스트 형태로 묶어서 저장합니다. 예를 들어, 두 개의 요소가 같은 해시값을 가지면, 해당 버킷에 연결 리스트가 생기고 그 안에서 요소들이 순차적으로 추가되는 것이죠. 이 방식 덕분에 충돌이 발생해도 데이터가 손실되지 않고 모두 저장될 수 있지만, 연결 리스트가 길어지면 검색이나 삽입 시 시간이 O(n)에 가까워질 수 있다는 단점이 있습니다. 이를 보완하기 위해 자바 8부터는 연결 리스트의 길이가 8이라는 일정 임계값을 넘으면, 그 버킷의 연결 리스트를 레드-블랙 트리로 변환합니다.
결과적으로, HashSet은 충돌이 적을 때는 평균 O(1)의 시간복잡도를 유지하고, 충돌이 많아지더라도 레드-블랙 트리 변환을 통해 성능을 최적화해서 안정적으로 효율성을 제공합니다.
Q. TreeSet의 레드-블랙 트리가 뭔가요?
레드-블랙 트리는 자가 균형 이진 탐색 트리 중 하나로, 각 노드에 레드 또는 블랙을 부여하여 트리의 균형을 유지하여 삽입, 삭제 모든 경우에서 O(log N)의 시간복잡도를 가지게 합니다. 레드-블랙 트리는 5가지 조건을 가지고 있습니다.
모든 노드는 빨간색 혹은 검은색이다.
루트 노드는 검은색이다.
모든 리프 노드들은 검은색이다.
빨간색 노드의 자식은 검은색이다. 또는 빨간색 노드가 연속으로 나올 수 없다.
모든 리프 노드에서 Black Depth는 같다. 레드-블랙 트리는 삽입할 때 항상 빨간색으로 삽입하고 삼촌 노드의 색깔에 따라 Restructuring과 Recoloring을 시행해서 균형을 맞춥니다.
Last updated