3
\$\begingroup\$

See also the next iteration.

This snippet is a counting Bloom filter supporting removal of elements as well. Instead of a bit vector it maintains a vector of "bucket counters". Also, the API supports well taking your customised hash functions.

Inserting: Just compute all hash values and increment all counters indexed by hash values.

Querying: Compute hash values once again, and if at least one indexes a counter with value of zero, the element can be safely inferred to be not in the filter.

Removal: Compute hash values. Check that the element may be in the filter, and if so, decrement by one all the counters indexed by the hash values.

All in all, Bloom filter may report false positives, but never false negatives.

A couple of questions:

  1. Is the API design good enough?
  2. What hash functions a grown-up programmer would use?

And the code follows:

net.coderodde.util.BloomFilter:

package net.coderodde.util;

/**
 * This class implements a counting Bloom filter which allows not only 
 * inserting, querying, but deleting an element as well.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class BloomFilter<T> {

    /**
     * The minimum capacity of the counter array.
     */
    private static final int MINIMUM_CAPACITY = 128;

    /**
     * The array holding the counts of each bucket.
     */
    private final int[] array;

    /**
     * The array of hash functions.
     */
    private final AbstractHashFunction[] hashFunctions;

    /**
     * Constructs a counting Bloom filter with array capacity {@code capacity}
     * and given hash functions.
     * 
     * @param capacity           the capacity of the counter array.
     * @param firstHashFunction  the mandatory hash function.
     * @param otherHashFunctions the array of voluntary hash functions.
     */
    public BloomFilter(int capacity, 
                       AbstractHashFunction<T> firstHashFunction,
                       AbstractHashFunction<T>... otherHashFunctions) {
        capacity = Math.max(capacity, MINIMUM_CAPACITY);
        this.array = new int[capacity];
        this.hashFunctions = 
                new AbstractHashFunction[otherHashFunctions.length + 1];
        this.hashFunctions[otherHashFunctions.length] = firstHashFunction;

        System.arraycopy(otherHashFunctions, 
                         0, 
                         this.hashFunctions, 
                         0, 
                         otherHashFunctions.length);
    }

    /**
     * Adds an element to this filter. Works by computing the hash values of the 
     * element and increments the counters indexed by those hash values.
     * 
     * @param element the element to add.
     */
    public void add(T element) {
        for (AbstractHashFunction<T> hashFunction : hashFunctions) {
            array[Math.abs(hashFunction.hash(element)) % array.length]++;
        }
    }

    /**
     * Queries whether {@code element} is possibly in the filter. This may give
     * false positives, but never false negatives. A false positive is the 
     * situation where an element is reported to be in the filter when it was 
     * never added to it. A false negative is the situation where an element
     * is reported not being in the filter when it was actually added to the 
     * filter.
     * 
     * @param element the element to query.
     * @return {@code false} if the element is definitely not in the filter, and
     *         {@code true} otherwise.
     */
    public boolean contains(T element) {
        for (AbstractHashFunction<T> hashFunction : hashFunctions) {
            if (array[Math.abs(hashFunction.hash(element)) % 
                    array.length] == 0) {
                return false;
            }
        }

        return true;
    }

    /**
     * Removes the {@code element} from this filter. In the first pass, this
     * operation makes sure that there is chance that the input element was 
     * added to this filter. If so, it decrements the counters indexed by the 
     * hash values.
     * 
     * @param element the element to remove.
     */
    public void remove(T element) {
        if (contains(element)) {
            for (AbstractHashFunction<T> hashFunction : hashFunctions) {
                array[Math.abs(hashFunction.hash(element)) % array.length]--;
            }
        }
    }
}

net.coderodde.util.AbstractHashFunction:

package net.coderodde.util;

/**
 * This abstract class defines the API for hash functions.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public abstract class AbstractHashFunction<T> {

    /**
     * Produces the hash value for {@code element}.
     * @param element
     * @return 
     */
    public abstract int hash(T element);

}

