[JAVA] Set 인터페이스

Set 인터페이스

Set은 순서가 없고 중복을 허용하지 않는 집합을 의미한다. 데이터를 중복해서 저장할 수 없으며 입력 순서대로 저장 순서를 보장하지 않는다.List를 구현한 클래스들은 index로 관리하기 때문에 add()를 통해 객체를 저장한다면 저장 순서대로 저장된다. Set은 입력받은 순서와 상관없이 데이터를 집합시키기 때문에 입력받은 순서를 보장하지 않는다.

 

• Set인터페이스를 구현한 대표적인 컬렉션 클래스

HashSet
TreeSet
LinkedHashSet
*LinkedHashSet는 Set임에도 불구하고 입력 순서대로의 저장순서를 보장한다. 그러나 데이터 중복을 허용하지 않는 것은 같다.

 

Set인터페이스의 메서드

Set는 Collection의 자손이기 때문에 Collection인터페이스의 메서드를 포함하고 있다.

메서드	설명
boolean add(Object o)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가한다.
void clear()	Collection의 모든 객체를 삭제한다.
boolean contains(Object o)	지정된 객체(o) 또는 Collection의 객체들이 Collection에 포함되어 있는지 확인한다.
boolean equals(Object o)	동일한 Collection인지 비교한다.
int hashCode()	Collection의 hash code를 반환한다.
boolean isEmpty()	Collection이 비어있는지를 확인한다.
Iterator iterator()	Collection의 Iterator를 얻어서 반환한다.
boolean remove(Object o)	지정된 객체를 삭제한다.
int size()	Collection에 저장된 객체의 개수를 반환한다.
Object[] toArray()	Collection에 저장된 객체를 객체배열(Object[])로 반환한다.
Object[] toArray(Object[] a)	지정된 배열에 Collection의 객체를 저장해서 반환한다.

• 집합과 관련된 메서드(Collection에 변환가 있으면 true, 아니면 false를 반환.)

메서드	설명
boolean addAll(Collection c)	지정된 Collection(c)의 객체들을 Collection에 추가한다 (합집합)
boolean containsAll(Collection c)	지정된 Collection의 객체들이 Collection에 포함되어 있는지 확인한다 (부분집합)
boolean removeAll(Collection c)	지정된 Collection에 포함된 객체들을 삭제한다 (차집합)
boolean retainAll(Collection c)	지정된 Collection에 포함된 객체만을 남기고 나머지는 Collection에서 삭제한다 (교집합)

---

HashSet 클래스

Set인터페이스를 구현한 대표적인 컬렉션 클래스이다. 입력 순서를 보장하지 않고 순서도 보장하지 않는다. 데이터가 정렬되어있을 필요가 없고, 빠르게 중복되는 값인지 찾을때 유용하다. Hash알고리즘과 Set 컬렉션이 합쳐진 것으로  검색 속도가 매우 빠르다. 

해시 알고리즘(Hash  algorithem)

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

자바에서 해시 알고리즘을 이용한 자료구조는 배열과 연결 리스트로 구현된다.

Hash는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환하는 것이라 할 수있다. 이러한 변환하는 역할을 기능을 가지는 함수를 해시 함수라 하며 해시함수를 통해 얻어진 값을 다이제스트(digest)라고 한다.

List 자료구주를 통해 특정값이 있는지 찾아내려면 노드또는 배열을 순회하여 특정 값이 있는지 찾아야 했다. 하지만 해시함수를 사용한다면 동일한 값에 대해서는 동일한 다이제스트를 갖기 때문에 배열을 순회할 필요가 없다. 특정값에 대한 다이제스트는 변하지 않기 때문에 다이제스트의 값을 배열의 인덱스로 활용한다.

동일 값에는 동일한 다이제스트를 갖기 때문에 원소를 추가할 때 마다 해당 원소가 중복되는 원소인지 검사를 할 필요가 없이 다이제스트(index)에 있는 요소만 검사하면 된다.

HashSet의 데이터 저장

boolean add(Object o)을 사용를 사용하여 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인하여 같은 객체가 없으면 저장하고(true반환), 있으면 저장하지 않는다(false 반환).

객체의 중복을 확인하기 위해 boolean add()는 저장할 객체의 equals()와 HashCode()를 호출하여 중복인지 확인한다.

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

import java.util.HashSet;

public class Main {

	public static void main(String[] args) {
		HashSet set = new HashSet();
		set.add("abc");
		set.add("abc");
		set.add(new Person("Kim",20));
		set.add(new Person("Kim",20));
		System.out.println(set);

	}

}

• 실행결과  [abc, Kim : 20, Kim : 20]  객체의 중복을 제거하지 못했다. 객체를 구별하는 기준이 Object의 HashCode()와 equals()를 사용하기 때문이다.

class Person{
	String name;
	int age;
	
	Person(String name, int age){
		this.name = name;
		this.age = age;
	}

	public String toString() {
		return name +" : " + age;
	}
}

 

• 따라서 HashSet에 중복없이 새로운 요소를 추가하기 위해서는 equals()와 HashCode()가 오버라이딩 되어 있어야 중복을 확인할 수 있다.(eqauls()는 iv를 비교하도록, HashCode()는 Objects.HashCode()를 사용하도록)

class Person{
	String name;
	int age;
	
