Java Program to Implement Bloom Filter

This is a Java Program to implement Bloom Filter. A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not; i.e. a query returns either “inside set (may be wrong)” or “definitely not in set”. Elements can be added to the set, but not removed (though this can be addressed with a “counting” filter). The more elements that are added to the set, the larger the probability of false positives.

Here is the source code of the Java program to implement Bloom Filter. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/*
 *    Java Program to Implement Bloom Filter
 */
 
import java.util.*;    
import java.security.*;
import java.math.*;
import java.nio.*;
 
/* Class BloomFilter */
class BloomFilter
{    
    private byte[] set;
    private int keySize, setSize, size;
    private MessageDigest md;
 
    /* Constructor */
    public BloomFilter(int capacity, int k)
    {
        setSize = capacity;
        set = new byte[setSize];
        keySize = k;
        size = 0;
        try 
        {
            md = MessageDigest.getInstance("MD5");
        } 
        catch (NoSuchAlgorithmException e) 
        {
            throw new IllegalArgumentException("Error : MD5 Hash not found");
        }
    }
    /* Function to clear bloom set */
    public void makeEmpty()
    {
        set = new byte[setSize];
        size = 0;
        try 
        {
            md = MessageDigest.getInstance("MD5");
        } 
        catch (NoSuchAlgorithmException e) 
        {
            throw new IllegalArgumentException("Error : MD5 Hash not found");
        }
    }
    /* Function to check is empty */
    public boolean isEmpty()
    {
        return size == 0;
    }
    /* Function to get size of objects added */
    public int getSize()
    {
        return size;
    }
    /* Function to get hash - MD5 */
    private int getHash(int i)
    {
        md.reset();
        byte[] bytes = ByteBuffer.allocate(4).putInt(i).array();
        md.update(bytes, 0, bytes.length);
        return Math.abs(new BigInteger(1, md.digest()).intValue()) % (set.length - 1);
    }
    /* Function to add an object */
    public void add(Object obj)
    {
        int[] tmpset = getSetArray(obj);
        for (int i : tmpset)
            set[i] = 1;
        size++;
    }
    /* Function to check is an object is present */
    public boolean contains(Object obj) 
    {
        int[] tmpset = getSetArray(obj);
        for (int i : tmpset)
            if (set[i] != 1)
                return false;
        return true;
    }
    /* Function to get set array for an object */
    private int[] getSetArray(Object obj)
    {
        int[] tmpset = new int[keySize];
        tmpset[0] = getHash(obj.hashCode());
        for (int i = 1; i < keySize; i++)
            tmpset[i] = (getHash(tmpset[i - 1]));
        return tmpset;
    }    
}
 
/* Class BloomFilterTest */
public class BloomFilterTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Bloom Filter Test\n");   
 
        System.out.println("Enter set capacity and key size");
        BloomFilter bf = new BloomFilter(scan.nextInt() , scan.nextInt());
 
        char ch;
        /*  Perform bloom filter operations  */
        do    
        {
            System.out.println("\nBloomFilter Operations\n");
            System.out.println("1. insert ");
            System.out.println("2. contains");
            System.out.println("3. check empty");
            System.out.println("4. clear");
            System.out.println("5. size");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                bf.add( new Integer(scan.nextInt()) );                     
                break;                          
            case 2 : 
                System.out.println("Enter integer element to search");
                System.out.println("Search result : "+ bf.contains( new Integer(scan.nextInt()) ));
                break;                                          
            case 3 : 
                System.out.println("Empty status = "+ bf.isEmpty());
                break;
            case 4 : 
                System.out.println("\nBloom set Cleared");
                bf.makeEmpty();
                break;    
            case 5 : 
                System.out.println("\nSize = "+ bf.getSize() );
                break;            
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }    
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');    
    }
}
Bloom Filter Test
 
Enter set capacity and key size
1000 1000
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
1
Enter integer element to insert
57
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
1
Enter integer element to insert
97
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
1
Enter integer element to insert
91
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
1
Enter integer element to insert
23
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
1
Enter integer element to insert
67
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
2
Enter integer element to search
67
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
2
Enter integer element to search
25
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
2
Enter integer element to search
33
Search result : false
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
2
Enter integer element to search
97
Search result : true
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
5
 
Size = 5
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
4
 
Bloom set Cleared
 
Do you want to continue (Type y or n)
 
y
 
BloomFilter Operations
 
1. insert
2. contains
3. check empty
4. clear
5. size
3
Empty status = true
 
Do you want to continue (Type y or n)
 
n

Related posts:

Tạo số và chuỗi ngẫu nhiên trong Java
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Java Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
Hướng dẫn Java Design Pattern – Iterator
Sử dụng CountDownLatch trong Java
Spring Data Java 8 Support
RegEx for matching Date Pattern in Java
Java Program to Implement ArrayDeque API
Java Program to Generate Random Numbers Using Multiply with Carry Method
Spring Security Logout
Introduction to Spring Data JPA
The Java 8 Stream API Tutorial
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Removing all Nulls from a List in Java
Java Program to Implement Adjacency Matrix
Hướng dẫn Java Design Pattern – Facade
An Introduction to ThreadLocal in Java
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Java Program to Implement Caesar Cypher
Flattening Nested Collections in Java
Java Program to add two large numbers using Linked List
A Quick Guide to Spring MVC Matrix Variables
Initialize a HashMap in Java
Java Program to Implement Gaussian Elimination Algorithm
Spring Boot - Apache Kafka
Java Program to Implement LinkedList API
Java Program to Implement Quick sort
Spring Boot - Scheduling
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
So sánh ArrayList và LinkedList trong Java
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm