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


##########
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:
   `k > bits`



##########
src/main/java/org/apache/commons/collections4/bloomfilter/Hasher.java:
##########
@@ -52,5 +55,14 @@ public interface Hasher {
      * @param shape the shape of the desired Bloom filter.
      * @return the iterator of integers
      */
-    IndexProducer uniqueIndices(Shape shape);
+    default IndexProducer uniqueIndices(Shape shape) {
+        return new IndexProducer() {

Review Comment:
   The functional interface can return a lambda:
   ```java
           return consumer -> {
               Objects.requireNonNull(consumer, "consumer");
               return 
Hasher.this.indices(shape).forEachIndex(IndexFilter.create(shape, consumer));
           };
   ```



##########
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:
   Since length will be positive you could use a bit shift here: `int segment = 
buffer.length >>> 1`
   
   The conversion to long is not easy to explain and the javadoc is missing 
details. After dividing in half, up to the first 8 bytes from each half are 
used to construct a long. The bytes are interpreted in big-endian order but if 
the buffer is less than 8 bytes then zeros are effectively prepended at the 
start.
   
   This is a non-standard zero fill behaviour (true big-endian number after the 
BE):
   ```
   // big-endian order with zero filling start
   a          -> a          BE: a0000000
   ab         -> ab         BE: ab000000
   abcdefg    -> abcdefg    BE: abcdefg0
   abcdefgh   -> abcdefgh   BE: abcdefgh
   
   // Now ignoring the end as we reached 8 bytes
   abcdefghi  -> abcdefgh
   abcdefghij -> abcdefgh
   ```
   This is basically not achieving the same as:
   ```Java
           // copy (with zero-fill) at least 8 bytes from the offset
           return ByteBuffer.wrap(
               Arrays.copyOfRange(byteArray, offset, offset + Math.max(len, 8)))
               .order(ByteOrder.BIG_ENDIAN)
               .getLong();
   ```
   
   If you keep it the same then note that the `toLong` method can avoid an 
addition inside the loop by using a start-end iteration:
   ```java
       private static long toLong(byte[] byteArray, int offset, int len) {
           long val = 0;
           final int end = offset + Math.min(len, Long.BYTES);
           for (int i = offset; i < end; i++) {
               val <<= 8;
               val |= (byteArray[i] & 0xff);
           }
           return val;
       }
   ```
   The bytes could be interpreted as little-endian:
   ```java
       private static long toLong(byte[] byteArray, int offset, int len) {
           long val = 0;
           final int end = offset + Math.min(len, Long.BYTES);
           int shift = 0;
           for (int i = offset; i < end; i++) {
               val |= (byteArray[i] & 0xff) << shift;
               shift += 8;
           }
           return val;
       }
   ```
   Using the little endian is easier to explain as the bytes are cut in half 
and up to 8 bytes from each is read as a long in little endian order. 
   
   Using little-endian, or the current code, both create smaller numbers when 
needing zero fill. Only a true big-endian read will create a large number.
   
   ### Thoughts on the hasher input:
   
   Note that it is worse to create smaller numbers for the increment and start 
point. If the start is smaller than the number of bits in a filter then hashing 
will start at the same point when the size increases; likewise the increment 
will be the same if it remains smaller than the number of bits in the filter 
and so the first few indices will be the same if the number of bits changes 
(but is still larger than the increment). In a worse case scenario with small 
start and increments for all items, hashing may not create indices that fill 
the full region within a much larger filter. Imagine hashers created with a 
single byte for the start and increment (bounded to 255) with a filter size of 
30000 and number of hash functions as 5. Ignoring the tetrahedral addition (a 
maximum of 20 for k=5) the max index is 255 * 4 + 255 = 1275, this covers 4.25% 
of the filter. This also ignores the negative wrapping but the behaviour is the 
same, some bits cannot be reached.
   
   So this needs to be avoided as the filter probability assumptions will be 
void. If the start and increment are larger than the number of bits then the 
modulus will create a 'random' position and increment within the size. However 
if limited to only 1 byte then you still only have 255 possible start positions 
even though randomly spread. So use big-endian numbers does not help. What 
matters is the number of bits of entropy in the start and increment. If there 
are more than 4 bytes to create the long (little-endian) the numbers will be 
expected to exceed the maximum size of a filter (limited to a 32-bit int).
   
   This behaviour could be noted in the javadoc. It is recommended to create a 
hasher using at least twice the number of random bytes as the number of 
non-zero bytes in the shape number of bits:
   ```java
   2 * Math.ceil(Integer.highestOneBit(shape.getNumberOfBits()) / 8.0)
   ```
   That is quite verbose. To simplify then assume a max size shape and 
recommend that a hasher is not constructed with fewer than 8 bytes of entropy 
through the `byte[]` constructor, or the 4 bytes of entropy for each argument 
to the `long, long` constructor; and then update to interpret the bytes as 
little-endian.
   



##########
src/main/java/org/apache/commons/collections4/bloomfilter/Shape.java:
##########
@@ -186,20 +186,6 @@ public double estimateN(int cardinality) {
         return -(m / k) * Math.log1p(-c / m);
     }
 
-    /**

Review Comment:
   This was from a previous documented factory. If you are happy that this is 
covered by the class javadoc then fine. I think the factory method names can be 
implied to use the standard variable names, but it is not explicitly 
documented. 
   
   Note: Unrelated - why is shape comparable? I thought this was previously 
discussed as unnecessary. I cannot find a Jira ticket for this. The method is 
not tested to return a specific order; its only usage in the package is in the 
equals function.
   
   



##########
src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * To be used for testing only.

Review Comment:
   You could transfer the javadoc from the old SimpleHasher to here. At least 
then the method is explained.



##########
src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * To be used for testing only.
+ */
+class IncrementingHasher implements Hasher {
+
+    /**
+     * The initial hash value.
+     */
+    private final long initial;
+
+    /**
+     * The value to increment the hash value by.
+     */
+    private final long increment;
+
+    /**
+     * Constructs the IncrementingHasher from 2 longs.  The long values will 
be interpreted as unsigned values.
+     * <p><em>If the increment is zero the default increment is used 
instead.</em></p>
+     * @param initial The initial value for the hasher.
+     * @param increment The value to increment the hash by on each iteration.
+     * @see #getDefaultIncrement()

Review Comment:
   NA



##########
src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * To be used for testing only.
+ */
+class IncrementingHasher implements Hasher {
+
+    /**
+     * The initial hash value.
+     */
+    private final long initial;
+
+    /**
+     * The value to increment the hash value by.
+     */
+    private final long increment;
+
+    /**
+     * Constructs the IncrementingHasher from 2 longs.  The long values will 
be interpreted as unsigned values.
+     * <p><em>If the increment is zero the default increment is used 
instead.</em></p>
+     * @param initial The initial value for the hasher.
+     * @param increment The value to increment the hash by on each iteration.
+     * @see #getDefaultIncrement()
+     */
+    IncrementingHasher(long initial, long increment) {
+        this.initial = initial;
+        this.increment = increment;
+    }
+
+    /**
+     * Performs a modulus calculation on an unsigned long and an integer 
divisor.
+     * @param dividend a unsigned long value to calculate the modulus of.
+     * @param divisor the divisor for the modulus calculation.
+     * @return the remainder or modulus value.
+     */
+    static int mod(long dividend, int divisor) {

Review Comment:
   Duplicate of `EnhancedDoubleHasher.mod`. Since that method (which is tested) 
is package-private then just call that.



##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -21,14 +21,15 @@
 
 /**
  * A Hasher that implements combinatorial hashing as as described by
- * <a 
href="https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf";>Krisch 
and Mitzenmacher</a>.
+ * <a 
href="https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf";>Krisch 
and Mitzenmacher</a> using the enhanced double hashing technique
+ * described in the wikipedia article  <a 
href="https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing";>Double
 Hashing</a>.
  * <p>
  * Common use for this hasher is to generate a byte array as the output of a 
hashing

Review Comment:
   `Common use for this hasher is to generate bit indices from a byte array 
output of ...`



##########
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:
   This line has no coverage.
   
   The last commit to Codecov failed. I reran the job to see if it was a 
glitch. You can do the same locally using:
   ```Java
   mvn test jacoco:report
   open 
target/site/jacoco/org.apache.commons.collections4.bloomfilter/EnhancedDoubleHasher.java.html
   ```



##########
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractHasherTest.java:
##########
@@ -78,12 +81,40 @@ public void testHashing(int k, int m) {
 
     @Test
     public void testUniqueIndex() {
-        // create a hasher that produces duplicates with the specified shape.
-        // this setup produces 5, 17, 29, 41, 53, 65 two times
-        Shape shape = Shape.fromKM(12, 72);
-        Hasher hasher = new SimpleHasher(5, 12);
-        Set<Integer> set = new HashSet<>();
-        assertTrue(hasher.uniqueIndices(shape).forEachIndex(set::add), 
"Duplicate detected");
-        assertEquals(6, set.size());
+        // @formatter:off
+        /*
+         * The probability of a collision when

Review Comment:
   Is there a reference for this?



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