[Java] Set

Benjamin·2023년 9월 25일
Java
0

JAVA

목록 보기
24/28
post-thumbnail

Set

  • 데이터 자료구조 (데이터 컬렉션)중 하나로, 특정한 값들을 저장하는 추상 자료형

  • 값들의 순서가 존재하지 않고, 중복되지 않음
    -> 유한 집합을 컴퓨터 구현한 것

  • 다른 모음(Collection) 타입에서는 특정 원소를 검색하는 것이 주 업무이고, Set은 대상 원소가 집합에 소속되었는지 여부를 검사하는게 주 업무

특징

  • 데이터를 비순차적으로 저장할 수 있는 순열 자료구조
  • 삽입한 데이터가 순서대로 저장되지 않음
  • 수정 가능
  • 같은 요소의 중복 저장을 허용하지 않음

중복을 제거해야 하거나 저장 순서가 중요하지 않을 때 자주 사용된다.

Set 구현 클래스

  1. HashSet
  2. TreeSet
  3. LinkedHashSet

HashSet

해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다.
내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다.

Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.
만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 된다.

코드

import java.util.HashSet;
import java.util.Set;

HashSet<String> hs01 = new HashSet<String>();
Set<String> hs02 = new HashSet<String>();

// add() 메소드를 이용한 요소의 저장
hs01.add("홍길동");
hs01.add("이순신");
System.out.println(hs01.add("임꺽정"));
System.out.println(hs01.add("임꺽정")); // 중복된 요소의 저장

for (String e : hs01) {
    System.out.print(e + " ");
}

hs02.add("임꺽정");
hs02.add("홍길동");
hs02.add("이순신");

hs02.remove("임꺽정");

// iterator() 메소드를 이용한 요소의 출력
Iterator<String> iter02 = hs02.iterator();
while (iter02.hasNext()) {
    System.out.print(iter02.next() + " ");
}
true
false
홍길동 이순신 임꺽정
홍길동 이순신

  • add() 메소드를 사용하여 해당 HashSet에 이미 존재하는 요소를 추가하려고 하면, 해당 요소를 저장하지 않고 false를 반환하는 것을 볼 수 있다.

  • Set은 인터페이스로 직접 생성해서 사용할 수 없고, HashSet, TreeSet, LinkedHashSet 등의 클래스로 구현해서 사용해야 한다.

  • Set은 인덱스로 관리하지 않기때문에 iterator를 사용하거나 향상된 반복문을 사용해 접근할 수 있다.

어떻게 중복된 요소는 저장하지 않을까?

HashSet에 이미 존재하는 요소인지를 파악하기 위해서는 내부적으로 다음과 같은 과정을 거친다.

  1. 해당 요소에서 hashCode() 메소드를 호출하여 반환된 해시값으로 검색할 범위를 결정한다.
  2. 해당 범위 내의 요소들을 equals() 메소드로 비교한다.

따라서 HashSet에서 add() 메소드를 사용하여 중복 없이 새로운 요소를 추가하기 위해서는 hashCode()와 equals() 메소드를 상황에 맞게 오버라이딩해야 한다.

다음예제는 사용자가 정의한 Animal 클래스의 인스턴스를 HashSet에 저장하기 위해 hashCode()와 equals() 메소드를 오버라이딩한 예제이다.

class Animal {
    String species;
    String habitat;

    Animal(String species, String habitat) {
    this.species = species;
    this.habitat = habitat;
}

public int hashCode() { return (species + habitat).hashCode(); }

    public boolean equals(Object obj) {
        if(obj instanceof Animal) {
            Animal temp = (Animal)obj;
            return species.equals(temp.species) && habitat.equals(temp.habitat);
        } else {
            return false;
        }
    }
}

public class Set02 {
    public static void main(String[] args) {
        HashSet<Animal> hs = new HashSet<Animal>();

        hs.add(new Animal("고양이", "육지"));
        hs.add(new Animal("고양이", "육지"));
        hs.add(new Animal("고양이", "육지"));

        System.out.println(hs.size());
    }
}

두번째 예제를 살펴보자.

	public static void main(String[] args) {
		HashSet<Point> set =  new HashSet<>();
		set.add(new Point(1,1));
		set.add(new Point(1,1));
		
		// 출력 결과 : 2
		System.out.println(set.size());
	}
	
	// 좌표를 저장하는 클래스
	public static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x  = x;
			this.y = y;
		}
	}

위처럼 좌표를 저장하는 클래스를 만들었다고 해보자.
사용자의 의도는 set에 좌표를 넣어 중복을 제거하려고 했다고 하면, 의도와는 다르게 중복된 좌표가 들어가게 된다. 즉, set의 사이즈는 1이어야 하는데 2가 되어버린다.

중복된 요소가 들어가는 이유는 사용자가 정의한 클래스가 hashCode()와 equals() 메서드를 오버라이딩 하지 않았기 때문이다.

