[JAVA ] Set Interface

SET INTERFACE

    •  저장 순서가 없는 데이터의 집합으로, 데이터의 중복을 허용하지 않습니다.

        ex) HashSet, LinkedHashSet( Hash Set의 하위 클래스 ), TreeSet

 

https://coding-factory.tistory.com/554

1. HashSet

•  Hash기능과 Set 컬렉션이 합쳐진 것입니다.

•  Hash Algorithm 에 의해 데이터의 위치를 특정시켜 해당 데이터를 빠르게 검색할 수 있게 만든 것입니다.

•  가장 기본적인 Set 컬렉션의 클래스로  입력순서에 상관없이 저장되어 정렬해주지 않고 중복된 값은 저장하지 않습니다.

•  만약 요소의 저장순서를 유지해야 한다면 LinkedHashSet 클래스를 사용해야합니다.

•  Null 요소도 허용합니다.

 

Hash Algorithm

: 해시 함수를 사용하여 데이터를 해시 테이블에 저장하고 다시 그것을 검색하는 알고리즘

: JAVA에서 해시알고리즘을 이용한 자료구조는 아래와 같이 Array와 LinkedList로 구현됩니다.

: 저장할 데이터의 키 값을 해시함수에 넣어 반환되는 값으로 배열의 인덱스를 구한 후 해당 인덱스에 저장된 연결리스트에 데이터를 저장합니다.

 

Hash Algorithm - TCP SCHOOL.com

HashSet 중복요소 파악 과정 

 

1. hashCode() 메소드를 호출하여 반환된 해시값으로 검색할 범위를 결정합니다.

2. 해당 범위 내의 요소들을 equals() 메소드로 비교합니다. 만일 True가 나오면 동일한 객체로 판단하고 중복저장을 하지 않습니다. 

 

String 객체를 HashSet에 저장할 경우 같은 문자열은 동일한 객체로 간주되고, 다른 문자열을 갖은 String 객체는 다른 객체로 간주합니다.

 

HashSet Implementation

import java.util.*;

class GFG {
	public static void main(String[] args)
	{
		// Creating an empty HashSet
		HashSet<String> h = new HashSet<String>();

		// Adding elements into HashSet
		h.add("India");
		h.add("Australia");
		h.add("South Africa");

		// Adding duplicate elements
		h.add("India");

		// Displaying the HashSet
		System.out.println(h);
		System.out.println("List contains India or not:"
						+ h.contains("India"));

		// Removing items from HashSet
		// using remove() method
		h.remove("Australia");
		System.out.println("List after removing Australia:" + h);

		// Display message
		System.out.println("Iterating over list:");

		// Iterating over hashSet items
		Iterator<String> i = h.iterator();

		// Holds true till there is single element remaining
		while (i.hasNext())
			// Iterating over elements
			// using next() method
			System.out.println(i.next());
	}
}

Output

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

2. LinkedHashSet

•  HashSet과 동일한 구조를 가지지만 LinkedHashSet은 삽입된 순서대로 반복합니다. ( 순서 보장 )

    -  HashSet의 정렬된 버전 

•  HashSet과 마찬가지로 중복 값은 허용하지 않습니다.

3. TreeSet

•  SortedSet Interface 를 구현한 TreeSet은 데이터의 가중치에 따른 순서대로 정렬됨을 보장합니다. 

•  이진 탐색 트리의 구조로 이루어져 있습니다. 

•  HashSet보다 데이터의 추가와 삭제는 시간이 더 걸리지만 검색과 정렬에는 유리합니다. 

•  정렬된 형태로 있다보니 특정 구간의 집합요소들을 탐색할 때 매우 유용합니다.

•  중복되지 않으면서 특정 규칙에 의해 정렬된 형태의 집합을 쓰고 싶을 때 사용합니다. 

 

TreeSet 내부 로직

TreeSet은 기본적으로 Red-Black Tree와 같은 자체 균형 이진 검색 트리의 구현되어 있습니다. 

정렬된 방대한 데이터를 저장하고 연산을 수행하기 위한 가장 효율적인 데이터 구조 중 하나로 간주합니다. 

 

Red-Black Tree

 

Red-Black Tree

: 자가 균형 이진 탐색 트리로서 대표적으로 연관 배열 등을 구현하는데 쓰이는 자료구조

: 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞춥니다.

: 모든 작업에 대해 트리의 높이가 항상 O(log(N))인지 확인하기 때문에 추가, 제거 및 검색과 같은 작업에는 O(log(N)) 시간이 걸립니다.

: 따라서 정렬된 방대한 데이터를 저장하고 연산을 수행하기 위한 가장 효율적인 데이터 구조 중 하나로 간주됩니다.

 

 

 

 

학습에 많은 도움이 된 링크를  참조했습니다. 🙂

 

참조 및 출처

HashSet in Java

Set 컬렉션 클래스

자바[JAVA] - Set Interface( 셋 인터페이스 )

[Java] 자바 TreeSet 사용법 & 예제 총정리