자료구조 선택 (HashSet vs BitSet)
·
Java/성능최적화
메모리 사용량1. 비트셋(BitSet)의 메모리 사용고정 비용: 비트셋은 내부적으로 long[] 배열로 비트를 저장합니다.예를 들어 new BitSet(1_000_000)은 약 1,000,000 비트(≈125 KB) + 배열 오버헤드(약 몇십 바이트) 정도를 사용합니다.저장 가능한 값의 최대치(=capacity)에 관계없이, capacity/8 바이트를 항상 차지합니다.장점:대량의 연속된 정수 범위에서 “존재 여부”만 저장할 때 가장 압축적입니다.단점:실제로 저장된 요소가 적더라도, 범위 전체에 대해 메모리를 할당합니다. 2. 해시셋(HashSet)의 메모리 사용가변 비용: HashSet은 내부적으로 HashMap을 쓰고, 키마다 Node 객체(엔트리)와 버킷 배열(참조 배열)을 유지합니다.버킷 배열:..