The Java Embedded Aggregator Class ApproxDistinctCountAggregate

 
    public static class ApproxDistinctCountAggregate implements Aggregate
    {
        static final int HASH_BITS = 25;
        static final int N_HASHES = 1 << (32 - HASH_BITS);
         
        public void initialize(Object val) 
        {
            accumulate(val);
        }
 
        public void accumulate(Object val) 
        {
            int h = val.hashCode();
            int j = h >>> HASH_BITS;
            int zeroBits = 1;
            while ((h & 1) == 0 && zeroBits <= HASH_BITS) 
             {
                h >>>= 1;
                zeroBits += 1;
            }
            if (maxZeroBits[j] < zeroBits) 
            {
                maxZeroBits[j] = zeroBits;
            }
        }
         
        public Object result()
        {
            final int m = N_HASHES;
            final double alpha_m = 0.7213 / (1 + 1.079 / (double)m);
            final double pow_2_32 = 0xffffffff;
            double E, c = 0;
            int i;
            for (i = 0; i < m; i++)
            {
                c += 1 / Math.pow(2., (double)maxZeroBits[i]);
            }
            E = alpha_m * m * m / c;
 
            if (E <= (5 / 2. * m))
            {
                double V = 0;
                for (i = 0; i < m; i++)
                {
                    if (maxZeroBits[i] == 0) 
                    {
                        V += 1;
                    }
                }
                if (V > 0)
                {
                    E = m * Math.log(m / V);
                }
            }
            else if (E > (1 / 30. * pow_2_32))
            {
                E = -pow_2_32 * Math.log(1 - E / pow_2_32);
            }
            return new Long((long)E);
        }
 
        public void merge(Aggregate other) 
        {
            int[] otherMaxZeroBits = ((ApproxDistinctCountAggregate)other).maxZeroBits;
            for (int i = 0; i < N_HASHES; i++) 
            {
                if (maxZeroBits[i] < otherMaxZeroBits[i]) 
                {
                    maxZeroBits[i] = otherMaxZeroBits[i];
                }
            }
        }
 
        int[] maxZeroBits = new int[N_HASHES];
    }