[JAVA ]Set , Map 알아보기, 로드 팩터 (Load Factor)와 HashSet의 리해싱

import java.util.*;

public class JavaSetMain {
    public static void main(String[] args) {
        run(new HashSet<String>());
        run(new LinkedHashSet<String>());
        run(new TreeSet<String>());
    }

    private static void run(Set<String> set) {
        System.out.println("set = " + set.getClass());
        set.add("C");
        set.add("B");
        set.add("A");
        set.add("1");
        set.add("2");
        Iterator<String> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        System.out.println();

    }
}

 

• 실행결과

 

 

• Set 종류와 특성
  1. HashSet
     • 입력한 순서를 보장하지 않음.
     • 해시 테이블을 기반으로 구현되어 빠른 조회와 삽입이 가능.
     • 실무에서 가장 많이 사용됨.
  2. LinkedHashSet
     • 입력한 순서를 유지.
     • 데이터 삽입 및 삭제 시에도 순서가 보장됨.
  3. TreeSet
     • 데이터 값을 기준으로 정렬.
     • 이진 검색 트리를 기반으로 구현되어 있으며, 삽입 시 자동으로 정렬됨.
     • 사용자 정의 객체의 정렬 기준은 Comparable 또는 Comparator 인터페이스를 구현하여 제공해야 함.

실무에서는 Set 이 필요한 경우 HashSet 을 가장 많이 사용한다고 한다.
입력 순서 유지, 값 정렬의 필요에 따라 LinkedHashSet, TreeSet 을 선택하면 된다.

 

Map 의 구현체도 Set 과 같은 원리를 따른다.

 

HashSet 은 내부적으로 해시맵의 자료 구조를 사용한다.

키- 값 저장 방식 대신 키만 저장하는 특수한 형태의 해시테이블로 이해하면 된다.

 

 

 

Map도 Set 과 똑같은 성질을 가진다.

입력한 순서 유지 , 데이터 값 정렬에 따라서 LinkedHashMap, TreeMap 을 선택하면 된다.

TreeSet과 정렬 기준

• TreeSet은 데이터의 크고 작음(정렬 기준)이 명확해야 사용 가능.
  • 예: 숫자(1, 2, 3) 또는 알파벳("A", "B", "C") 등.
• 사용자 정의 객체(Member 등)의 경우, 기본적으로 크기를 비교할 수 없으므로, 정렬 기준을 제공해야 함.
  • 방법:
    • Comparable 인터페이스: 클래스 자체에 자연 순서를 정의.
    • Comparator 인터페이스: 외부에서 정렬 기준 제공.

 

 

로드 팩터 (Load Factor)와 HashSet의 리해싱

로드 팩터 (Load Factor)

 

"로드 팩터"(Load Factor)는 해시 테이블의 중요한 성능 지표로, 테이블에 저장된 요소의 개수를 버킷 크기로 나눈 값입니다

• 로드 팩터(Loas Factor) 방이 얼마나 차 있는가?
• 해시 테이블에 저장된 개수 n 을 버킷의 개수 K 로 나눈것
• load factor = n / k
  • 저장 공간이 100 개 있을때 80 의 데이터가 들어있으면 로드팩터는 0.8 이다.

로드 팩터 비율에 따라 해시 함수를 재작성할지 또는 해시 테이블의 크기를 조정할지 결정한다.

자바 HashSet과 최적화

 

자바 HashSet 기본 동작

 

자바에서 HashSet은 기본적으로 0.75의 로드 팩터와 초기 크기를 설정하여 해시 테이블의 크기와 성능을 관리한다.

 

 

로드 팩터와 성능

로드 팩터는 해시 테이블의 채워진 정도를 나타내는 지표로, 해시 테이블에 저장된 요소의 수를 버킷의 개수로 나눈 값이다. 자바에서는 기본적으로 0.75의 로드 팩터를 사용한다.. 즉, 테이블의 크기가 75%를 초과하면 해시 테이블의 크기를 확장하고, 이때 리해싱이 발생한다.

• 75% 이상의 데이터가 추가되면 해시 인덱스 충돌이 자주 발생하고, 이로 인해 성능이 저하된다.
• 해시 충돌이 발생하면, 같은 해시 인덱스에 들어간 데이터를 전부 탐색해야 하므로 성능이 O(n) 으로 떨어지게 된다.

 

 

HashSet 리해싱

• 데이터양이 75% 이상 증가하면 그 만큼 해시 인덱스의 충돌 가능성도 높아진다.
• 데이터양이  75% 이상이면 배열의 크기를 2배로 증가하고, 모든 데이터의 해시 인덱스를  커진 배열에 맞추어 다시 계산한다. 이 과정을 리해싱이라고 한다.
• 리해싱은 해시 충돌을 줄이고, 데이터 검색과 삽입 성능을 개선하는 중요한 과정이다. 그러나 리해싱 과정은 시간이 소요될 수 있다.

 

 

 

 

 

참고자료 : 

김영한의 실전 자바 - 중급 2편