Java - Set과 HashSet

Java - Set

---

목차

1. Set 사용 이유 및 특징
2. Set의 구현체
3. HashSet 생성자
4. HashSet 기능
5. Hash 충돌

---

1. Set 사용 이유 및 특징

• Set은 중복된 원소를 갖지 않는다는 특성이 있다.

• 특정한 순서를 가지고 있지 않다.

• 중복을 제거해야 하는 상황이라면 Set을 고려할 만 하다.

---

2. Set의 구현체

1. HashSet

• Set은 인터페이스 이므로 구현체인 HashSet을 통해 객체를 생성한다.

Set<Integer> set = new HashSet<>();

• 이 외에도, LinkedHashSet, TreeSet 등 다양한 구현체가 있다.

---

3. HashSet 생성자

1. HashSet()

• 새로운 빈 Set을 생성한다.
• 내부적으로 HashMap을 쓰는데, capacity (16), load factor(0.75) 이다.

Set<Integer> set = new HashSet<>();

2. HashSet(Collection<? extends E> c)

• collections을 인자로 받아 새로운 Set을 생성할 수 있다.

List list = new ArrayList<>(List.of(1, 2, 3));
// 1 2 3

Set<Integer> set = new HashSet<>(list);
// 1 2 3 (순서 X)

3. HashSet(int initialCapacity)

• 새로운 빈 Set을 생성한다.
• capacity를 변경할 수 있으며, load factor(0.75) 이다.

4. HashSet(int initialCapacity, float loadFactor)

• 새로운 빈 Set을 생성한다.
• capacity와 load factor를 변경할 수 있다.

Capcity와 Load factor가 무엇일까 ?

HashSet의 내부는 HashMap으로 구현되어 있다. 데이터를 저장할 때 버킷이라는 배열에 저장한다. 처음부터 배열의 크기를 무한정 늘려 놓을 수가 없다. 만약 데이터를 조금만 저장한다면 남은 공간은 모두 낭비가 되기 때문이다. 그래서 Set은 처음의 배열의 크기 즉 데이터를 저장할 수 있는 공간인 capcity를 default로 16으로 설정해 둔다.

그렇다면 capacity를 넘어서 데이터를 저장하려고 하면 어떤일이 일어날까? 16개를 다 채운다음에 배열의 크기를 늘리는 것일까? 여기서 작용하는게 바로 load factor이다. load factor가 0.75이고 capacity가 16이라면, 16 * 0.75인 12의 공간에 데이터가 저장되면 capcity를 2배 늘려준다. 즉, 16의 공간이 다 쓰이기 전에 미리 저장 공간을 늘려 놓는다는 소리이다.

load factor가 너무 작으면, 아직 많이 쓰지도 않았는데 저장 공간을 키워 빈 공간이 많이 남아 비효율적일 위험이 크다.

---

4. HashSet 기능

1. add(E e)

• Set에 원소를 삽입한다.
• 만약 삽입하려는 원소가 이미 Set에 존재한다면 false를 반환하고 아무일도 일어나지 않는다.
• 중복되는 원소를 삽입하지 않는 원리는 객체의 hashCode()값을 비교하여, 만약 같다면 equals() method를 실행시켜 객체를 비교한다. 만약 같은 객체라면, 삽입하지 않는다.

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(2);
set.add(3);
// 1 2 3 (순서 X)

2. addAll(Collection<? extends E> c)

• 인자로 받은 Collection의 원소들을 Set에 추가한다.

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(2);
set.add(3);
// 1 2 3 (순서 X)

Set<Integer> otherSet = new HashSet<>();
otherSet.add(4);
otherSet.add(5);
// 4 5 (순서 X)

set.addAll(otherSet);
// set : 1 2 3 4 5 (순서 X)

3. contains(Object o)

• 이 Set안에 특정 원소가 있는지 확인할 때 쓴다.
• 특정 원소가 Set에 존재한다면 true를 반환한다.

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(2);
set.add(3);
// 1 2 3 (순서 X)

System.out.println(set.contains(1));
// true

System.out.println(set.contains(10));
// false

4. isEmpty()

• Set이 빈 상태인지 알고 싶을 때 사용한다.
• Set에 원소가 하나도 없으면 true를 반환한다.

Set<Integer> set = new HashSet<>();

// 원소 삽입 전
System.out.println(set.isEmpty());
// true

set.add(1);
set.add(2);

// 원소 삽입 후
System.out.println(set.isEmpty());
// false

5. remove(Object o)

• Set안의 특정 원소를 제거하고 싶을 때 사용한다.
• 특정 원소가 있다면, 지운 뒤 true를 반환한다.

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(2);
// 1 2 (순서 X)

System.out.println(set.remove(1));
// true
System.out.println(set.remove(4));
// false

6. size()

• Set의 들어있는 원소의 수를 알고 싶을 때 사용한다.
• 원소의 수를 반환한다.

Set<Integer> set = new HashSet<>();

set.add(1);
set.add(2);
// 1 2 (순서 X)

System.out.println(set.size());
// 2

---

5. HashSet의 해쉬 충돌

객체를 저장하다 보면 HashCode() 값이 같은 객체가 존재할 수 있다. 그런 상황에서는 어떻게 객체를 저장할까?

이러한 해쉬 충돌을 해결하기 위한 방법은 여러가지가 있다. 대표적인 두 가지 방법에 대해 알아보자.

1. Separate Chaining

이 방법은 같은 hashCode를 갖는 객체들을 리스트로 연결해 둔다. 만약 A라는 문자열과 B라는 문자열의 hashCode값이 10이라고 해보자. B라는 문자열을 찾는 상황이라고 가정할 때, 첫째로 B의 hashCode값을 계산해 10인걸 알아낸 뒤 버켓에 접근한다. 그 버켓은 hashCode가 10인 문자열들을 저장해 놓은 리스트를 참조하고 있어서 그 리스트에 접근하여 B라는 문자열을 찾아낼 수가 있다.

이러한 방법은 테이블 외부의 추가적인 공간을 요한다는 점에서 단점이라고 할 수 있다.

요즘은 링크드 리스트 대신 트리 자료구조를 활용한다고 한다. 데이터의 개수가 6개 이하이면 링크드 리스트를, 8개 이상이면 트리를 사용하여 효율을 높인다고 한다. 이렇게 6과 8로 설정해 차이가 1이 아닌 2가 나게한 이유는, 잦은 삽입과 반복으로 그 내부 구조를 링크드 리스트 또는 트리로 변환할 때 오버헤드가 생기기 때문이다.

2. Open Addressing

Open Addressing은 만약 삽입하려는 객체의 hashCode의 저장공간에 이미 다른 객체가 저장되어 있다면, 그 저장공간 바로 다음 공간에 저장한다. 이미 존재하는 테이블을 쓰는 것이기 때문에 외부의 저장공간이 따로 필요가 없다.

또한 연속된 공간에 데이터를 저장하기 때문에 cache 효율이 높은 장점이 있다.

만약 데이터를 저장/조회 한다고 하면, Linear Probing같은 방법을 사용한다고 한다.

[ 참고 문헌 ]

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

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

https://d2.naver.com/helloworld/831311