Claudenw commented on code in PR #320:
URL: 
https://github.com/apache/commons-collections/pull/320#discussion_r933840784


##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -129,24 +126,60 @@ public IndexProducer indices(final Shape shape) {
             @Override
             public boolean forEachIndex(IntPredicate consumer) {
                 Objects.requireNonNull(consumer, "consumer");
-                int bits = shape.getNumberOfBits();
-                /*
-                 * Essentially this is computing a wrapped modulus from a 
start point and an
-                 * increment. So actually you only need two modulus operations 
before the loop.
-                 * This avoids any modulus operation inside the while loop. It 
uses a long index
-                 * to avoid overflow.
-                 */
-                long index = mod(initial, bits);
+                final int bits = shape.getNumberOfBits();
+                // Enhanced double hashing:
+                // hash[i] = ( h1(x) + i*h2(x) + (i*i*i - i)/6 ) mod bits
+                // See: 
https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing
+                //
+                // Essentially this is computing a wrapped modulus from a 
start point and an
+                // increment and an additional term as a tetrahedral number.
+                // You only need two modulus operations before the loop. 
Within the loop
+                // the modulus is handled using the sign bit to detect 
wrapping to ensure:
+                // 0 <= index < bits
+                // 0 <= inc < bits
+                // The final hash is:
+                // hash[i] = ( h1(x) - i*h2(x) - (i*i*i - i)/6 ) wrapped in 
[0, bits)
+
+                int index = mod(initial, bits);
                 int inc = mod(increment, bits);
 
-                for (int functionalCount = 0; functionalCount < 
shape.getNumberOfHashFunctions(); functionalCount++) {
-
-                    if (!consumer.test((int) index)) {
-                        return false;
+                final int k = shape.getNumberOfHashFunctions();
+                if (k>bits) {

Review Comment:
   fixed



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to