1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.collections4.bloomfilter; 18 19 import java.util.Objects; 20 import java.util.function.IntPredicate; 21 22 /** 23 * A Hasher that implements simple combinatorial hashing as described by 24 * <a href="https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf">Krisch and Mitzenmacher</a>. 25 * 26 * <p>To be used for testing only.</p> 27 */ 28 public final class IncrementingHasher implements Hasher { 29 30 /** 31 * The initial hash value. 32 */ 33 private final long initial; 34 35 /** 36 * The value to increment the hash value by. 37 */ 38 private final long increment; 39 40 /** 41 * Constructs the IncrementingHasher from 2 longs. The long values will be interpreted as unsigned values. 42 * <p> 43 * The initial hash value will be the modulus of the initial value. 44 * Subsequent values will be calculated by repeatedly adding the increment to the last value and taking the modulus. 45 * </p> 46 * @param initial The initial value for the hasher. 47 * @param increment The value to increment the hash by on each iteration. 48 */ 49 public IncrementingHasher(final long initial, final long increment) { 50 this.initial = initial; 51 this.increment = increment; 52 } 53 54 @Override 55 public IndexProducer indices(final Shape shape) { 56 Objects.requireNonNull(shape, "shape"); 57 58 return new IndexProducer() { 59 @Override 60 public int[] asIndexArray() { 61 final int[] result = new int[shape.getNumberOfHashFunctions()]; 62 final int[] idx = new int[1]; 63 64 // This method needs to return duplicate indices 65 66 forEachIndex(i -> { 67 result[idx[0]++] = i; 68 return true; 69 }); 70 return result; 71 } 72 73 @Override 74 public boolean forEachIndex(final IntPredicate consumer) { 75 Objects.requireNonNull(consumer, "consumer"); 76 final int bits = shape.getNumberOfBits(); 77 78 // Essentially this is computing a wrapped modulus from a start point and an 79 // increment. So actually you only need two modulus operations before the loop. 80 // This avoids any modulus operation inside the while loop. It uses a long index 81 // to avoid overflow. 82 83 long index = BitMap.mod(initial, bits); 84 final int inc = BitMap.mod(increment, bits); 85 86 for (int functionalCount = 0; functionalCount < shape.getNumberOfHashFunctions(); functionalCount++) { 87 if (!consumer.test((int) index)) { 88 return false; 89 } 90 index += inc; 91 index = index >= bits ? index - bits : index; 92 } 93 return true; 94 } 95 }; 96 } 97 }