따라서 아래처럼 오버라이딩하면 문제가 해결된다.

	public static void main(String[] args) {
		HashSet<Point> set =  new HashSet<>();
		set.add(new Point(1,1));
		set.add(new Point(1,1));
		
        // 출력 결과 : 1
		System.out.println(set.size());
		
	}
	
	// 좌표를 저장하는 클래스
	public static class Point{
		int x;
		int y;
		Point(int x, int y){
			this.x  = x;
			this.y = y;
		}
		
		@Override
		public int hashCode() {
			return (String.valueOf(x) + String.valueOf(y)).hashCode();
		}
		
		@Override
		public boolean equals(Object obj) {
			if(obj instanceof Point) {
				Point temp = (Point)obj;
				return x== temp.x && y == temp.y;
			}else {
				return false;
			}
		}
	}

참고
hashCode() 메서드를 간단하게 return (x+y).hashCode()로 하면 안 될까?
->잘 생각해보면 좌표의 합은 다른 좌표여도 같을 수 있다. (2,3)과 (3,2)는 다른 좌표이지만 합은 5로 똑같다.
따라서 좌표의 합을 hashCode로 사용하면 둘은 다른 클래스이지만 같은 hashCode를 가져버리게 된다.
하지만 String으로 변환해서 만든다면 (2,3) 은 "23", (3,2)는 "32"가 되어 다른 hashCode를 가지게 된다.

TreeSet

오름차순으로 정렬되는 특징을 갖고있다.
데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장한다.

이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다.

TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현한다.

TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.

코드

TreeSet<Integer> ts = new TreeSet<Integer>();

// add() 메소드를 이용한 요소의 저장
ts.add(30);
ts.add(40);
ts.add(20);
ts.add(10);

// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
for (int e : ts) {
    System.out.print(e + " ");
}

// remove() 메소드를 이용한 요소의 제거
ts.remove(40);

// iterator() 메소드를 이용한 요소의 출력
Iterator<Integer> iter = ts.iterator();

while (iter.hasNext()) {
    System.out.print(iter.next() + " ");
}

// subSet() 메소드를 이용한 부분 집합의 출력
① System.out.println(ts.subSet(10, 20));
② System.out.println(ts.subSet(10, true, 20, true));

<결과>

10 20 30 40 
10 20 30 
[10]
[10, 20]

위의 예제처럼 TreeSet 인스턴스에 저장되는 요소들은 모두 정렬된 상태로 저장된다.

subSet()

<원형>

1. public NavigableSet<E> subSet(E fromElement, E toElement)
2. public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

①번 라인에서 사용된 subSet() 메소드는 첫 번째 매개변수로 전달된 값에 해당하는 요소부터 시작하여 두 번째 매개변수로 전달된 값에 해당하는 요소의 바로 직전 요소까지를 반환한다.

②번 라인에서 사용된 subSet() 메소드는 두 번째와 네 번째 매개변수로 각각 첫 번째와 세 번째 매개변수로 전달된 값에 해당하는 요소를 포함할 것인지 아닌지를 명시할 수 있다.

LinkedHashSet

삽입된 순서대로 순서를 보장한다.

코드

초기화는 다음과 같이 할 수 있다.

import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
	public static void main(String[] args)  {
		LinkedHashSet<Integer> i2 = new LinkedHashSet(); 
		LinkedHashSet<Integer> i3 = new LinkedHashSet<Integer>(10); // 크기 10으로 선언
		LinkedHashSet<Integer> i4 = new LinkedHashSet<Integer>(Arrays.asList(1, 2, 3, 4)); // 선언과 동시에 초기 값 설정

값 추가 및 삭제는 다음과 같이 할 수 있다.

import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
	public static void main(String[] args)  {
		LinkedHashSet<String> str = new LinkedHashSet<String>(); // LinkedHashSet 선언
		
		// 값 추가
		str.add("Hello1");
		str.add("World2");
		str.add("Hello3");
		str.add("World4");
		
		System.out.println(str); // 결과 출력		
		
		str.remove("World2"); // World2 값 삭제
		System.out.println(str); // 결과 출력	
		
		str.clear(); // 모든 값 삭제
		System.out.println(str); // 결과 출력	
	}
}

<결과>

  • LinkedHashSet는 Linked로 서로 연결하여 값을 관리하기때문에 순서만 관리할 뿐 앞/뒤 데이터만 삭제가 불가능합니다
  • remove(Obejct) 메서드를 사용하여 원하는 값을 제거할 수 있다.

Set 인터페이스 메소드

Set 인터페이스는 Collection 인터페이스를 상속받으므로, Collection 인터페이스에서 정의한 메소드도 모두 사용할 수 있다.

Set 인터페이스에서 제공하는 주요 메소드는 다음과 같다.

참고
https://godsu94.tistory.com/173
http://www.tcpschool.com/java/java_collectionFramework_set
https://code-lab1.tistory.com/238
https://crazykim2.tistory.com/582

profile
Benjamin
이전 포스트

[JAVA] HashSet - 개념 및 구현

다음 포스트

[Java] JSON 라이브러리 사용 방법 (JSONObject, JSONArray) + JsonParser로 파싱하기

0개의 댓글