net.coderodde.util.BitPermutationHashFunction:

package net.coderodde.util;

import java.util.Random;
import java.util.stream.IntStream;

/**
 * This hash function attempts to permute the bits of hash values returned by
 * {@link hashCode}.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 * @param <T> the element type.
 */
public class BitPermutationHashFunction<T> extends AbstractHashFunction<T> {

    /**
     * The amount of bits per an integer.
     */
    private static final int BITS_PER_INT = 32;

    /**
     * The bit index permutation. Is not required to be an actual permutation.
     */
    private final int[] permutationMap;

    /**
     * Constructs a hash function that uses a randomly generated index 
     * permutation.
     */
    public BitPermutationHashFunction() {
        this(createIndexPermutation(new Random()));
    }

    /**
     * Constructs a hash function with given bit reordering.
     * 
     * @param permutationMap the permutation map.
     */
    public BitPermutationHashFunction(int[] permutationMap) {
        checkPermutationMap(permutationMap);
        checkPermutationMap(permutationMap);
        this.permutationMap = permutationMap;
    }

    @Override
    public int hash(T element) {
        int code = element.hashCode();
        int hash = 0;

        for (int bitIndex = 0; bitIndex < BITS_PER_INT; ++bitIndex) {
            boolean bit = readBit(code, bitIndex);
            hash = setBit(hash, bit, permutationMap[bitIndex]);
        }

        return hash;
    }

    /**
     * Reads the {@code index}th least significant bit from the integer 
     * {@code value}.
     * 
     * @param value the integer to read.
     * @param index the index of the bit to read.
     * @return {@code true} only if the bit in question is set to one (1).
     */
    private boolean readBit(int value, int index) {
        return (value & (1 << index)) != 0;
    }

    /**
     * Returns the integer whose {@code index}th least significant bit is set
     * according to {@code bit}: if it is set to {@code true}, the bit is set to
     * one, otherwise to zero.
     * 
     * @param value the integer to operate on.
     * @param bit   the bit to set.
     * @param index the index of the bit to set.
     * @return      the new integer with particular bit set.
     */
    private int setBit(int value, boolean bit, int index) {
        if (bit) {
            return value | (1 << index);
        }

        return value & (~(1 << index));
    }

    /**
     * Checks that the array of indices contains indices within proper range.
     * This method, however, does not enforce the input array to be a 
     * permutation of integers {@code 0, 1, 2, ..., 31}.
     * 
     * @param permutationMap the permutation map to check.
     */
    private void checkPermutationMap(int[] permutationMap) {
        for (int i : permutationMap) {
            if (i < 0) {
                throw new IndexOutOfBoundsException(
                        "The index is negative: " + i);
            } else if (i >= BITS_PER_INT) {
                throw new IndexOutOfBoundsException(
                        "The index is too large: " + BITS_PER_INT + ". Must " +
                        "be at most " + (BITS_PER_INT - 1) + ".");
            }
        }
    }

    /**
     * Creates a shuffled array of integer bit indices.
     * 
     * @param random the random number generator.
     * @return the index permutation.
     */
    private static int[] createIndexPermutation(Random random) {
        int[] ret = IntStream.range(0, BITS_PER_INT).toArray();

        for (int i = 0; i < 3 * BITS_PER_INT; ++i) {
            int a = random.nextInt(BITS_PER_INT);
            int b = random.nextInt(BITS_PER_INT);

            int tmp = ret[a];
            ret[a] = ret[b];
            ret[b] = tmp;
        }

        return ret;
    }
}

net.coderodde.util.XorHashFunction:

package net.coderodde.util;

import java.util.Random;

/**
 * This hash function takes an exclusive or with the hash code returned by an 
 * element, using a fixed mask.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 * @param <T> the element type.
 */
public class XorHashFunction<T> extends AbstractHashFunction<T> {

    /**
     * The mask used.
     */
    private final int mask;

    /**
     * Constructs this mask using a random mask.
     */
    public XorHashFunction() {
        this(new Random().nextInt());
    }

