비트셋과 비트 배열 — 대량 Boolean을 메모리 효율적으로 저장하기

boolean 배열: [00000001] [00000000] [00000001] [00000000]  → 4바이트, 4개 값
BitSet:       [1 0 1 0]                                     → 1바이트 미만, 4개 값

import java.util.BitSet;

BitSet bitSet = new BitSet(100); // 100비트 크기

// 비트 설정
bitSet.set(0);      // 0번 비트를 1로
bitSet.set(5);      // 5번 비트를 1로
bitSet.set(10, 20); // 10~19번 비트를 1로

// 비트 확인
boolean exists = bitSet.get(5);   // true
boolean absent = bitSet.get(3);   // false

// 비트 해제
bitSet.clear(5);    // 5번 비트를 0으로

// 설정된 비트 수
int count = bitSet.cardinality(); // 1로 설정된 비트 개수

// 반복
for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) {
    System.out.println("비트 " + i + "이 설정됨");
}

// BitSet 내부 (간략화)
public class BitSet {
    long[] words; // 64비트씩 묶어서 저장

    public void set(int bitIndex) {
        int wordIndex = bitIndex >> 6;        // bitIndex / 64
        words[wordIndex] |= (1L << bitIndex); // 해당 비트를 1로 설정
    }

    public boolean get(int bitIndex) {
        int wordIndex = bitIndex >> 6;
        return (words[wordIndex] & (1L << bitIndex)) != 0;
    }
}

BitSet a = new BitSet();
a.set(1); a.set(2); a.set(3);

BitSet b = new BitSet();
b.set(2); b.set(3); b.set(4);

// 합집합 (OR)
BitSet union = (BitSet) a.clone();
union.or(b);  // {1, 2, 3, 4}

// 교집합 (AND)
BitSet intersection = (BitSet) a.clone();
intersection.and(b);  // {2, 3}

// 차집합
BitSet diff = (BitSet) a.clone();
diff.andNot(b);  // {1}

// 대칭 차집합 (XOR)
BitSet symDiff = (BitSet) a.clone();
symDiff.xor(b);  // {1, 4}

// boolean 배열: n이 1억이면 약 100MB
boolean[] isComposite = new boolean[n + 1];
for (int i = 2; i * i <= n; i++) {
    if (!isComposite[i]) {
        for (int j = i * i; j <= n; j += i) {
            isComposite[j] = true;
        }
    }
}

// BitSet: n이 1억이면 약 12.5MB
public List<Integer> sieve(int n) {
    BitSet composite = new BitSet(n + 1);
    List<Integer> primes = new ArrayList<>();

    for (int i = 2; i <= n; i++) {
        if (!composite.get(i)) {
            primes.add(i);
            // i가 int 범위를 넘지 않도록 long으로 계산
            for (long j = (long) i * i; j <= n; j += i) {
                composite.set((int) j);
            }
        }
    }
    return primes;
}

public class SimpleBloomFilter {
    private BitSet bitSet;
    private int size;
    private int hashCount;

    public SimpleBloomFilter(int size, int hashCount) {
        this.bitSet = new BitSet(size);
        this.size = size;
        this.hashCount = hashCount;
    }

    // 해시 함수 (더블 해싱)
    private int hash(String value, int i) {
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16; // 상위 비트를 활용
        return Math.abs((hash1 + i * hash2) % size);
    }

    public void add(String value) {
        for (int i = 0; i < hashCount; i++) {
            bitSet.set(hash(value, i));
        }
    }

    public boolean mightContain(String value) {
        for (int i = 0; i < hashCount; i++) {
            if (!bitSet.get(hash(value, i))) {
                return false; // 확실히 없음
            }
        }
        return true; // 있을 수도 있음 (False Positive 가능)
    }
}

// 캐시 관통(Cache Penetration) 방지 예시
@Service
public class ProductService {
    private final SimpleBloomFilter existFilter;

    public Product getProduct(Long id) {
        // 1. 블룸 필터로 빠르게 확인
        if (!existFilter.mightContain(id.toString())) {
            return null; // 확실히 없는 데이터 → DB 조회 불필요
        }

        // 2. 캐시 확인
        Product cached = cache.get(id);
        if (cached != null) return cached;

        // 3. DB 조회
        return productRepository.findById(id).orElse(null);
    }
}

// 권한 시스템 — 비트 플래그
public class Permission {
    public static final int READ    = 1;       // 0001
    public static final int WRITE   = 1 << 1;  // 0010
    public static final int EXECUTE = 1 << 2;  // 0100
    public static final int ADMIN   = 1 << 3;  // 1000

    private int flags;

    public void grant(int permission) {
        flags |= permission;  // OR로 권한 추가
    }

    public void revoke(int permission) {
        flags &= ~permission; // AND NOT으로 권한 제거
    }

    public boolean has(int permission) {
        return (flags & permission) == permission;
    }
}

// 사용 예시
Permission perm = new Permission();
perm.grant(Permission.READ | Permission.WRITE); // 읽기 + 쓰기 권한
perm.has(Permission.READ);    // true
perm.has(Permission.ADMIN);   // false

enum Permission { READ, WRITE, EXECUTE, ADMIN }

// 내부적으로 long 하나의 비트를 사용 (enum 원소가 64개 이하일 때)
EnumSet<Permission> permissions = EnumSet.of(Permission.READ, Permission.WRITE);

permissions.add(Permission.EXECUTE);
permissions.contains(Permission.ADMIN); // false

// 합집합, 교집합 등 집합 연산도 가능
EnumSet<Permission> all = EnumSet.allOf(Permission.class);