	Person(String name, int age){
		this.name = name;
		this.age = age;
	}
	@Override
	public int hashCode() {
		return Objects.hash(age, name);
	}
	@Override
	public boolean equals(Object obj) {
		if(!(obj instanceof Person)) return false;
		
		Person p = (Person)obj;
		// 나자신(this)의 이름과 나이를 p와 비교
		return this.name.equals(p.name) && this.age == p.age;
		
		
	}
	public String toString() {
		return name +" : " + age;
	}
}

• 오버라이딩된 equals()와 HashCode()를 사용하여 중복을 확인하기 때문에 결과로 [abc, Kim : 20]이 나오게 된다.

HahsSet의 주요 생성자와 메서드

• 생성자

생성자	설명
HashSet()	기본 생성자
HashSet(Collection c)	주어진 컬렉션을 포함하는 HahsSet객체를 생성한다.
HashSet(int initialCapacity)	주어진 값을 초기용량으로 하는 HahsSet객체를 생성한다.
HashSet( int initialCapacity, float loadFactor)	초기용량과 loaclFactor를 지정하는 생성자. loaclFactor : 저장공간이 가득차기 전에 미리 용량을 확보하기 위한 것, 0.7일 경우 저장공간이 70% 채워졌을 때 용량이 2배로 늘어난다(디폴트 값 : 0.75)

• 메서드

메서드	설명
boolean add(Object o)	새로운 객체를 저장한다.
boolean addAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 추가한다.(합집합)
boolean remove(Object o)	지정된 객체를 HahsSet에서 삭제한다.(성공하면 true, 실패하면 false를 반환한다.)
boolean removeAll(Collection c)	주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 HashSet에서 삭제한다.(차집합) (성공하면 true, 실패하면 false)
boolean retainAll(Collection c)	주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제한다.(교집합)
void clear()	저장된 모든 객체를 삭제한다.
boolean isEmpty()	HahsSet이 비어있는지 알려준다.
int size()	저장된 객체의 개수를 반환한다.
Object[] toArray()	저장된 객체들을 객체배열의 형태로 반환한다.
Object[] toArray(Object[] a)	저장된 객체들은 주어진 객체배열(arr)에 담는다.
boolean contains(Object o)	지정된 객체를 포함하고 있는지 알려준다.
boolean containsAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 포함하고 있는지 알려준다.
Iterator iterator()	Iterator를 반환한다.

---

TreeSet 클래스

이진 탐색 트리(binary search tree)로 구현하여 범위 탐색과 정렬에 유리한 컬렉션 클래스이다. HashSet과 마찬가지로 저장 순서를 보장하지 않으며 중복 데이터를 허용하지 않는다. TreeSet은 특정 규칙에 의해 정렬된 형태로 저장되어 LinkedHashSet 클래스를 이용해 HashSet은 정렬이 가능하지만 TreeSet은 따로 정렬이 필요 없으며 정렬되어 있기 때문에 특정 구간의 집합 요소들(범위)을 탑색할 때 유용하다.

이진 탐색 트리

이진트리 

이진 트리는 모든 노드가 최대 2개(0 ~ 2)의 하위 노드를 갖는다. 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)되어 있다.

이진 탐색 트리는 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장하는 이진 트리의 한 종류이며 데이터가 많아질 수록 비교 횟수 증가하여 추가, 삭제에 시간이 더 걸리게 된다.

트리 순회(tree traversal)

이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다. 트리 순회법에는 전위, 중위, 후위 순회법이 있으며, 중위 순회 하면 오름차순으로 정렬된다. 이를 통해 쉽게 정렬을 할 수 있기 때문에 TreeSet은 정렬에 유리하다.

 

TreeSet의 데이터 저장

HashSet과 마찬가지로 객체추가시 boolean add(Object o)을 사용하는데 HashSet은 중복을 확인하기 위해 equals()와 HashCode()를 사용하지만 TreeSet()은 compare()을 사용하여 중복을 확인한다.

 

이진 탐색 트리를 구현하여 이진 탐색 트리와 마찬가지로 저장 횟수가 늘어감에 따라 비교 횟수가 증가하는 것을 알 수 있다.

- 7, 4, 9,1, 5의 순서로 데이터를 저장시 아래의 과정을 거친다, 루트부터 트리를 따라 내려가며 값을 비교하여, 작으면 왼쪽, 크다면 오른쪽에 저장한다.

 

데이터의 크기가 클수록 비교 횟수가 늘어나기 때문에 HashSet보다 데이터 추가, 삭제에 시간이 더 걸리게 된다.

TreeSet의 주요 생성자와 메서드

• 생성자

생성자	설명
TreeSet()	기본 생성자, 객체의 Comparable을 활용하여 비교한다.
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬 기준으로 정렬하는 TreeSet을 저장

• 메서드

메서드	설명
Object first()	정렬된 순서에서 첫 번째 객체를 반환한다.
Object last()	정렬된 순서에서 마지막 객체를 반환한다.
Object ceilling(Object o)	지정된 객체와 같은 객체를 반환. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object floor(Object o)	지정된 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 봔한. 없으면 null
Object higher(Obejct o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object lower(Obejct o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
SortedSet subSet(Obejct fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다. 끝 범위인 toElelment는 범위에 포함되지 않음)
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.

• 범위 검색 메서드

메서드	설명
SortedSet subSet(Object fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다. (끝 범위인 toElement는 범위에 포함되지 않음)
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.