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.

  1. /*
  2.  *    Java Program to Implement Bloom Filter
  3.  */
  4.  
  5. import java.util.*;    
  6. import java.security.*;
  7. import java.math.*;
  8. import java.nio.*;
  9.  
  10. /* Class BloomFilter */
  11. class BloomFilter
  12. {    
  13.     private byte[] set;
  14.     private int keySize, setSize, size;
  15.     private MessageDigest md;
  16.  
  17.     /* Constructor */
  18.     public BloomFilter(int capacity, int k)
  19.     {
  20.         setSize = capacity;
  21.         set = new byte[setSize];
  22.         keySize = k;
  23.         size = 0;
  24.         try 
  25.         {
  26.             md = MessageDigest.getInstance("MD5");
  27.         } 
  28.         catch (NoSuchAlgorithmException e) 
  29.         {
  30.             throw new IllegalArgumentException("Error : MD5 Hash not found");
  31.         }
  32.     }
  33.     /* Function to clear bloom set */
  34.     public void makeEmpty()
  35.     {
  36.         set = new byte[setSize];
  37.         size = 0;
  38.         try 
  39.         {
  40.             md = MessageDigest.getInstance("MD5");
  41.         } 
  42.         catch (NoSuchAlgorithmException e) 
  43.         {
  44.             throw new IllegalArgumentException("Error : MD5 Hash not found");
  45.         }
  46.     }
  47.     /* Function to check is empty */
  48.     public boolean isEmpty()
  49.     {
  50.         return size == 0;
  51.     }
  52.     /* Function to get size of objects added */
  53.     public int getSize()
  54.     {
  55.         return size;
  56.     }
  57.     /* Function to get hash - MD5 */
  58.     private int getHash(int i)
  59.     {
  60.         md.reset();
  61.         byte[] bytes = ByteBuffer.allocate(4).putInt(i).array();
  62.         md.update(bytes, 0, bytes.length);
  63.         return Math.abs(new BigInteger(1, md.digest()).intValue()) % (set.length - 1);
  64.     }
  65.     /* Function to add an object */
  66.     public void add(Object obj)
  67.     {
  68.         int[] tmpset = getSetArray(obj);
  69.         for (int i : tmpset)
  70.             set[i] = 1;
  71.         size++;
  72.     }
  73.     /* Function to check is an object is present */
  74.     public boolean contains(Object obj) 
  75.     {
  76.         int[] tmpset = getSetArray(obj);
  77.         for (int i : tmpset)
  78.             if (set[i] != 1)
  79.                 return false;
  80.         return true;
  81.     }
  82.     /* Function to get set array for an object */
  83.     private int[] getSetArray(Object obj)
  84.     {
  85.         int[] tmpset = new int[keySize];
  86.         tmpset[0] = getHash(obj.hashCode());
  87.         for (int i = 1; i < keySize; i++)
  88.             tmpset[i] = (getHash(tmpset[i - 1]));
  89.         return tmpset;
  90.     }    
  91. }
  92.  
  93. /* Class BloomFilterTest */
  94. public class BloomFilterTest
  95. {
  96.     public static void main(String[] args)
  97.     {
  98.         Scanner scan = new Scanner(System.in);
  99.         System.out.println("Bloom Filter Test\n");   
  100.  
  101.         System.out.println("Enter set capacity and key size");
  102.         BloomFilter bf = new BloomFilter(scan.nextInt() , scan.nextInt());
  103.  
  104.         char ch;
  105.         /*  Perform bloom filter operations  */
  106.         do    
  107.         {
  108.             System.out.println("\nBloomFilter Operations\n");
  109.             System.out.println("1. insert ");
  110.             System.out.println("2. contains");
  111.             System.out.println("3. check empty");
  112.             System.out.println("4. clear");
  113.             System.out.println("5. size");
  114.  
  115.             int choice = scan.nextInt();            
  116.             switch (choice)
  117.             {
  118.             case 1 : 
  119.                 System.out.println("Enter integer element to insert");
  120.                 bf.add( new Integer(scan.nextInt()) );                     
  121.                 break;                          
  122.             case 2 : 
  123.                 System.out.println("Enter integer element to search");
  124.                 System.out.println("Search result : "+ bf.contains( new Integer(scan.nextInt()) ));
  125.                 break;                                          
  126.             case 3 : 
  127.                 System.out.println("Empty status = "+ bf.isEmpty());
  128.                 break;
  129.             case 4 : 
  130.                 System.out.println("\nBloom set Cleared");
  131.                 bf.makeEmpty();
  132.                 break;    
  133.             case 5 : 
  134.                 System.out.println("\nSize = "+ bf.getSize() );
  135.                 break;            
  136.             default : 
  137.                 System.out.println("Wrong Entry \n ");
  138.                 break;   
  139.             }    
  140.  
  141.             System.out.println("\nDo you want to continue (Type y or n) \n");
  142.             ch = scan.next().charAt(0);                        
  143.         } while (ch == 'Y'|| ch == 'y');    
  144.     }
  145. }

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.