[Java] HashSet의 load factor

출처

ChatGPT

---

HashSet은 자바에서 중복을 허용하지 않는 집합(Set) 자료구조이다. 내부적으로 HashMap을 사용해 데이터를 저장하며, HashSet의 성능 특성(특히 삽입과 검색 성능)은 HashMap과 매우 밀접한 관련이 있다. HashSet의 load factor(부하율)는 HashMap의 load factor와 동일한 개념을 사용하며, 이는 해시 테이블에서 성능과 메모리 사용량을 조절하는 중요한 요소이다.

• 관련 글 -> [Java] HashSet 구현

 

1. load factor 란?

load factor(부하율)는 해시 테이블의 버킷이 얼마나 차야 해시 테이블의 크기를 자동으로 늘릴지를 결정하는 값이다. 즉, 해시 테이블이 얼마나 채워지면 테이블의 크기를 증가시킬 것인지를 결정하는 기준이다.

기본 값

자바의 HashSet 및 HashMap에서 기본 load factor는 0.75이다. 즉, 해시 테이블이 75% 차게 되면, 테이블의 크기를 2배로 확장한다.

공식

load factor = 저장된 요소 수 / 해시 테이블의 버킷 수

 

예를 들어, HashSet이 16개의 버킷을 가지고 있고, 여기에 12개의 요소가 저장되어 있다면, load factor는 12/16 = 0.75가 된다. 이 값이 load factor 값을 넘으면, 테이블이 확장된다.

 

2. load factor의 역할

성능

load factor의 해시 충돌과 관련이 깊다. 충돌이 많이 발생하면 해시 테이블의 성능이 떨어지는데, 충돌을 줄이기 위해서는 해시 테이블이 어느 정도 여유 공간을 가지고 있어야 한다. load factor가 낮을수록 충돌 가능성이 줄어들어 검색 성능이 향상된다. 반면, 너무 낮은 load factor는 메모리 사용량이 증가할 수 있다.

메모리 사용

해시 테이블은 공간과 시간 사이의 트레이드오프가 존재한다. laod factor가 낮으면 충돌이 적고 성능이 향상되지만, 많은 빈 버킷을 유지해야 하므로 메모리 사용량이 증가한다. 반대로 load factor가 높으면 메모리 사용이 절약되지만 충돌이 발생할 가능성이 높아져 성능이 저하될 수 있다.

 

3. HashSet의 초기 용량과 laod factor 설정

HashSet을 생성할 때 초기 용량과 load factor를 설정할 수 있다. 이를 통해 메모리 사용량과 성능을 조절할 수 있다.

 

기본 생성자

기본 적으로 HashSet의 초기 용량은 16이며, load factor는 0.75이다.

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

 

초기 용량과 load factor 설정

특정 초기 용량과 load factor 값을 지정할 수 있다.

HashSet<String> set = new HashSet<>(initialCapacity, loadFactor);

 

• initialCapacity : 해시 테이블의 초기 크기(버킷 수)
• loadFactor : 해시 테이블이 얼마나 차면 크기를 확장할지를 결정하는 값

예시

HashSet<String> set = new HashSet<>(32, 0.5f);

 

위의 예에서는 HashSet의 초기 용량이 32이고, load factor는 0.5이다. 즉, 해시 테이블이 50% 차면 크기를 늘리기 시작한다.

 

4.  확장 테이블 확장 과정

해시 테이블은 load factor가 임계치에 도달하면 크기를 확장한다. 해시 테이블이 확장될 때마다 기존 요소들의 해시 값을 다시 계산해 새로운 버킷에 재배치한다. 이과정을 리해싱(rehashing)이라고 한다.

• 관련 글 -> [Java] 버킷 Butcket

리해싱 과정

• load factor가 초과되면 해시 테이블의 크기가 2배로 증가한다.
• 기존 해시 값을 기반으로 요소들이 다시 새로운 버킷에 할당된다.
• 리해싱은 성능 비용일 발생하므로, 너무 자주 발생하지 않도록 적절한 load factor 값을 설정하는 것이 중요하다.

 

5. load factor와 성능 간의 관계

낮은 load factor (예 : 0.5)

메모리 사용량이 증가하지만, 해시 충돌이 적기 때문에 검색, 삽입, 삭제의 성능이 향상된다.

높은 load factor(예 : 0.9)

메모리 사용량을 절약할 수 있지만, 해시 충돌이 발생할 가능성이 높아져 검색 성능이 저하될 수 있다. 충돌이 많아지면 충돌을 해결하기 위해 버킷의 체인 탐색(혹은 기타 충돌 해결 매커니즘)이 더 많이 발생한다.

 

일반적으로 자바에서 기본으로 사용하는 0.75는 성능과 메모리 사용 사이의 적절한 균형점으로 여겨진다.

 

6. 결론

• load factor는 해시 테이블이 얼마나 차면 크기를 확장할지를 결정하는 중요한 매개 변수이다. 
• HashSet과 HashMap에서 기본 load factor는 0.75이며, 이는 성능과 메모리 사용 사이에서 최적화된 값으로 간주된다.
• 개발자는 HashSet을 사용할 때 필요에 따라 load factor와 초기 용량을 조절햐 성능을 최적화할 수 있다. 너무 낮은 load factor는 메모리 낭비를 초래할 수 잇으며, 너무 높은 load facotr는 성능 저하를 유발할 수 있다.

이처럼 load factor는 해시 테이블의 성능을 결정하는 중요한 요소로, 용량과 충돌 해결의 균형을 유지하는 데 사용된다.