자료구조 선택 (HashSet vs BitSet)

메모리 사용량

1. 비트셋(BitSet)의 메모리 사용

• 고정 비용: 비트셋은 내부적으로 long[] 배열로 비트를 저장합니다.
  • 예를 들어 new BitSet(1_000_000)은 약 1,000,000 비트(≈125 KB) + 배열 오버헤드(약 몇십 바이트) 정도를 사용합니다.
  • 저장 가능한 값의 최대치(=capacity)에 관계없이, capacity/8 바이트를 항상 차지합니다.
• 장점:대량의 연속된 정수 범위에서 “존재 여부”만 저장할 때 가장 압축적입니다.
• 단점:실제로 저장된 요소가 적더라도, 범위 전체에 대해 메모리를 할당합니다.

 

 

2. 해시셋(HashSet)의 메모리 사용

• 가변 비용: HashSet은 내부적으로 HashMap을 쓰고, 키마다 Node 객체(엔트리)와 버킷 배열(참조 배열)을 유지합니다.
  • 버킷 배열: 초기 크기 16, 로드 팩터 0.75 → 요소가 늘어나면 배열 크기를 2배씩 늘림
  • 엔트리 객체: 하나당 약 32~48바이트 (객체 헤더, 해시코드, 키 참조, 다음 노드 참조 등)
• 메모리:
  • 요소 수 n에 대해 대략 n × (엔트리 오버헤드) + 버킷 배열 크기 만큼 사용
  • 예컨대 1,000,000개의 정수를 저장하면 1,000,000×40B ≈ 40 MB + 버킷 배열(약 8 MB) = 총 48 MB 정도

 

3. 비교 요약

구분	비트셋(BitSet)	해시셋(HashSet)
저장 단위	비트(0/1)	객체 레퍼런스 + 엔트리 객체
메모리 규모	범위 크기(bits)/8+소수의 오버헤드	요소 수 × (~40 B) + 버킷 배열
적합한 경우	연속된 범위, 밀집된 데이터	희소(sparse) 데이터, 범위 모름

 

• 연속 범위가 작고 밀집된 값(n≈범위) → 비트셋이 더 효율
• 범위가 크고 실제 요소 수가 적은 경우 → 해시셋이 더 효율

 

메모리 계산

1. 주요 파라미터 정의

• N: 저장할 유니크 값의 개수
• R: 값이 가질 수 있는 전체 범위 크기 = (max – min + 1)
• E: HashSet 엔트리당 오버헤드 (Java HotSpot 기준 대략 32∼48 byte)
• B: HashSet 버킷 배열 오버헤드 (참조 배열 크기)
• 비트셋 바이트 = R / 8

예시) 값이 [-1,000,000 ~ 1,000,000] 범위, 유니크 수 N=100,000, 엔트리 오버헤드 E=40 byte, 버킷 오버헤드 B≈8 MB 라고 가정.

 

2. 예상 메모리 계산식

1) BitSet(또는 boolean[])

• M_bitset = R / 8
• 예) R=2,000,001 → M_bitset ≈ 250,000 byte (≈0.24 MB)

2) HashSet

• M_hashset = N × E + B
• 예) N=100,000, E=40 B, B=8 MB
• → M_hashset = 100,000×40 + 8,388,608 ≈ 12,388,608 byte (≈11.8 MB)

3. 손익분기점(Break-even) 구하기

• M_bitset < M_hashset 이면 비트셋이 메모리 면에서 유리합니다.
• R/8  <  N×E + B  → N > (R/8 - B) / E 
• B를 무시하거나 작다고 본다면
  • N_threshold ≈ (R/8) / E
• 예시값 대입
  • N_threshold ≈ 250,000 / 40 = 6,250

⇒ 유니크 값이 6,250개 초과라면 BitSet(고정메모리)이 메모리 유리.
⇒ 그 이하면 HashSet(N에 따라 증가하는 메모리).