Class Xor8

src/main/java/utils/Xor8.java:13–162

The xor filter, a new algorithm that can replace a Bloom filter. It needs 1.23 log(1/fpp) bits per key. It is related to the BDZ algorithm [1] (a minimal perfect hash function algorithm). [1] paper: Simple and Space-Efficient Minimal Perfect Hash Functions - http://cmph.sourceforge.net/papers/wads

 * http://cmph.sourceforge.net/papers/wads07.pdf
 */
public class Xor8 {

    private static final int BITS_PER_FINGERPRINT = 8;
    private static final int HASHES = 3;
    private static final int OFFSET = 2;
    private static final int FACTOR_TIMES_100 = 123;
    private final int size;
    private final int arrayLength;
    private final int blockLength;
    private long seed;
    private byte[][] ciphertext;
    private final int bitCount;
    private static Random random = new Random();


    private static int getArrayLength(int size) {
        return (int) (OFFSET + (long) FACTOR_TIMES_100 * size / 100);
    }


    public Xor8(long[] keys, byte[][] ct) {
        this.size = keys.length;
        arrayLength = getArrayLength(size);
        bitCount = arrayLength * BITS_PER_FINGERPRINT;
        blockLength = arrayLength / HASHES;
        int m = arrayLength;
        ciphertext = new byte[m][];
        long[] reverseOrder = new long[arrayLength];
        byte[] reverseH = new byte[arrayLength];
        int reverseOrderPos;
        long seed;
        do {
            seed = Hash.randomSeed();
            byte[] t2count = new byte[m];
            long[] t2 = new long[m];
            for (int i = 0; i < size; i++) {
                long k = i;
                for (int hi = 0; hi < HASHES; hi++) {
                    int h = getHash(keys[i], seed, hi);
                    t2[h] ^= k;
                    if (t2count[h] > 120) {
                        // probably something wrong with the hash function
                        // let us not crash the system:
                        throw new IllegalArgumentException();
                    }
                    t2count[h]++;
                }
            }
            reverseOrderPos = 0;
            int[][] alone = new int[HASHES][blockLength];
            int[] alonePos = new int[HASHES];
            for (int nextAlone = 0; nextAlone < HASHES; nextAlone++) {
                for (int i = 0; i < blockLength; i++) {
                    if (t2count[nextAlone * blockLength + i] == 1) {
                        alone[nextAlone][alonePos[nextAlone]++] = nextAlone * blockLength + i;
                    }
                }
            }