확률적 자료구조 — HyperLogLog, Count-Min Sketch의 원리

1. 각 요소를 해시합니다
   hash("Alice") = 0001 0110 1011 ...
                    ^^^^ 선행 0이 3개 → 최대 3

   hash("Bob")   = 0000 0010 1101 ...
                    ^^^^^^ 선행 0이 5개 → 최대 5로 갱신

2. 선행 0의 최대값 R이면, 추정 카디널리티 ≈ 2^R
   R = 5 → 약 32개의 고유 값

3. 정확도를 높이기 위해 여러 버킷(레지스터)으로 나눠서 추정
   해시의 앞쪽 비트로 버킷 결정, 나머지로 선행 0 계산
   각 버킷의 추정치를 조화 평균으로 합산

public class SimpleHyperLogLog {
    private static final int BUCKET_COUNT = 16384; // 2^14 = 16384 버킷
    private int[] registers;

    public SimpleHyperLogLog() {
        registers = new int[BUCKET_COUNT];
    }

    public void add(String element) {
        long hash = murmurhash(element);

        // 상위 14비트로 버킷 결정
        int bucket = (int) (hash >>> 50); // 상위 14비트

        // 나머지 50비트에서 선행 0 개수 + 1
        long remaining = hash & ((1L << 50) - 1);
        int leadingZeros = Long.numberOfLeadingZeros(remaining) - 14 + 1;

        // 최댓값 갱신
        registers[bucket] = Math.max(registers[bucket], leadingZeros);
    }

    public long estimate() {
        // 조화 평균으로 추정
        double harmonicMean = 0;
        int zeroCount = 0;

        for (int reg : registers) {
            harmonicMean += Math.pow(2, -reg);
            if (reg == 0) zeroCount++;
        }

        double alpha = 0.7213 / (1 + 1.079 / BUCKET_COUNT); // 보정 상수
        double estimate = alpha * BUCKET_COUNT * BUCKET_COUNT / harmonicMean;

        // 작은 값 보정
        if (estimate <= 2.5 * BUCKET_COUNT && zeroCount > 0) {
            estimate = BUCKET_COUNT * Math.log((double) BUCKET_COUNT / zeroCount);
        }

        return Math.round(estimate);
    }
}

# 요소 추가: O(1)
PFADD visitors "user:1001"
PFADD visitors "user:1002"
PFADD visitors "user:1001"  # 중복 — 카운트에 영향 없음

# 고유 개수 추정: O(1)
PFCOUNT visitors  # 2 (추정치)

# 여러 HLL 병합: 일별 UV를 주별 UV로 합산
PFMERGE weekly:visitors daily:mon daily:tue daily:wed ...
PFCOUNT weekly:visitors  # 주간 고유 방문자 추정

# 메모리: 최대 12KB (정확한 카운팅은 수백 MB 필요)

@Service
public class UniqueVisitorService {
    private final StringRedisTemplate redis;

    // 방문자 기록
    public void recordVisit(String userId) {
        String key = "uv:" + LocalDate.now();
        redis.opsForHyperLogLog().add(key, userId);
    }

    // 오늘의 UV 추정
    public long getTodayUV() {
        String key = "uv:" + LocalDate.now();
        return redis.opsForHyperLogLog().size(key);
    }

    // 이번 주 UV 추정
    public long getWeeklyUV() {
        String[] keys = IntStream.range(0, 7)
            .mapToObj(i -> "uv:" + LocalDate.now().minusDays(i))
            .toArray(String[]::new);

        String mergedKey = "uv:weekly:" + LocalDate.now();
        redis.opsForHyperLogLog().union(mergedKey, keys);
        return redis.opsForHyperLogLog().size(mergedKey);
    }
}

Hash 1: [  2  |  0  |  3  |  0  |  1  |  0  |  0  |  4  ]
Hash 2: [  1  |  3  |  0  |  0  |  2  |  0  |  1  |  0  ]
Hash 3: [  0  |  0  |  2  |  1  |  0  |  3  |  0  |  0  ]

public class CountMinSketch {
    private int[][] table;
    private int width;
    private int depth;
    private int[] hashSeeds;

    public CountMinSketch(int width, int depth) {
        this.width = width;
        this.depth = depth;
        this.table = new int[depth][width];
        this.hashSeeds = new int[depth];

        Random random = new Random(42);
        for (int i = 0; i < depth; i++) {
            hashSeeds[i] = random.nextInt();
        }
    }

    // 빈도 증가: O(d)
    public void increment(String item) {
        for (int i = 0; i < depth; i++) {
            int index = hash(item, i) % width;
            table[i][index]++;
        }
    }

    // 빈도 추정: O(d) — 모든 행의 최솟값을 반환
    public int estimate(String item) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < depth; i++) {
            int index = hash(item, i) % width;
            min = Math.min(min, table[i][index]);
        }
        return min;
    }

    private int hash(String item, int i) {
        return Math.abs((item.hashCode() ^ hashSeeds[i]) * 31 + hashSeeds[i]);
    }
}

@Component
public class PopularUrlTracker {
    private final CountMinSketch sketch;
    private final PriorityQueue<Map.Entry<String, Integer>> topK;

    public PopularUrlTracker() {
        this.sketch = new CountMinSketch(10000, 5); // w=10000, d=5
        this.topK = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
    }

    public void recordAccess(String url) {
        sketch.increment(url);
    }

    public int getEstimatedCount(String url) {
        return sketch.estimate(url);
    }
}