    /**
     * Constructs this mask using a particular mask.
     * 
     * @param mask the mask to use.
     */
    public XorHashFunction(int mask) {
        this.mask = mask;
    }

    @Override
    public int hash(T element) {
        return element.hashCode() ^ mask;
    }
}

Demo:

import net.coderodde.util.BitPermutationHashFunction;
import net.coderodde.util.BloomFilter;
import net.coderodde.util.XorHashFunction;

public class Demo {

    public static void main(String[] args) {
        String text = "Lorem ipsum dolor sit amet, consectetuer adipiscing " +
                      "elit. Sed posuere interdum sem. Quisque ligula eros " +
                      "ullamcorper quis, lacinia quis facilisis sed sapien. " +
                      "Mauris varius diam vitae arcu. Sed arcu lectus auctor " +
                      "vitae, consectetuer et venenatis eget velit. Sed " +
                      "augue orci, lacinia eu tincidunt et eleifend nec lacus.";

        String[] words = text.split("\\s+");

        BloomFilter<String> filter = 
                new BloomFilter<>(200, 
                                  new BitPermutationHashFunction<>(),
                                  new XorHashFunction<>(),
                                  new XorHashFunction<>());

        System.out.println("--- Adding words ---");
        int longestWordLength = 0;

        for (String word : words) {
            System.out.println("Adding \"" + word + "\"");
            filter.add(word);
            longestWordLength = Math.max(word.length(), longestWordLength);
        }

        System.out.println();
        System.out.println("--- Removing ---");

        for (int i = 10; i < 20; ++i) {
            System.out.println("Removing \"" + words[i] + "\"");
            filter.remove(words[i]);
        }

        System.out.println();
        System.out.println("--- Querying ---");

        for (String word : words) {
            System.out.printf("%-" + longestWordLength + "s : %s\n", word,
                    (filter.contains(word) ? 
                            "maybe there" : 
                            "definitely not"));
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

I can't speak to hashing functions, but I can talk about API.

BloomFilter

  • Should be final. You don't want users extending BloomFilter, since the class is not designed for that.
  • The documentation doesn't discuss what happens in any exceptional conditions, such as when null values get passed into any of the methods. The class level documentation should specify what the type represents. In the constructor docs, don't say array. Array is an implementation detail. Also, you label 'firstHashFunction' as 'mandatory', but that's the only place it's discussed. Call it 'first', and include in the class/constructor documentation that at least one is required. Finally, if clients may not be familiar with Bloom filters, you may want to summarize at the class level why they're useful and how to use the class.

AbstractHashFunction

  • Should be an interface named HashFunction. You provide no implementation, and this is SPI - something intended to be customizable by the library client. Don't take away their ability to extend a concrete class without a good reason.
  • The documentation is poor. The interface defines a contract, not an API. The class/method documentation should clearly indicate the contract the implementer is expected to uphold, including standard behavior, pre- and post- conditions, if applicable, and failure conditions.

BitPermutationHashFunction, XorHashFunction

While they are part of the library, these shouldn't really be part of the API. Currently they are, because you allow clients to extend them. Since they are not designed or documented for that, you should make them final.

\$\endgroup\$
2
\$\begingroup\$

Edge case in remove()

Suppose you insert an item that hashes to 0 and 1 (two hash functions). So you increment array[0] and array[1] to 1. Now you search for a different item that hashes to 0 and 0. This item is considered to be contained by the bloom filter because array[0] is 1. So far so good: this was a false positive but those are allowed.

But now suppose you try to remove the second item. It is considered to be contained by the bloom filter, so it is allowed to be removed. But when you try to remove it, it will decrement array[0] twice, leaving it at value -1. You can add a check to prevent your array values from becoming negative.

The larger problem is that if you remove any false positive element, it may cause the bloom filter to change to a state where valid elements are no longer considered valid. However, since you can't tell which elements are valid and which are false positives, there's not too much you can do about that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.