Java:在最后一分钟实现 Hit() 和 getNumHits()

Question

这更像是一个设计问题，但我只是想知道是否有人对这个问题有任何想法。

在一次面试中，我被要求设计 2 个方法。

hit();
getNumHits();

hit() 每次用户向服务器发出请求时调用，getNumHits() 返回最后一分钟的点击次数。

有什么想法吗？

更新:

我知道这是一个副本

Implementation of a "hits in last [second/minute/hour]" data structure

但我在理解 C++ 代码时遇到了一些困难，想知道我们是否可以获得 Java 版本的答案!

Answer 1

您要寻找的核心是保留最后一分钟内所有匹配项的列表。使用 LinkedList 可以实现快速的 removeFirst()。

class HitCounter {

    // My most recent list - only the last minute is retained.
    LinkedList<Long> hitList = new LinkedList<>();
    private static final long OneMinute = 1000L * 60L;

    public void hit() {
        // Track the hit.
        hitList.add(System.currentTimeMillis());
        // Always clean up.
        cleanup();
    }

    public int hitCount() {
        // Make sure we are clean.
        cleanup();
        return hitList.size();
    }

    private void cleanup() {
        // Eat all stale hits.
        while (hitList.getFirst() < System.currentTimeMillis() - OneMinute) {
            hitList.removeFirst();
        }
    }
}

但是，如果您的命中非常快，并且您怀疑保留所有命中的所有时间是否有效，您可以使用桶系统进行量化。在这里，我每一秒都在计数。很明显，你可能会在一秒钟内被击中多少次。

class HitCounter {

    // One bucket - keeps track of how many hits since the start time.
    private class Bucket {

        // Probably should use an atomic.
        int count;
        // The time this bucket was started.
        long started = System.currentTimeMillis();
    }
    // My most recent list - only the last minute is retained.
    LinkedList<Bucket> hitList = new LinkedList<>();
    private static final long OneSecond = 1000L;
    private static final long OneMinute = OneSecond * 60L;

    public void hit() {
        // Grab the hit time.
        long now = System.currentTimeMillis();
        // Normally goes in the last bucket.
        Bucket bucket = hitList.size() > 0 ? hitList.getLast() : null;
        // Time for new bucket?
        if (bucket == null || now > bucket.started + OneSecond) {
            // Yup!
            hitList.add(bucket = new Bucket());
        }
        // Track the hit.
        bucket.count++;
        // Always clean up.
        cleanup();
    }

    public int hitCount() {
        // Make sure we are clean.
        cleanup();
        // Add up all the bucket counts.
        int total = 0;
        for (Bucket bucket : hitList) {
            total += bucket.count;
        }
        return total;
    }

    private void cleanup() {
        // Eat all stale hits.
        while (hitList.size() > 0 && hitList.getFirst().started < System.currentTimeMillis() - OneMinute - OneSecond) {
            hitList.removeFirst();
        }
    }
}

public void test() throws InterruptedException {
    HitCounter hitList = new HitCounter();
    for (int i = 0; i < 90; i++) {
        hitList.hit();
        System.out.println(i + " - " + hitList.hitCount());
        Thread.sleep(1000);
    }
}