반응형
메모리 사용량
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에 따라 증가하는 메모리).
반응형