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


##########
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) {
+                    for (int j = k; j > 0;) {
+                        // handle k > bits
+                        final int block = Math.min(j, bits);
+                        j -= block;
+                        for (int i = 0; i < block; i++) {
+                            if (!consumer.test(index)) {
+                                return false;

Review Comment:
   Added test



##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -58,50 +59,46 @@ private static long toLong(byte[] byteArray, int offset, 
int len) {
     }
 
     /**
-     * Constructs the SimpleHasher from a byte array.
+     * Constructs the EnhancedDoubleHasher from a byte array.
      * <p>The byte array is split in 2 and each half is interpreted as a long 
value.
      * Excess bytes are ignored.  This simplifies the conversion from a Digest 
or hasher algorithm output
      * to the two values used by the SimpleHasher.</p>
-     * <p><em>If the second long is zero the default increment is used 
instead.</em></p>
      * @param buffer the buffer to extract the longs from.
      * @throws IllegalArgumentException is buffer length is zero.
-     * @see #getDefaultIncrement()
      */
-    public SimpleHasher(byte[] buffer) {
+    public EnhancedDoubleHasher(byte[] buffer) {
         if (buffer.length == 0) {
             throw new IllegalArgumentException("buffer length must be greater 
than 0");
         }
         int segment = buffer.length / 2;

Review Comment:
   Converted to big endian adding extra bytes of 0 when there are not enough 
bytes in the buffer.  Added "Thoughts on hasher" to the class javadocs. 
   



-- 
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