Implementation of Bloom Filter in Java
- Bloom filter is a probabilistic data structure which is used to find association of a member in a set.
- Bloom filter is space optimized because it uses bits(after hasing key) to store a key in a set.
- If Bloom filter return FALSE for association of a member in a set,that means member is not part of that set. True positive rate of bloom filter is 1.
- If Bloom filter return TRUE for association of a member in a set, that means member might be or might not be part of that set. False positive rate of bloom filter is greater than 0.
- The false positive rate depends on multiple factors like type of hash function, number of hash function, no of insertions etc..
- Guava library provides implementation of Bloom Filter in Java. Check this
![image](https://private-user-images.githubusercontent.com/26311536/248563075-2ba17e96-b4cc-4b1c-967e-23fdbd93bf0f.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQ3MjkzOTksIm5iZiI6MTcyNDcyOTA5OSwicGF0aCI6Ii8yNjMxMTUzNi8yNDg1NjMwNzUtMmJhMTdlOTYtYjRjYy00YjFjLTk2N2UtMjNmZGJkOTNiZjBmLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA4MjclMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwODI3VDAzMjQ1OVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWIzNjQ0ZDQ5Mzc5YTJmMThlNjEyN2U3NGNlNjQyNTgxMmRmNThmMTBmNGYxN2M3OGNkN2UxM2Y0ZmFiN2FmYWMmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.Gxc7AMxrvQ0zHuT6QYCVJmgPUdgLkTgnQWVYpeTvVTY)
![image](https://private-user-images.githubusercontent.com/26311536/248563167-66807470-06aa-4fa8-ab8c-4d5011a679df.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQ3MjkzOTksIm5iZiI6MTcyNDcyOTA5OSwicGF0aCI6Ii8yNjMxMTUzNi8yNDg1NjMxNjctNjY4MDc0NzAtMDZhYS00ZmE4LWFiOGMtNGQ1MDExYTY3OWRmLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA4MjclMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwODI3VDAzMjQ1OVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWQ0NWNmNWI1N2FmY2FiMGM2MWZjOTNjOWE0MTRhNzJmYjVmNDdlOTljZjIwYTExYTY2YjA0ZWI5ZmFmMDQ4NWQmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.Drr2xhRsKUxLKBLuJa31RnPNO1hgUINoKxWzcyLWw04)
![image](https://private-user-images.githubusercontent.com/26311536/249862113-09a394af-87f8-496f-a27b-0a5118e2a4ff.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQ3MjkzOTksIm5iZiI6MTcyNDcyOTA5OSwicGF0aCI6Ii8yNjMxMTUzNi8yNDk4NjIxMTMtMDlhMzk0YWYtODdmOC00OTZmLWEyN2ItMGE1MTE4ZTJhNGZmLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA4MjclMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwODI3VDAzMjQ1OVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWY2NDYxMDJlYTdlNmE4ZmEyOThmNGE3ZjEzODc5Mjk2ZTc5NTIwMDQ3ZGNiZWM2YzExYTY2OTk0MmVlMzVmMjUmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.PLA72gZ_GQIERgoiQqa1HedWpTrq_M8HTHI7_T0v3R8)
![image](https://private-user-images.githubusercontent.com/26311536/249862497-401bab13-f784-47bc-b3ce-58bf1ab1e57a.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQ3MjkzOTksIm5iZiI6MTcyNDcyOTA5OSwicGF0aCI6Ii8yNjMxMTUzNi8yNDk4NjI0OTctNDAxYmFiMTMtZjc4NC00N2JjLWIzY2UtNThiZjFhYjFlNTdhLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA4MjclMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwODI3VDAzMjQ1OVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWEwOGQyZjRlY2Q1MTQ2NzhjNzUyOWQ1ZDViZWY5MTQ0N2RkMDczMGU0OGM5ZjVhZDdjMjI1ZDU5Y2Y2Mjc5MjYmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.v6woJDN68og7FQXCrK23qh6FUMcpeMxO50ObzcpNuJo)