aherbert commented on PR #501:
URL:
https://github.com/apache/commons-collections/pull/501#issuecomment-2160492067
The increment `inc` is adjusted by `i`. If it is negative then it has
wrapped and we add `bits`. This works only if `i` is always less than `bits`.
If `i > bits` then when we adjust `inc` by adding `bits` it may still be
negative. This is then an invalid increment to use to adjust `index`.
In the worst case the `inc` will be a large enough negative that `index -=
inc` will great a number above the size in `bits`. That could cause a bounds
error on the IntPredicate consumer.
In the real world the upper loop will not be used. It is a fail safe for bad
use. A number of hash functions greater than the number of bits would saturate
the filter very fast. An alternative less friendly solution would be to throw
an IllegalArgumentException if called under these conditions.
As to resetting the tetrahedral number then you are correct. My fail-safe
implementation is wrong for a correct enhanced double hasher. What the upper
loop requires is for the `inc + bits` to be repeated until `inc` is positive:
```java
for (int i = 1; i <= k; i++) {
if (!consumer.test(index)) {
return false;
}
// Update index and handle wrapping
index -= inc;
index = index < 0 ? index + bits : index;
// Incorporate the counter into the increment to
create a
// tetrahedral number additional term, and handle
wrapping
// **given** i can exceed bits
inc -= i;
if (inc < 0) {
inc += bits;
while (inc < 0) {
inc += bits;
}
}
}
```
Try that and see if we have coverage. If not then we should add a test to
make sure that we are testing extremely bad usage and the hasher still works.
--
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]
