39. Set, HashSet, TreeSet, LinkedHashSet - 집합

▶ Set 인터페이스

 

- 순서에 상관없이 원소만 저장하고 싶은 경우 집합(Set)을 사용한다.

 

- 동일한 원소를 가질 수 없다.

 

- 해쉬 테이블(Hash Table)

• 집합을 구현하는 가장 잘 알려진 방법이다.

• 각각의 원소에 대해 해쉬 코드란 정수를 계산하며, 해쉬 코드는 대개 객체의 인스턴스 필드로부터 계산된다.

• 각 클래스마다 해쉬 코드를 계산하는 hashCode()를 가지고 있다.

• 해쉬 테이블은 연결 리스트의 배열로 구현되며, 각 리스트는 버킷(bucket)이라고 불린다.

• 순서는 임의적이지만 검색 속도가 빠르다.

• 테이블에서 원하는 객체를 찾기 위해 먼저 객체의 해쉬 코드를 계산하고 테이블의 크기에 맞추어 나머지 연산을 수행한 후에 결과로 나오는 숫자를 테이블의 인덱스로 사용하면 된다.

• 쉽게 말해, 원하는 객체의 해쉬 코드를 테이블의 크기로 나누어서 나온 나머지가 버킷을 대표하는 번호가 된다. 이 때 각 리스트들은 순서가 임의적이다.

- Set 인터페이스를 구현하는 클래스는 HashSet, TreeSet, LinkedHashSet 등이 있다. 주로 사용되는 3가지에 대해 알아보자.

https://docs.oracle.com/javase/7/docs/api/java/util/Set.html

▶ HashSet

- HashSet : 해쉬 테이블에 원소를 저장하기 때문에 성능면에서 가장 우수하다. 단, 원소들의 순서가 일정하지 않다.

 

HashSet<String> hashSet = new HashSet<String>();

 

hashSet.add(“Milk”);

hashSet.add(“Bread”);

hashSet.add(“Butter”);

hashSet.add(“Cheese”);

hashSet.add(“Ham”);

hashSet.add(“Ham”);

 

System.out.println(hashSet);

 

출력 결과 : [Bread, Milk, Butter, Ham, Cheese] -> 순서가 임의적이다.

https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

▶ TreeSet

- TreeSet : 레드-블랙 트리(red-black tree)에 원소를 저장하므로 값에 따라서 순서가 결정되며 속도가 HashSet보다 느리다.

 

TreeSet<String> treeSet = new TreeSet<String>();

 

treeSet.add(“Milk”);

treeSet.add(“Bread”);

treeSet.add(“Butter”);

treeSet.add(“Cheese”);

treeSet.add(“Ham”);

treeSet.add(“Ham”);

 

System.out.println(treeSet);

 

출력 결과 : [Bread, Butter, Cheese, Ham, Milk] -> 알파벳 순으로 정렬됨

 

https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

▶ LinkedHashSet

- LinkedHashSet : 해쉬 테이블과 연결 리스트의 결합된 형태로 원소들의 순서는 삽입되었던 순서와 같다. 야간의 비용을 들여서 HashSet의 문제점인 순서의 불명확성을 제거한 방법이다.

 

LinkedHashSet<String> linked = new LinkedHashSet<String>();

linked.add(“Milk”);

linked.add(“Bread”);

linked.add(“Butter”);

linked.add(“Cheese”);

linked.add(“Ham”);

linked.add(“Ham”);

 

System.out.println(linked);

 

출력 결과 : [Milk, Bread, Butter, Cheese, Ham] -> 입력된 순서대로 출력됨.

대량 연산 메소드
set1.containsAll(set2)	만약 set2가 set1의 부분집합이면 true를 반환한다.
set1.addAll(set2)	set1을 set1과 set2의 합집합으로 만든다.
set1.retainAll(set2)	set1을 set1과 set2의 교집합으로 만든다.
set1.removeAll(set2)	set1을 set1과 set2의 차집합으로 만든다. (set1 – set2)

- 집합 연산 시 주의할 점은 원집합이 파괴되면 안되므로 항상 연산 수행 전에 복사본을 만들어야 한다.

 

Set<String> union = new HashSet<String>(set1); //합집합을 위해 set1의 복사본을 union에 저장한다.

union.addAll(set2);

https://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html