java实现简易版布隆过滤器

java实现简易版布隆过滤器

public class BloomFilters {

    
    private int arraySize;

    
    private int[] array;

    public BloomFilters(int arraySize){
        this.arraySize = arraySize;
        this.array = new int[arraySize];
    }

    public void add(String key){
        int hash1 = hashcode_1(key);
        int hash2 = hashcode_2(key);
        int hash3 = hashcode_3(key);
        array[hash1 % arraySize] = 1;
        array[hash2 % arraySize] = 1;
        array[hash3 % arraySize] = 1;
    }

    public boolean mightContain(String code){
        int hash1 = hashcode_1(code);
        int hash2 = hashcode_2(code);
        int hash3 = hashcode_3(code);
        return array[hash1 % arraySize] == 1 && array[hash2 % arraySize] == 1 && array[hash3 % arraySize] == 1;
    }

    
    private int hashcode_1(String key){
        int hash = 0;
        for(int i = 0; i < key.length(); i++){
            hash += 33 + key.charAt(i);
        }
        return Math.abs(hash);
    }

    
    private int hashcode_2(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++) {
            hash = (hash ^ data.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }

    
    private int hashcode_3(String key) {
        int hash, i;
        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return Math.abs(hash);
    }

    public static void main(String[] args) {
        BloomFilters bloomFilters = new BloomFilters(10000000);
        for (int i = 0; i < 1000000; i++) {
            if(i == 12334 || i == 23223 || i == 2332){
                continue;
            }
            bloomFilters.add(i + "");
        }
        System.out.println(bloomFilters.mightContain("12334"));
        System.out.println(bloomFilters.mightContain("23223"));
        System.out.println(bloomFilters.mightContain("2332"));
        System.out.println(bloomFilters.mightContain("23324"));
    }
}