Set - 자바가 제공하는 Set4 - 최적화

자바의 HashSet은 우리가 직접 구현한 내용과 거의 같지만 다음과 같은 최적화를 추가로 진행한다.

 

최적화

• 해시 기반 자료 구조를 사용하는 경우 통계적으로 입력한 데이터의 수가 배열의 크기를 75%정도 넘어가면 해시 인덱스가 자주 충돌한다. 따라서 75%가 넘어가면 성능이 떨어지기 시작한다.
  • 해시 충돌로 같은 해시 인덱스에 들어간 데이터를 검색하려면 모두 탐색해야 한다. 따라서 성능이O(n)으로 좋지 않다.
• 하지만 데이터가 동적으로 계속 추가되기 때문에 적절한 배열의 크기를 정하는 것은 어렵다.
• 자바의 HashSet은 데이터의 양이 배열 크기의 75%를 넘어가면 배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다.
  • 해시 인덱스를 다시 적용하는 시간이 걸리지만, 결과적으로 해시 충돌이 줄어든다.
  • 자바 HashSet의 기본 크기는 16이다.

 

데이터 양 75%이상 증가

 

배열의 크기 2배 증가, 해시 다시 계산

• 데이터양이 75% 이상이면 배열의 크기를 2배로 증가하고, 모든 데이터의 해시 인덱스를 커진 배열에 맞추어 다시 계산한다. 이 과정을 재해싱(rehashing)이라 한다.
• 인덱스 충돌 가능성이 줄어든다.
• 여기서 데이터가 다시 75%이상 증가하면 다시 2배 증가와 재계산을 반복한다.

정리

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