HyperLogLog 这里面水很深，但是你必须趟一趟

package com.lizba.pf;
import java.util.concurrent.ThreadLocalRandom;
/** * <p> *      伯努利试验 中基数n与kmax之间的关系  n = 2^kmax * </p> * * @Author: Liziba * @Date: 2021/8/17 23:16 */public class BernoulliExperimentTest {
    static class BitKeeper {
        /** 记录最大的低位0的长度 */        private int kmax;

        public void random() {            // 生成随机数            long value = ThreadLocalRandom.current().nextLong(2L << 32);            int len = this.lowZerosMaxLength(value);            if (len > kmax) {                kmax = len;            }
        }
        /**         * 计算低位0的长度         * 这里如果不理解看下我的注释         * value >> i 表示将value右移i,  1<= i <32 ， 低位会被移出         * value << i 表示将value左移i,  1<= i <32 ， 低位补0         * 看似一左一右相互抵消，但是如果value低位是0右移被移出后，左移又补回来，这样是不会变的，但是如果移除的是1，补回的是0，那么value的值就会发生改变         * 综合上面的方法，就能比较巧妙的计算低位0的最大长度         *         * @param value         * @return         */        private int lowZerosMaxLength(long value) {            int i = 1;            for (; i < 32; i++) {                if (value >> i << i != value) {                    break;                }            }            return i - 1;        }
    }

    static class Experiment {        /** 测试次数n */        private int n;        private BitKeeper bitKeeper;
        public Experiment(int n) {            this.n = n;            this.bitKeeper = new BitKeeper();        }
        public void work() {            for(int i = 0; i < n; i++) {                this.bitKeeper.random();            }        }
        /**         * 输出每一轮测试次数n         * 输出 logn / log2 = k 得 2^k = n，这里的k即我们估计的kmax         * 输出 kmax，低位最大0位长度值         */        public void debug() {            System.out.printf("%d %.2f %d\n", this.n, Math.log(this.n) / Math.log(2), this.bitKeeper.kmax);        }    }
    public static void main(String[] args) {        for (int i = 0; i < 100000; i++) {            Experiment experiment = new Experiment(i);            experiment.work();            experiment.debug();        }    }
}

package com.lizba.pf;
import java.util.concurrent.ThreadLocalRandom;
/** * <p> *      HyperLogLog 简单实现 * </p> * * @Author: Liziba * @Date: 2021/8/18 10:40 */public class HyperLogLogTest {
    static class BitKeeper {
        /** 记录最大的低位0的长度 */        private int kmax;

        /**         * 计算低位0的长度，并且保存最大值kmax         *         * @param value         */        public void random(long value) {            int len = this.lowZerosMaxLength(value);            if (len > kmax) {                kmax = len;            }        }
        /**         * 计算低位0的长度         * 这里如果不理解看下我的注释         * value >> i 表示将value右移i,  1<= i <32 ， 低位会被移出         * value << i 表示将value左移i,  1<= i <32 ， 低位补0         * 看似一左一右相互抵消，但是如果value低位是0右移被移出后，左移又补回来，这样是不会变的，但是如果移除的是1，补回的是0，那么value的值就会发生改变         * 综合上面的方法，就能比较巧妙的计算低位0的最大长度         *         * @param value         * @return         */        private int lowZerosMaxLength(long value) {            int i = 1;            for (; i < 32; i++) {                if (value >> i << i != value) {                    break;                }            }            return i - 1;        }    }

    static class Experiment {
        private int n;        private int k;        /** 分桶，默认1024，HyperLogLog中是16384个桶，并不适合我这里粗糙的算法 */        private BitKeeper[] keepers;
        public Experiment(int n) {            this(n, 1024);        }
        public Experiment(int n, int k) {            this.n = n;            this.k = k;            this.keepers = new BitKeeper[k];            for (int i = 0; i < k; i++) {                this.keepers[i] = new BitKeeper();            }        }
        /**         * (int) (((m & 0xfff0000) >> 16) % keepers.length) -> 计算当前m在keepers数组中的索引下标         * 0xfff0000 是一个二进制低16位全为0的16进制数，它的二进制数为 -> 1111111111110000000000000000         * m & 0xfff0000 可以保理m高16位， (m & 0xfff0000) >> 16 然后右移16位，这样可以去除低16位，使用高16位代替高16位         * ((m & 0xfff0000) >> 16) % keepers.length 最后取模keepers.length，就可以得到m在keepers数组中的索引         */        public void work() {            for (int i = 0; i < this.n; i++) {                long m = ThreadLocalRandom.current().nextLong(1L << 32);                BitKeeper keeper = keepers[(int) (((m & 0xfff0000) >> 16) % keepers.length)];                keeper.random(m);            }        }
        /**         * 估算 ，求倒数的平均数，调和平均数         *         * @return         */        public double estimate() {            double sumBitsInverse = 0.0;            // 求调和平均数            for (BitKeeper keeper : keepers) {                sumBitsInverse += 1.0 / (float) keeper.kmax;            }            double avgBits = (float) keepers.length / sumBitsInverse;            return Math.pow(2, avgBits) * this.k;        }
    }
    /**     * 测试     *     * @param args     */    public static void main(String[] args) {        for (int i = 100000; i < 1000000; i+=100000) {            Experiment experiment = new Experiment(i);            experiment.work();            double estimate = experiment.estimate();            // i 测试数据            // estimate 估算数据            // Math.abs(estimate - i) / i 偏差百分比            System.out.printf("%d %.2f %.2f\n", i, estimate, Math.abs(estimate - i) / i);        }    }
}