logo
  • Home
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

Java Program to Implement Bloom Filter

Posted on September 7, 2013 by Manish
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.

If you wish to look at all Java Programming examples, go to Java Programs.
« Prev Page - Java Program to Implement Threaded Binary Tree
» Next Page - Java Program to Implement Triply Linked List
« Java Program to Implement Variable length array
Java Program to Implement Triply Linked List »

Deep Dive @ Sanfoundry:

  1. Java Training II – Advanced Java Training
  2. Java Programming Examples on Numerical Problems & Algorithms
  3. C Programming Examples on Bitwise Operations
  4. 100+ Java Android Programming Examples
  5. Java Programming Examples on Computational Geometry Problems & Algorithms
  6. Java Programming Examples on Graph Problems & Algorithms
  7. Java Programming Examples on Hard Graph Problems & Algorithms
  8. C Programming Examples on Arrays
  9. Java Programming Examples on Combinatorial Problems & Algorithms
  10. Java Programming Examples on Data-Structures
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer and SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage & Cluster Administration, Advanced C Programming, SAN Storage Technologies, SCSI Internals and Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him below:
LinkedIn | Facebook | Twitter | Google+

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
TOS & Privacy
Jobs
Bangalore Training
Online Training
SAN Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry